Scribd
Upload
5 views10 pages

Understanding Viable Prefixes in LR Parsing

The document discusses the concept of viable prefixes in LR parsing, emphasizing that stack contents must be prefixes of right-sentential forms and that handles should be reduced before shifting. It outlines different types of LR parsers, including Simple LR (SLR), Canonical LR (CLR), and LookAhead LR (LALR), highlighting their characteristics and advantages. Additionally, it explains the role of LR(1) items in managing reductions based on lookahead symbols to avoid invalid reductions.

Uploaded by

Abhilasha Goyal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views10 pages

Understanding Viable Prefixes in LR Parsing

The document discusses the concept of viable prefixes in LR parsing, emphasizing that stack contents must be prefixes of right-sentential forms and that handles should be reduced before shifting. It outlines different types of LR parsers, including Simple LR (SLR), Canonical LR (CLR), and LookAhead LR (LALR), highlighting their characteristics and advantages. Additionally, it explains the role of LR(1) items in managing reductions based on lookahead symbols to avoid invalid reductions.

Uploaded by

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

More powerful LR parsers

Viable Prefix
- The stack contents must be a prefix of a right-sentential form.

- If the stack holds α and the rest of the input is x, then a sequence of reductions will
take αx to S. In terms of derivations.

S->*rmαx

- However, Not all prefixes of right-sentential forms can appear on the stack. However,
if a handle is recognized, it should be reduced before shift operation for next input
symbol. Consider the example

- The stack will hold (, (E, and (E), but it must not hold (E)*, since (E) is a handle,
which the parser must reduce to F before shifting *.

- The prefixes of right sentential forms that can appear on the stack of a shift-reduce
parser are called viable prefixes.

- By this definition, it is always possible to add terminal symbols to the end of a viable
prefix to obtain a right-sentential form.
Viable Prefix
- SLR parsing is based on the fact that LR(0) automata recognizes the viable prifixes.

- We say an item A-ß1.ß2 is valid for a viable prefix αßß1 if there is a derivation S’ => αßAw
=> αßß1ß2w .

- An item can be valid for many viable prefix.


LR Parser – Shift Reduce Parsers
- Simple LR (SLR): Uses LR(0) automata with a minimum number of items and
states

- Cannonical LR (CLR): The canonical-LR or just LR method, which makes full


use of the lookahead symbol(s), typically one symbol of the input for LR(1). This
method uses a large set of items, called the LR(1) items.

- LookAhead LR (LALR):
- Uses LR(0) sets of items, and has many fewer states than typical parsers based
on the LR(1) items.
- Carefully introduce lookaheads into the LR(0) items,

- we can handle many more grammars with the LALR method than with the
SLR method, and build parsing tables that are no bigger than the SLR tables.
Cannonical LR(1) Items
- SLR(1) calls for reduction if state i is on top of stack, input symbol is a is in Follow(A), while
the state i has an item [A=>α.]

- In some situations, however, when state i appears on top of the stack, the viable prefix ßα on the α on the
stack is such that ßα on the A cannot be followed by a in any right-sentential form. Thus, the reduction by
item A => α should be invalid on input a. While the handle might be valid for other viable prefix.

- Indicating which input symbol can follow a handle α with the item can overcome the invalid
reduction problem.

- LR(1) Item: [A ->α., a] calls for a reduction by A => α only if the next input symbol is a.

- The set of such a's will always be a subset of FOLLOW(A).


Clouser and GoTo for LR(1) items
Clouser and GoTo for LR(1) items
LR(1) Automata
Clouser and GoTo for LR(1) items

S’ -> S
S -> CC
C -> cC | d

Automata using LR(1) items


Clouser and GoTo for LR(1) items

You might also like