A practical arbitrary look-ahead LR parsing technique

Abstract

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.