Canonical LR parser: Difference between revisions

Revision as of 12:48, 14 October 2012

Revision as of 03:27, 21 October 2012

Line 89:

The dot '•' denotes the marker of the current parsing position within this rule. The expected lookahead terminal to apply this rule is noted after the comma. The '$' sign is used to denote 'end of input' is expected, as is the case for the starting rule.

This is not the complete item set 0, though. Each item set must be 'closed', which means all production rules for each terminalnonterminal following a '•' have to be recursively included into the item set until all of those terminalsnonterminals are dealt with. The resulting item set is called the closure of the item set we began with.

For LR(1) for each production rule an item has to be included for each possible lookahead terminal following the rule. For more complex languages this usually results in very large item sets, which is the reason for the large memory requirements of LR(1) parsers.