Please use this identifier to cite or link to this item:
The Lane Table Method Of Constructing LR(1) Parsers
|Title:||The Lane Table Method Of Constructing LR(1) Parsers|
|Issue Date:||01 Jun 2009|
|Abstract:||The first practical application of the LR algorithm was by  for the LALR(1) subset of LR(1) grammars. In  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  for determining whether or not states may be combined was that of weak compatibility, as defined in . In this paper we describe an alternative method for determining whether states can be combined. According to testing by  this method requires less computation. It is also more efficient. when extending the method from LR(1) to LR(k) parsing as described in  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.