Methods for Computing LALR(k) Lookahead

Abstract

Methods for constructing LALR(k) parsers are discussed. Algorithms for computing LALR(k)-lookahead are presented together with the necessary theory to prove their correctness. Firstly a special algorithm for the LALR(1) case is presented. Secondly a general LALR(k)-algorithm with k >= 1 is presented. Given an item and a state the algorithms compute their corresponding LALR-lookahead during a recursive traversal of the LR(0)-machine. Finally the LALR(k)-algorithm is generalised to compute LALR(k)-lookahead for all items and states visited during the recursive traversal performed by the former algorithms.