Skip to content

RNGLR: Right nulled GLR

The right nulled generalized LR parsing algorithm is a new generalization of LR parsing which provides an elegant correction to, and extension of, Tomita’s GLR methods whereby we extend the notion of a reduction in a shift-reduce parser to include right nulled items. The result is a parsing technique which runs in linear time on LR(1) grammars and whose performance degrades gracefully to a polynomial bound in the presence of non LR(1) rules. Compared to other GLR-based techniques, our algorithm is simpler and faster.

Elizabeth Scott and Adrian Johnstone. Right nulled GLR parsers, 2006