Suffix Languages in LR Parsing
Document Type
Article
Publication Date
1995
Department
Computing
School
Computing Sciences and Computer Engineering
Abstract
For each state in the LR(0) automaton of a context-free grammar, there exists a language consisting of the valid strings that might be parsed from that state. Existing techniques for adding lookahead to an LR(0) automaton do not explicitly consider these ''suffix'' languages. Instead, existing techniques examine prefixes of suffix languages or some other simplification or approximation of them. We define suffix languages and describe an algorithm for computing them. We then show that suffix languages can provide lookahead for inconsistent states of an LR(0) automaton, providing single-symbol lookahead, k-symbol lookahead, and regular lookahead, each only where needed. We submit that suffix languages provide a sound theoretical basis for the study of LR parsing.
Publication Title
International Journal of Computer Mathematics
Volume
55
Issue
41337
First Page
135
Last Page
153
Recommended Citation
Seyfarth, B. R.,
Bermudez, M. E.
(1995). Suffix Languages in LR Parsing. International Journal of Computer Mathematics, 55(41337), 135-153.
Available at: https://aquila.usm.edu/fac_pubs/5862