Open AccessA Practical State Splitting Algorithm for Constructing LR-Parsers
Author(s) -
Bent Bruun Kristensen,
Ole Lehrmann Madsen
Publication year - 1984
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v9i115.6533
Subject(s) - tree traversal , computer science , recursion (computer science) , algorithm , parsing , tree (set theory) , state (computer science) , node (physics) , combinatorics , discrete mathematics , mathematics , physics , programming language , quantum mechanics
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.