Scribd
Upload
22 views4 pages

Advanced LR Parsing Techniques

There are two main methods for LR parsing: the Canonical-LR or LR method which uses large LR(1) item sets and full lookahead, and the Lookahead-LR or LALR method which is based on LR(0) items but introduces limited lookahead. The LALR method handles more grammars than SLR parsing and is commonly used in practice due to requiring fewer parser states than the Canonical-LR method. An example Canonical-LR item set is provided for a simple grammar involving addition and parentheses.

Uploaded by

Marlon Nacinopa de Vera
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
22 views4 pages

Advanced LR Parsing Techniques

There are two main methods for LR parsing: the Canonical-LR or LR method which uses large LR(1) item sets and full lookahead, and the Lookahead-LR or LALR method which is based on LR(0) items but introduces limited lookahead. The LALR method handles more grammars than SLR parsing and is commonly used in practice due to requiring fewer parser states than the Canonical-LR method. An example Canonical-LR item set is provided for a simple grammar involving addition and parentheses.

Uploaded by

Marlon Nacinopa de Vera
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

MORE POWERFUL

LR PARSERS
CA NONICAL LR || LOOKA HEAD LR

2 DIFFERENT METHODS
1. Canonical-LR or LR Method
Full use of lookahead symbols
Uses large set of items called LR(1) items

2. Lookahead-LR or LALR Method


Based on LR(0) set of items
Fewer states than typical parsers based on LR(1) items
Carefully introduce lookaheads into LR(0) items to handle
many more grammars with this method than with SLR
method
Method of choice in most situations

CANONICAL LR(1) ITEMS


Example: Given the ff. production rules

S
E
E
T
T
T

E
T
(E)
n
+T
T+n

Item Set
Item Set 0: [S E, $]
[ ] denotes the marker of the current parsing position within
the rule.
[ , ] the expected lookahead terminal is noted after the comma
[ $ ] used to denote the end of input is expected.

You might also like