The Lane Table Method Of Constructing LR(1) Parsers

dc.contributor.author Pager, D. en_US
dc.date.accessioned 2014-06-06T01:31:48Z
dc.date.available 2014-06-06T01:31:48Z
dc.date.issued 2009-06-01 en_US
dc.description.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. en_US
dc.identifier.uri http://hdl.handle.net/10125/33112
dc.language.iso en-US en_US
dc.relation.ispartofseries ICS2009-06-02 en_US
dc.rights CC0 1.0 Universal
dc.rights.uri http://creativecommons.org/publicdomain/zero/1.0/
dc.title The Lane Table Method Of Constructing LR(1) Parsers en_US
dc.type Report en_US
dc.type.dcmi Text en_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
report.pdf
Size:
12.5 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.62 KB
Format:
Item-specific license agreed upon to submission
Description: