Efficient construction of LR(k) states and tables

ABSTRACT

A new method for building LR(k) states and parsing tables is presented. The method aims at giving a feasible construction of a collection of LR(k) parsing tables, especially when k > 1. for nontrivial grammars. To this purpose, the algorithm first attempts to build a set of normal states for the given grammar, each one associated to a single parsing action in {accept, reduce, shift}. When such an action cannot be uniquely determined, that is, when up to k input symbols have to be examined (inadequacy), further states, belonging to a new type, called look-ahead states, are computed. The action associated with inadequate states is a new parsing action, look. States are built without actual computation of the FIRSTk and EFFk functions; that is, nonterminals are kept in the context string of items composing each state, and their expansion to terminals is deferred until indispensable to solve inadequacy. The aforementioned method is illustrated; then the canonical collection of states and the canonical tables are compared with those obtained from the proposed method. A sufficient condition is stated, by which the size of parsing tables, obtained by applying this new method, is smaller than that of canonical tables. Experimental results show that such a condition is verified by the grammars of several programming languagues and that significant speed is gained by avoiding the computation of the FIRSTk function.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 3: M. Ancona , G. Dodero , V. Gianuzzi, Building collections of LR(K) items with partial expansion of lookahead strings, ACM SIGPLAN Notices, v.17 n.5, p.25-28, May 1982 [doi>10.1145/947923.947926]
• 4: ANCONA, M., FASSINO, C., AND GIANUZZI, V. Optimization of LR(k) reduced tables. Tech. Rep. 39/88, IMA-CNR, Genoa, Italy, 1988.
• 5: ANCONA, M., AND GIANUZZI V. Implementation of reduced LR(k) tables when k > 1. Tech. Rep. 47, IMA-CNR, Genoa, Italy, 1980.
• 6: ANCONA, M., AND GIANUZZI, V. A new method for implementing LR(k) tables. Inf. Process. Lett. 13, 4 and 5 (1981), 171-176.
• 7: Manuel E. Bermudez , Karl M. Schimpf, A practical arbitrary look-ahead LR parsing technique, ACM SIGPLAN Notices, v.21 n.7, p.136-144, July 1986
• 8: CULIK, C., AND COHEN, R. LR-regular grammars-An extension of LR(k) grammars. J. Comput. Syst. Sci. 7 (1973), 66-96.
• 9: 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]
• 10: K Jensen , N Wirth , A B Mickel , J F Miner, Pascal user manual and report; 3rd ed., Springer-Verlag New York, Inc., New York, NY, 1985
• 11: JOHNSON, S.C. YACC--Yet another compiler compiler. Computing Science Tech. Rep. 32, AT&T Bell Laborafories. Murray Hill. N.J.. 1975.
• 12: KNUTtt, D.E. On the translation of languages from left to right. Inf. Control 8 (1965), 607-639.
• 13: MCKEEMAN, W. M., HORNING, J. J., AND WORTMAN, D.B. A Compiler Generator. Prentice- Hall, Englewood Cliffs, N.J., 1974.
• 14: MORGAVI, M. An algorithm to build sets of states and parsing tables for LR(k) grammars lin
• 15: SEITE, B. A YACC extension for LRR grammar parsing. Ph.D. dissertation. INRIA, France, 1986.
• 16: David Spector, Lexing and parsing Modula-2, ACM SIGPLAN Notices, v.18 n.10, October 1983 [doi>10.1145/988175.988181]
• 17: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

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

General Terms:
Algorithms, Experimentation, Languages, Theory, Verification

Keywords:
LR(k) grammars, parsing tables, set of items