Abstract
This paper introduces a mechanism for combining unbounded lookahead exploration with linear time complexity in a deterministic parser. The idea is to use a resolve parsing action in place of the classical reduce. The construction of shift-resolve parsers is presented as a two-step algorithm, from the grammar to a finite nondeterministic automaton, and from this automaton to the deterministic parser. Grammar classes comparisons are provided.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Donnely, C., Stallman, R.: Bison, The YACC-compatible Parser Generator. The Free Software Foundation (2002)
Baker, T.P.: Extending lookahead for LR parsers. Journal of Computer and System Sciences 22(2), 243–259 (1981)
Bermudez, M.E., Schimpf, K.M.: Practical arbitrary lookahead LR parsing. Journal of Computer and System Sciences 41(2), 230–250 (1990)
Farré, J., Fortes Gálvez, J.: A bounded graph-connect construction for LR-regular parsers. In: Wilhelm, R. (ed.) CC 2001. LNCS, vol. 2027, pp. 244–258. Springer, Heidelberg (2001)
Szymanski, T.G., Williams, J.H.: Noncanonical extensions of bottom-up parsing techniques. SIAM Journal on Computing 5(2), 231–250 (1976)
Tai, K.C.: Noncanonical SLR(1) grammars. ACM Transactions on Programming Languages and Systems 1(2), 295–320 (1979)
Schmitz, S.: Noncanonical LALR(1) parsing. In: Dang, Z., Ibarra, O.H. (eds.) DLT 2006. LNCS, vol. 4036, pp. 95–107. Springer, Heidelberg (2006)
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling. Parsing of Series in Automatic Computation, vol. I. Prentice Hall, Englewood Cliffs (1972)
Tomita, M.: Efficient Parsing for Natural Language. Kluwer Academic Publishers, Dordrecht (1986)
Čulik, K., Cohen, R.: LR-Regular grammars—an extension of LR(k) grammars. Journal of Computer and System Sciences 7, 66–96 (1973)
Farré, J., Fortes Gálvez, J.: Bounded-connect noncanonical discriminating-reverse parsers. Theoretical Computer Science 313(1), 73–91 (2004)
Fortes Gálvez, J.: A Discriminating Reverse Approach to LR(k) Parsing. PhD thesis, Universidad de Las Palmas de Gran Canaria and Université de Nice-Sophia Antipolis (1998)
Grune, D., Jacobs, C.J.H.: Parsing Techniques: A Practical Guide. Ellis Horwood Limited (1990)
Hunt III, H.B., Szymanski, T.G., Ullman, J.D.: On the complexity of LR(k) testing. Communications of the ACM 18(12), 707–716 (1975)
Heilbrunner, S.: A parsing automata approach to LR theory. Theoretical Computer Science 15(2), 117–157 (1981)
Schöbel-Theuer, T.: Towards a unifying theory of context-free parsing. In: Pighizzini, G., San Pietro, P. (eds.) Proceedings ASMICS Workshop on Parsing Theory. Technical Report 126-1994, Università di Milano, pp. 89–100 (1994)
Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL 1977, pp. 238–252. ACM Press, New York (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gálvez, J.F., Schmitz, S., Farré, J. (2006). Shift-Resolve Parsing: Simple, Unbounded Lookahead, Linear Time. In: Ibarra, O.H., Yen, HC. (eds) Implementation and Application of Automata. CIAA 2006. Lecture Notes in Computer Science, vol 4094. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11812128_24
Download citation
DOI: https://doi.org/10.1007/11812128_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37213-4
Online ISBN: 978-3-540-37214-1
eBook Packages: Computer ScienceComputer Science (R0)