TY - GEN

T1 - LR parsing for boolean grammars

AU - Okhotin, Alexander

PY - 2005/10/17

Y1 - 2005/10/17

N2 - The generalized LR parsing algorithm for context-free grammars, invented by Tomita in 1986, is extended for the case of Boolean grammars, which are a recently introduced generalization of context-free grammars with logical connectives added to the formalism of rules. In addition to the standard LR operations, Shift and Reduce, the new algorithm uses a third operation called Invalidate, which reverses a previously made reduction; this makes the algorithm considerably different from its prototype, though it can still be made to work in time O(n3).

AB - The generalized LR parsing algorithm for context-free grammars, invented by Tomita in 1986, is extended for the case of Boolean grammars, which are a recently introduced generalization of context-free grammars with logical connectives added to the formalism of rules. In addition to the standard LR operations, Shift and Reduce, the new algorithm uses a third operation called Invalidate, which reverses a previously made reduction; this makes the algorithm considerably different from its prototype, though it can still be made to work in time O(n3).

UR - http://www.scopus.com/inward/record.url?scp=26444539848&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:26444539848

VL - 3572

T3 - Lecture Notes in Computer Science

SP - 362

EP - 373

BT - DLT 2005: Developments in Language Theory

T2 - 9th International Conference on Developments in Language Theory, DLT 2005

Y2 - 4 July 2005 through 8 July 2005

ER -