FORTRAN IV as a syntax language
B. M. Leavenworth · Communications of the ACM · 1964
Backus: I would like to hear some discussion on how we can measure the efficiency of some of these processors.Perlis: One measure is the ratio of the overage number of instructions the compiler executes per instruction the compiler produces.I understand that the ratio for 220 BALGOL was 700.Bauer: We have found ratios of 46 to 100 depending on the machine used.Dijkstra: We are running 1000.Greiback: Concerning pp.6-7ff. in IDA-CRD Working Paper No. 93, "An Error-correcting Parse Algorithm," the conjecture is correct--one can always find a BNF specification with desired properties.The theorem states: For every context-free psg one can find context-free psg whose rules are of form: Z --~ aY1, ..., Y~ where a is a terminal symbol, Z and Y~ are nonterminal.Here one can link (B, a), eliminate the pointers, and the algorithm is almost the multiple-path analyzer of Kuno-Oettinger.Details can be found in my thesis, "Inverse of Phrase Structure Generators" [Harvard Report NSF-11] and an unpublished paper, "A New Normalform Theorem for Phrase Structure Generators."The bracket ({ I) device you use is indeed an intermediate.Any BNF system (context-free psg) can be mechanically placed in this special form (which I call standard form), preserving ambiguities (or lack thereof).