Title

Suffix Languages in LR Parsing

Document Type

Article

Publication Date

1995

Department

Computing

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