Deterministic parsing of ambiguous grammars

ABSTRACT

Methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions are considered. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. It is shown how efficient LR and LL parsers can be constructed directly from certain classes of these specifications.

REFERENCES

• 1: A. V. Aho , S. C. Johnson, LR Parsing, ACM Computing Surveys (CSUR), v.6 n.2, p.99-124, June 1974 [doi>10.1145/356628.356629]
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Aho, A. V. and Ullman, J. D. A technique for speeding up LR (k) parsers. SlAM J. Computing 2, 2 (June 1972), 106-127.
• 4: Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
• 5: Demers, A. J. Elimination of single productions and merging nonterminal symbols of LR (1) grammars. J. Computer Languages l, 2 (April 1975).
• 6: Demers, A. J. Skeletal LR parsing. IEEE Conf. Record of 15th Annual Symposium on Switching and Automata Theory, 1974, pp. 185-198.
• 7: Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971 [doi>10.1145/362619.362625]
• 8: de Bakker, J. W. and Scott, D. A theory of programs. Unpublished.
• 9: Earley, J. Ambiguity and precedence in syntax description. Tech Rep. 13, Dep. Computer Science, U. of California, Berkeley, 1973.
• 10: E1 Djabri, N. Extending the LR parsing technique to some non- LR grammars. TR 121, Computer Science Lab., Dep. Electr. Eng., Princeton U., Princeton, N.J., 1973.
• 11: Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
• 12: Michael J. Fischer, Some properties of precedence languages, Proceedings of the first annual ACM symposium on Theory of computing, p.181-190, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805432]
• 13: Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
• 14: Friedman, E. P. The inclusion problem for simple machines. Proc. Eighth Annual Princeton Conference on Information Sciences and Systems, 1974, pp. 173-177.
• 15: Ginsburg, S. and Spaniel E. H. Control sets on grammars. Mathematical Systems Theory 2, 2 (1968), 159-178.
• 16: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 17: Joliat, M. L. Practical minimization of LR(k) parser tables. Proc. IFIP Congress 1974, pp. 376-380.
• 18: Knuth, D. E. Top-down syntax analysis. Acta Informatica 1, 2 (1971), 79-110.
• 19: Brian W. Kernighan , Lorinda L. Cherry, A system for typesetting mathematics, Communications of the ACM, v.18 n.3, p.151-157, March 1975 [doi>10.1145/360680.360684]
• 20: Korenjak, A. J. and Hopcroft, J. E. Simple deterministic languages. IEEE Conf. Record of 7th Annual Symposium on Switching and Automata Theory, 1966, pp. 36-46.
• 21: Lewis, P. M. and Rosenkrantz, D. J. An Algol compiler designed using automata theory. Proc. Symposium on Computers and Automata, Polytechnic Institute of Brooklyn, N.Y., 1971, pp. 75-88.
• 22: Lewis, P. M., Rosenkrantz, D. J., and Stearns, R. E. Attributed translations. J. Computer and System Sciences 9, 3 (Dec. 1974), 279- 307.
• 23: 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]
• 24: Zohar Manna , Stephen Ness , Jean Vuillemin, Inductive methods for proving properties of programs, Proceedings of ACM conference on Proving assertions about programs, p.27-50, January 06-07, 1972, Las Cruces, New Mexico, United States
• 25: McKeeman, W. M., Homing, J. J., and Wortman, D. B. A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J., 1970.
• 26: M. D. Mickunas , V. B. Schneider, A parser-generating system for constructing compressed compilers, Communications of the ACM, v.16 n.11, p.669-676, Nov. 1973 [doi>10.1145/355611.362536]
• 27: Pager, D. On eliminating unit productions from LR(k) parsers. TR, Information Sciences Program, U. of Hawaii, Honolulu, Hawaii, 1974.
• 28: Rosenkrantz, D. J. and Stearns, R. E. Properties of deterministic top-down grammars. Inf. Control 14, 5 (1969), 226-256.
• 29: Stearns, R. E. Deterministic top-down parsing. Proc. Fifth Annual Princeton Conf. on Information Sciences and Systems, 1971, pp. 182-188.
• 30: Wood, D. The theory of left factored languages. Computer J. 12, 4 (1969), 349-356 and 13, 1 (1970), 55-62.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing; Grammar types (e.g., context-free, context-sensitive)

General Terms:
Design, Languages, Performance, Theory

Keywords:
LL parsing, LR parsing, ambiguous grammars, parser generation, programming language specification, syntax analysis, translator writing systems