BRNGLR: a cubic Tomita-style GLR parsing algorithm |
| |
Authors: | Elizabeth Scott Adrian Johnstone Rob Economopoulos |
| |
Affiliation: | (1) Department of Computer Science, Royal Holloway, University of London, Egham, TW20 0EX, Surrey, UK |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|