Suffix Languages in LR Parsing

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 \u27\u27suffix\u27\u27 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