LR(0) items and parsing in Compiler Design - Step-by-Step Execution

Concept Flow - LR(0) items and parsing

Start with Grammar

↓

Create Augmented Grammar

↓

Generate LR(0) Items

↓

Build Canonical Collection of LR(0) Items

↓

Construct LR(0) Parsing Table

↓

Parse Input String Using Table

↓

Accept or Reject Input

The process starts with a grammar, then creates LR(0) items, builds a collection of these items, constructs a parsing table, and finally uses it to parse input strings.

Execution Sample

Compiler Design

S' -> .S
S -> .aSb
S -> .

Shows initial LR(0) items with dot positions indicating parsing progress.

Analysis Table

Step	Item Set	Action	Next Item Set	Reason
1	I0: S' -> .S, S -> .aSb, S -> .	Shift 'a'	I1	Dot before 'a', shift to next state
2	I1: S -> a.Sb	Shift 'b'	I2	Dot before 'b', shift to next state
3	I2: S -> aS.b	Reduce by S -> aSb	-	Dot at end, reduce
4	I0: S' -> .S, S -> .aSb, S -> .	Reduce by S -> epsilon	-	Dot at end in S -> . (epsilon), reduce
5	I0: S' -> .S, S -> .aSb, S -> .	Accept	-	Input fully parsed, accept
6	-	-	-	Parsing ends

💡 Parsing ends when input is accepted or no valid action is found.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Current Item Set	I0	I1	I2	-	I0	-
Input Position	0	1 (after 'a')	2 (after 'b')	3	3	3
Stack	[]	[I0, 'a', I1]	[I0, 'a', I1, 'b', I2]	[I0, 'a', I1]	[I0]	[I0]

Key Insights - 3 Insights

Why do we add a dot at different positions in the production?

The dot shows how much of the production has been seen. For example, in step 1, dot before 'a' means we expect to read 'a' next (see execution_table row 1).

What does it mean when the dot is at the end of a production?

It means the production is complete and we can reduce (see execution_table rows 3 and 4).

Why do we create an augmented grammar with S' -> S?

To have a unique start production that helps detect when parsing is done (accept state), as shown in the first item set I0.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What action is taken when the dot reaches the end of the production?

A Accept the input

B Shift the next input symbol

C Reduce by the completed production

D Go back to the start

💡 Hint

Check the 'Action' column at Step 3 in execution_table where dot is at the end.

At which step does the parser accept the input string?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look for the 'Accept' action in the execution_table.

If the input symbol 'a' was missing at the start, what would happen at Step 1?

A Shift 'a' anyway

B No valid action, parsing error

C Reduce immediately

D Accept input

💡 Hint

Refer to Step 1 action requiring 'a' to shift; without it, no action is possible.

Concept Snapshot

LR(0) parsing uses items with a dot to track progress in productions.
Start with augmented grammar S' -> S.
Build item sets by moving the dot over symbols.
Create parsing table from item sets.
Use table to shift, reduce, or accept input.
Parsing ends when input is accepted or error occurs.

Full Transcript

LR(0) parsing is a method to analyze if a string belongs to a grammar. We start by adding a new start rule to the grammar. Then, we create LR(0) items which are productions with a dot showing how much we have read. We group these items into sets and build a parsing table. The parser reads the input string, shifting symbols or reducing by productions based on the table. When the input is fully matched, the parser accepts it. If no valid action is found, parsing fails.

Practice

1. What does an LR(0) item represent in compiler design?

easy

A. A syntax error in the source code

B. A token recognized by the lexer

C. A grammar rule with a dot showing how much has been read

D. A semantic action to be performed

Solution

1. Step 1: Understand LR(0) item definition

   An LR(0) item is a grammar production with a dot indicating the position up to which input has been processed.

2. Step 2: Differentiate from other concepts

   Tokens are lexer outputs, errors are problems, and semantic actions are separate; only the dot notation fits LR(0) items.

3. Final Answer:

   A grammar rule with a dot showing how much has been read -> Option C

4. Quick Check:

   LR(0) item = grammar rule + dot position [OK]

Hint: LR(0) items always show a dot in grammar rules [OK]

Common Mistakes:

• Confusing LR(0) items with tokens
• Thinking LR(0) items are errors
• Mixing semantic actions with LR(0) items

2. Which of the following is the correct way to write an LR(0) item for the production A -> αβ where the dot is before β?

easy

A. A -> α · β

B. A -> · αβ

C. A -> αβ ·

D. A -> β · α

Solution

1. Step 1: Understand dot placement in LR(0) items

   The dot shows how much of the production has been seen. Before β means after α, so dot goes after α.

2. Step 2: Match the correct notation

   A -> α · β places the dot correctly as A -> α · β. Others place dot incorrectly.

3. Final Answer:

   A -> α · β -> Option A

4. Quick Check:

   Dot before β means after α [OK]

Hint: Dot shows position; before β means after α [OK]

Common Mistakes:

• Placing dot at start when it should be after α
• Putting dot at end incorrectly
• Swapping α and β positions

3. Given the grammar rule S -> a A b, what is the LR(0) item after reading a?

medium

A. S -> · a A b

B. S -> a · A b

C. S -> a A · b

D. S -> a A b ·

Solution

1. Step 1: Identify the position of the dot after reading 'a'

   Reading 'a' means the dot moves past 'a' in the production.

2. Step 2: Place the dot correctly

   So the item becomes S -> a · A b, showing 'a' is read and next is 'A'.

3. Final Answer:

   S -> a · A b -> Option B

4. Quick Check:

   Dot moves past read symbols [OK]

Hint: Dot moves right after reading a symbol [OK]

Common Mistakes:

• Keeping dot before 'a' after reading it
• Moving dot too far past unread symbols
• Confusing order of symbols

4. Identify the error in this LR(0) item: B -> α β · γ

medium

A. Dot placement is correct

B. Dot must be at the start or end only

C. Dot should be before γ, not after β

D. Dot cannot be placed between two symbols

Solution

1. Step 1: Understand valid dot positions in LR(0) items

   The dot can appear before any symbol or at the end of the production.

2. Step 2: Check the given item

   In B -> α β · γ, the dot is before γ, which is valid.

3. Final Answer:

   Dot placement is correct -> Option A

4. Quick Check:

   Dot can be anywhere before or after symbols [OK]

Hint: Dot can be before any symbol or at end [OK]

Common Mistakes:

• Thinking dot can't be between symbols
• Believing dot must be only at start or end
• Misreading dot position

5. In LR(0) parsing, what action should be taken when the parser encounters an LR(0) item with the dot at the end of a production, like A -> α ·?

hard

A. Report a syntax error

B. Shift the next input symbol

C. Accept the input string

D. Reduce by the production A -> α

Solution

1. Step 1: Understand dot at end meaning

   When the dot is at the end, it means the entire production has been recognized.

2. Step 2: Determine parser action

   The parser should reduce the recognized symbols to the non-terminal on the left side of the production.

3. Final Answer:

   Reduce by the production A -> α -> Option D

4. Quick Check:

   Dot at end means reduce [OK]

Hint: Dot at end means reduce by that production [OK]

Common Mistakes:

• Trying to shift instead of reduce
• Confusing accept with reduce
• Reporting error incorrectly