zbMATH — the first resource for mathematics

Shift-resolve parsing: simple, unbounded lookahead, linear time. (English) Zbl 1160.68339
Ibarra, Oscar H. (ed.) et al., Implementation and application of automata. 11th international conference, CIAA 2006, Taipei, Taiwan, August 21–23, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-37213-4/pbk). Lecture Notes in Computer Science 4094, 253-264 (2006).
Summary: 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.
For the entire collection see [Zbl 1113.68007].

68N20 Theory of compilers and interpreters
68Q45 Formal languages and automata
Full Text: DOI