A new grammatical transformation into LL(k) form (Extended Abstract)

ABSTRACT

For some time, it has been recognized that left-to-right deterministic top-down parsing has a number of features to recommend it. The logic of such a parser is easily expressed as a one-state pushdown machine, and very flexible translations can readily be performed in conjunction with top-down processing. The major difficulty with this style of parsing is that there are relatively few grammars which satisfy the rather restrictive requirements to admit of top-down parsing (the LL(k) grammars), in comparsion with grammars that can be parsed deterministically bottom-up (the LR(k) grammars). There has been some research along the lines of trying to apply transformations to non-LL(k) grammars in order to convert them into equivalent LL(k) form [1,2,3]; the most successful approach has been that of Rosenkrantz and Lewis [4]. They define class of grammars, the LC(k) grammars, which can be parsed in a mixed hybrid of top-down bottom-up techniques; this class strictly includes the LL(k) grammars, as well as many interesting but non-LL(k) grammars. They then provide a deterministic algorithm for converting any LC(k) grammar into an equivalent LL(k) grammar. This work is a generalization of, and in the same spirit as, the Lewis and Rosenkrantz program. We investigate a new hybrid parsing method, basically bottom-up in character, but which contains a minimal infusion of top-down ideas. We consider the class of grammars which can be parsed by this method, and observe that it strictly includes the class of LC(k) grammars. Then we exhibit an algorithm for deriving from any such grammar an equivalent LL(k) grammar; this derived grammar is also as “useful” as the original one in directing compilation activities, for it can support translations equivalent to those supportable by the original grammar.

REFERENCES

• 1: Stearns, R. E., "Deterministic Top-Down Parsing," Proceedings of Fifth Annual Princeton Conference on Information Sciences and Systems, March 1971, 182-189.
• 2: Foster, J. M., "A Syntax Improving Program," Computer Journal 11, 31-34 (1968)
• 3: Wood, D., "The Normal Form Theorem-Another Proof," Computer Journal 12, 139-147 (1969).
• 4: Rosenkrantz, D. J., and Lewis, P. M., "Deterministic Left Corner Parsing," Conference Record IEEE 11th Annual Symposium on Switching and Automata Theory, October 1970, 139-152.
• 5: Tixier, V., "Recursive Functions of Regular Expressions in Language Analysis," Ph.D. Thesis, Stanford University, Stanford, California, 1967.
• 6: David Bruce Lomet, A Formalization of Transition Diagram Systems, Journal of the ACM (JACM), v.20 n.2, p.235-257, April 1973 [doi>10.1145/321752.321756]
• 7: Knuth, D. E., "On the Translation of Languages from Left to Right," Information and Control 8, 607-639(1965)
• 8: P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
• 9: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 10: Hammer, M., "A New Grammatical Transformation into Deterministic Top-Down Form," MIT Project MAC Technical Report TR-ll9, February 1974

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

General Terms:
Theory