# BRNGLR: Binary Right Nulled GLR

Tomita-style generalised

`LR`

(`GLR`

) algorithms extend the standard`LR`

algorithm to non-deterministic grammars by performing all possible choices of action. Cubic complexity is achieved if all rules are of length at most two. In this paper we shall show how to achieve cubic time bounds for all grammars by binarising the search performed whilst executing reduce actions in a`GLR`

-style parser. We call the resulting algorithm Binary Right Nulled`GLR`

(`BRNGLR`

) parsing. The binarisation process generates run-time behaviour that is related to that shown by a parser which pre-processes its grammar or parse table into a binary form, but without the increase in table size and with a reduced run-time space overhead.BRNGLR parsers have worst-case cubic run time on all grammars, linear behaviour on`LR(1)`

grammars and produce, in worst-case cubic time, a cubic size binary SPPF representation of all the derivations of a given sentence.