Empirical comparison of LR(k) and precedence parsers

ABSTRACT

Knuth's LR(k) algorithm provides a more general basis for the syntactic portion of compilers than does precedence analysis. We have conducted experiments to determine, for practical grammars, how much this extra generality costs in efficiency. The results indicate that the extra generality of the LR(k) approach may often be accompanied by a reduction in table size and an increase in parsing speed.

REFERENCES

• 1: DeRemer, F. L., "Practical Translators for LR(k) Languages", Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Mass., August, 1969.
• 2: 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]
• 3: 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]
• 4: Robert W. Floyd, Bounded context syntactic analysis, Communications of the ACM, v.7 n.2, p.62-67, Feb. 1964 [doi>10.1145/363921.363927]
• 5: Ichbiah, J. D., private communication, July 1970.
• 6: Knuth, D. E., "On the Translation of Languages from Left to Right", <u>Information and Control 8</u> (October 1965).
• 7: A. J. Korenjak, A practical method for constructing LR (k) processors, Communications of the ACM, v.12 n.11, p.613-623, Nov. 1969 [doi>10.1145/363269.363281]
• 8: McKeeman, W. M., J. J. Horning, E. C. Nelson and D. B. Wortman, "The XPL Compiler Generator System", <u>AFIPS Conference Proceedings</u> 33 (1968 FJCC).
• 9: McKeeman, W. M., J. J. Horning, and D. B. Wortman, <u>A Compiler Generator</u>, Prentice-Hall, 1970.
• 10: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]