Lecture Notes in Computer Science, 2001, Volume 2027/2001, 244-258, DOI: 10.1007/3-540-45306-7_17

A Bounded Graph-Connect Construction for LR-regular Parsers

Jacques Farré and José Fortes Gálvez

View Related Documents

Abstract

Parser generation tools currently used for computer language analysis rely on user wisdom in order to resolve grammar conflicts. Here practical LR(0)-based parser generation is introduced, with automatic conflict resolution by potentially-unbounded lookahead exploration. The underlying LR(0)-automaton item dependence graph is used for lookahead DFA construction. A bounded graph-connect technique overcomes the difficulties of previous approaches with empty rules, and compact coding allows to precisely resume right-hand contexts. Resulting parsers are deterministic and linear, and accept a large class of LR-regular grammars including LALR(k). Their construction is formally introduced, shown to be decidable, and illustrated by a detailed example.

Fulltext Preview

Image of the first page of the fulltext document