Please use this identifier to cite or link to this item:

The Lane Table Method Of Constructing LR(1) Parsers

File SizeFormat 
report.pdf12.8 MBAdobe PDFView/Open

Item Summary

Title: The Lane Table Method Of Constructing LR(1) Parsers
Authors: Pager, D.
Issue Date: 01 Jun 2009
Series/Report no.: ICS2009-06-02
Abstract: The first practical application of the LR algorithm was by [1] for the LALR(1) subset of LR(1) grammars. In [2] an efficient method of producing an LR(1) parser for all LR(1) grammars was described which involves resolving conflicts at states of the LR(0) parsing machine, employing two phases. In Phase 1 the contexts of the productions involved in conflicts are evaluated by a process described there called “lane tracing”. If conflicts cannot be resolved by these means, then in Phase 2 the parts of the machine involved in lane tracing are regenerated, avoiding the combination of states that potentially lead to conflicts. Other works along the same lines include [4, 5]. The criterion employed in [2] for determining whether or not states may be combined was that of weak compatibility, as defined in [3]. In this paper we describe an alternative method for determining whether states can be combined. According to testing by [6] this method requires less computation. It is also more efficient. when extending the method from LR(1) to LR(k) parsing as described in [7] where very large grammars may be used for the purposes of natural language translation. Taken together with Phase 1, this new method of Phase 2 will, as before, produce a conflict-free LR(1) parser for all LR(1) grammars.
Rights: CC0 1.0 Universal
Appears in Collections:Technical Reports

Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.