Ambiguity in grammars in Compiler Design - Step-by-Step Execution

Concept Flow - Ambiguity in grammars

Start with Grammar

↓

Parse Input String

↓

Generate Parse Trees

↓

Check Number of Parse Trees

↓

One

↓

Unambiguous

The process starts with a grammar and input string, then generates parse trees. If there is more than one valid parse tree for the same input, the grammar is ambiguous.

Execution Sample

Compiler Design

Grammar:
S -> S + S | a
Input: a + a + a

This grammar can generate multiple parse trees for the input 'a + a + a', showing ambiguity.

Analysis Table

Step	Input Processed	Parse Tree Count	Action	Result
1	a	1	Parse 'a' as S	One parse tree for 'a'
2	a + a	1	Parse 'a + a' as S + S	One parse tree: (a + a)
3	a + a + a	2	Parse 'a + a + a' as (S + S) + S or S + (S + S)	Two different parse trees for full input
4	Check parse trees	2	More than one parse tree found	Grammar is ambiguous

💡 Parsing stops because multiple parse trees exist for the input, indicating ambiguity.

State Tracker

Variable	Start	After 1	After 2	After 3	Final
Parse Tree Count	0	1	1	2	2

Key Insights - 2 Insights

Why does the parse tree count increase at step 3?

At step 3, the input 'a + a + a' can be parsed in two ways due to the recursive rule S -> S + S, creating two parse trees as shown in execution_table row 3.

Does having multiple parse trees mean the input is invalid?

No, multiple parse trees mean the grammar is ambiguous for that input, not that the input is invalid. This is shown in execution_table row 4.

Visual Quiz - 3 Questions

According to the execution_table, how many parse trees exist after processing 'a + a'?

A 3

B 1

C 2

D 0

💡 Hint

Look at execution_table row 2 under 'Parse Tree Count' column.

At which step does the grammar get identified as ambiguous?

A Step 1

B Step 2

C Step 4

D Step 3

💡 Hint

Check execution_table row 4 where the action notes multiple parse trees found.

If the grammar had only one parse tree at every step, what would the 'Parse Tree Count' be in variable_tracker's final column?

A 1

B 0

C 2

D Multiple

💡 Hint

Refer to variable_tracker row for 'Parse Tree Count' and imagine only one parse tree at each step.

Concept Snapshot

Ambiguity in grammars means an input string can have multiple valid parse trees.
Check parse trees generated for input; if more than one, grammar is ambiguous.
Ambiguity causes confusion in parsing and compiler design.
Example: S -> S + S | a with input 'a + a + a' has multiple parse trees.
Avoid ambiguity for clear, deterministic parsing.

Full Transcript

Ambiguity in grammars happens when a single input string can be parsed in more than one way, producing multiple parse trees. Starting with a grammar and an input, we try to parse the input. If we find more than one parse tree, the grammar is ambiguous. For example, the grammar with rules S -> S + S or S -> a can parse 'a + a + a' in two different ways. This is shown step-by-step in the execution table where the parse tree count increases and finally shows ambiguity. Understanding this helps in designing clear grammars for compilers.