Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

A Practical State Splitting Algorithm for Constructing LR-Parsers

1984; Volume: 9; Issue: 115 Linguagem: Inglês

10.7146/dpb.v9i115.6533

ISSN

2245-9316

Autores

Bent Bruun Kristensen, Ole Lehrmann Madsen,

Tópico(s)

Semantic Web and Ontologies

Resumo

<p>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.</p><p>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.</p>

Referência(s)