A practical arbitrary look-ahead LR parsing technique

• Main Authors: Bermudez, Manuel E., Schimpf, Karl M.
• Format: Conference Proceeding
• Language: English
• Subjects: Applied computing > Computers in other domains > Personal computers and PC applications; Human-centered computing > Human computer interaction (HCI); Social and professional topics > Professional topics > Management of computing and information systems > Software management; Software and its engineering > Software creation and management; Software and its engineering > Software creation and management > Designing software; Software and its engineering > Software creation and management > Designing software > Requirements analysis; Software and its engineering > Software notations and tools > Compilers; Software and its engineering > Software notations and tools > Compilers > Parsers; Theory of computation > Semantics and reasoning > Program reasoning > Parsing
• ISSN: 0362-1340
• DOI: 10.1145/12276.13325

We present a practical technique that provides an LR (0) parser with either fixed or arbitrary look-ahead. The construction algorithm is based on certain paths in the LR (0) state diagram, which must be restricted to a maximum length m. The technique determines the amount of look-ahead required, and the user is spared the task of guessing it. Instead, the user provides m. In situations where single symbol look-ahead is sufficient, the corresponding grammar class (called LAR (m )) is identical to the NQLALR (1) class. For practical grammars that require arbitrary look-ahead, the storage requirements typically do not exceed an amount linear in the size of the corresponding LR (0) parser. The technique is shown to work for a practical programming language grammar, and has been used to solve particular cases of the PL/1 keyword problem.