• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Generalized LR Parsing Algorithm for Boolean Grammars

Alexander Okhotin, Generalized LR Parsing Algorithm for Boolean Grammars. International Journal of Foundations of Computer Science 17(3), 629–664, 2006.

Abstract:

The generalized LR parsing algorithm for context-free grammars is extended for the case of Boolean grammars, which are a generalization of the context-free grammars with logical connectives added to the formalism of rules. In addition to the standard LR operations, <i>Shift</i> and <i>Reduce</i>, the new algorithm uses a third operation called <i>Invalidate</i>, which reverses a previously made reduction. This operation makes the mathematical justification of the algorithm significantly different from its prototype. On the other hand, the changes in the implementation are not very substantial, and the algorithm still works in time O(n^4).

BibTeX entry:

@ARTICLE{jOkhotin06b,
  title = {Generalized LR Parsing Algorithm for Boolean Grammars},
  author = {Okhotin, Alexander},
  journal = {International Journal of Foundations of Computer Science},
  volume = {17},
  number = {3},
  publisher = {World Scientific Publishing Co},
  pages = {629–664},
  year = {2006},
  keywords = {Boolean grammars, language equations, conjunctive grammars, parsing, LR, bottom-up, shift--reduce},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication