A Practical State Splitting Algorithm for Constructing LR-Parsers

Abstract

A practical algorithm for constructing LR(k) parsers is given. The algorithm works by splitting those states in the LR(O)-machine that give rise to LALR(k)-conflicts. The algorithm takes a conflicting pair of items, say l,J in a state T, and performs a recursive backwards traversal of part of the predecessor tree of T. At each node pairs of items which contribute with lookahead to I and J in T are visited.

During the return from the recursion, states in the predecessor tree that give rise to LALR(k)-conflicts (between I and J in T) which are not LR(k)-conflicts, will be split. This splitting may involve unrolling of loops and separation of loops into several loops.