zbMATH — the first resource for mathematics

A Yacc extension for LRR grammar parsing. (English) Zbl 0627.68070
The algorithm we present here generates finite-state automata for potentially unbounded examination of lookahead and stack in order to try to discriminate the conflicting actions of an LR0 collection. Furthermore, this algorithm can be considered as an overall model to extend the current LR parser generators preserving (i): the valid prefix property and the traditional error recovery routines of the LR parser; (ii): the LALR(1) context on the LR0 collection. The power of acceptance is a subset of Cohen-Culik’s LRR, with acceptation of non-LR(k) grammars, allowing a deterministic bottom-up parsing in linear time when this succeeds.
The special feature of this method, compared to foregoing endeavours, consists in the use of the stack language so that a good deal of LR(k) grammars not accessible by foregoing methods now becomes acceptable. In terms of practicability, the minimization techniques allow one to get very compact automata as illustrated on the output lists. The generation of complementary tables can be done independently of the parser generator, which makes the connection of this complementary module to any LR parser generator quite easy. We also show some orginal results regarding LR automata.

68N20 Theory of compilers and interpreters
68Q45 Formal languages and automata
Full Text: DOI
[1] Aho, A.V.; Ullman, J.D., Optimization of LR(k) parsers, J. comput. system sci., 6, 573-602, (1972) · Zbl 0264.68032
[2] Aho, A.V.; Ullman, J.D., The theory of parsing, translation, and compiling, Vols. 1 and 2, (1972), Prentice-Hall Englewood Cliffs, NJ · Zbl 0264.68032
[3] Aho, A.V.; Ullman, J.D., A technique for speeding up LR(k) parsers, SIAM J. comput., 2, 2, 106-127, (1973) · Zbl 0271.68013
[4] Aho, A.V., Language theory in compiler design, ()
[5] Aho, A.V.; Ullman, J.D., Principles of compiler design, (1977), Addison-Wesley Reading, MA · Zbl 0196.01702
[6] Aho, A.V.; Ullman, J.D.; Sethi, R., Compilers: principles, techniques, and tools, (1985), Addison-Wesley Reading, MA
[7] Alpern, Bowen, M. Chaney, M. Fay, T. Pennello and R. Radin, Translator writing system for the Burroughs B5700, Tech. Rept., Dept. of Information Sciences, UC Santa Cruz.
[8] Anderson, T.; Eve, J.; Horning, J.J., Efficient LR(1) parsers, Acta inform., 2, 12-39, (1973) · Zbl 0235.68009
[9] Baker, T., Extending lookahead for LR parsers, J. comput. system sci., 22, 243-259, (1981) · Zbl 0472.68049
[10] Bermudez, M.E.; Schimpf, K.M., A practical arbitrary look-ahead LR parsing technique, Palo Alto, Proc. SIGPLAN ’86 symp. on compiler construction, 136-144, (June 1986)
[11] Boullier, P., Contribution á la construction automatique d’analyseurs lexicographiques et syntaxiques, ()
[12] Culik, K.; Cohen, R., LR-regular grammars—an extension of LR(k) grammars, J. comput. system sci., 7, 66-96, (1973) · Zbl 0253.68014
[13] Demers, A.J., Elimination of single productions and merging nonterminals symbols of LR(1) grammars, Comput. lang., 1, 105-119, (1975) · Zbl 0362.68102
[14] DeRemer, F.; Penello, T., Efficient computation of LALR(1) look-ahead sets, SIGPLAN notices, 14, 8, 176-187, (1979)
[15] Earley, J., An efficient context-free parsing algorithm, Comm. ACM, 13, 94-102, (1970) · Zbl 0185.43401
[16] Geller, M.M.; Harrison, M.A., On LR(k) grammars and languages, Theoret. comput. sci., 4, 3, 245-276, (1977) · Zbl 0357.68083
[17] Geller, M.M.; Harrison, M.A.; Geller, M.M.; Harrison, M.A., Characteristic parsing, a framework for producing compact deterministic parsers, part II, J. comput. system sci., J. comput. system sci., 14, 3, 318-343, (1977) · Zbl 0363.68092
[18] Harrison, M.A., An introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[19] Heilbrunner, S., A parsing automata approach to LR theory, Theoret. comput sci., 15, 117-157, (1981) · Zbl 0469.68086
[20] Hopcroft, J.; Ullman, J., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, MA · Zbl 0196.01701
[21] Hunt, H.; Szymansky, T.; Ullman, J., On the complexity of LR(k) testing, Comm. ACM, 18, 12, 707-716, (1975) · Zbl 0318.68052
[22] Joliat, M.L., A simple technique for partial elimination of unit productions from LR(k) parsers, IEEE trans. comput., C-27, 763-764, (1976) · Zbl 0331.68046
[23] Knuth, D.E., On the translation of languages from left to right, Inform. and control, 8, 607-639, (1965) · Zbl 0231.68027
[24] Koskemies, K.; Soisalon-Soininen, E., On a method for optimizing LR parsers, Internat. J. comput. math., 7, 287-295, (1979) · Zbl 0418.68067
[25] Kristensen, B.; Madsen, O., Methods for computing LALR(k) lookahead, ACM trans. programm. lang. systems, 3, 1, 60-82, (1981) · Zbl 0454.68100
[26] Lalonde, W.R., On directly constructing LR(k) parsers without chain productions, Conf. record third ACM SIGACT-SIGPLAN symp. on principles of programming languages, 127-133, (1976)
[27] Mickhunas, M.; Lancaster, R.; Schneider, V., Transforming LR(k) grammars to LR(1), SLR(1), and (1,1) BRC grammars, J. ACM, 23, 3, 511-533, (1976) · Zbl 0359.68098
[28] Pager, D., A solution to an open problem by Knuth, Inform. and control, 17, 462-473, (1970) · Zbl 0217.22604
[29] Pager, D., On eliminating unit productions from LR(k) parsers, () · Zbl 0284.68013
[30] Pager, D., Eliminating unit productions from LR parsers, Acta inform., 9, 31-59, (1977) · Zbl 0349.68009
[31] Pager, D., A practical general method for constructing LR(k) parsers, Acta inform., 7, 249-268, (1977) · Zbl 0358.68116
[32] Pager, D., The Lane-tracing algorithm for constructing LR(k) parsers and ways of enhancing its efficiency, Inform. sci., 12, 19-42, (1977) · Zbl 0357.68084
[33] Park, J.C.H.; Choe, K.M.; Chang, C.H., A new analysis of LALR formalisms, Trans. program lang. system, 7, 1, 159-175, (1985) · Zbl 0549.68083
[34] Seité, B., Une extension de yacc, pour analyse des grammaires LRR, qui autorise un examen non borné du contexte droit et de la pile, ()
[35] Soisalon-Soininen, E., Elimination of single production from LR parsers in conjunction with the use of default reductions, Conf. record of the 4th ACM SIGACT-SIGPLAN symp. on principles of programming languages, 183-193, (1977)
[36] Soisalon-Soininen, E., On the space optimizing effect of eliminating single production from LR parsers, Acta inform., 14, 157-174, (1980) · Zbl 0442.68085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.