A preliminary report on generalized LR parsing for Boolean grammars
Alexander Okhotin · 2004
The generalized LR parsing algorithm for context-free grammars, invented by Tomita in 1986, is extended for the case of Boolean grammars – a recently introduced generalization of context-free grammars with logical connectives added to the formalism of rules. A high-level description of the algorithm, an elaborate example of its operation and a suggested implementation are provided. The algorithm has been implemented in a parser generator. However, the proof of the algorithm’s correctness is so far incomplete, hence the preliminary status of this report. 1