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

The Lane Table Method Of Constructing LR(1) Parsers

File Size Format  
report.pdf 12.8 MB Adobe PDF View/Open

Item Summary

Title:The Lane Table Method Of Constructing LR(1) Parsers
Authors:Pager, D.
Date Issued:01 Jun 2009
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

Please email if you need this content in ADA-compliant format.

This item is licensed under a Creative Commons License Creative Commons