Ambiguity in grammars in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean when a grammar is ambiguous?

A grammar is ambiguous if there is at least one string that can be generated in more than one way, meaning it has more than one distinct parse tree or derivation.

beginner

Why is ambiguity in grammars a problem in compiler design?

Ambiguity causes confusion in understanding the structure of code, making it hard for compilers to decide which meaning or parse tree to use, leading to incorrect program interpretation.

intermediate

Give a simple example of an ambiguous grammar.

The grammar with rules: E → E + E | E * E | id is ambiguous because the expression 'id + id * id' can be parsed in two different ways, changing the order of operations.

beginner

What is a parse tree and how does it relate to ambiguity?

A parse tree shows how a string is derived from a grammar. Ambiguity means there is more than one valid parse tree for the same string.

intermediate

How can ambiguity in grammars be resolved?

Ambiguity can be resolved by rewriting the grammar to remove multiple interpretations, often by adding precedence rules or using unambiguous grammar forms.

What does ambiguity in a grammar mean?

A A string can have multiple parse trees

B Grammar has syntax errors

C Grammar cannot generate any string

D Grammar has only one production rule

Ambiguity means a string can be generated in more than one way, resulting in multiple parse trees.

Which of the following is a sign of an ambiguous grammar?

A Multiple parse trees for the same string

B No parse tree for any string

C Only one production rule

D Grammar is context-free

Ambiguous grammars allow multiple parse trees for the same string.

Why is ambiguity bad for compilers?

A It reduces code size

B It makes code run faster

C It causes confusion in interpreting code

D It helps optimize code

Ambiguity makes it unclear how to interpret code, causing errors in compilation.

Which expression shows ambiguity in the grammar E → E + E | E * E | id?

A id

B id + id

C id * id

D id + id * id

The expression 'id + id * id' can be parsed in two ways, showing ambiguity.

How can ambiguity be removed from a grammar?

A Remove all production rules

B Rewrite grammar with precedence rules

C Add more ambiguous rules

D Ignore ambiguity

Adding precedence rules or rewriting the grammar helps remove ambiguity.

Explain what ambiguity in grammars means and why it matters in compiler design.

Think about how one string can be understood in different ways.

Describe a simple example of an ambiguous grammar and how you might fix it.

Consider arithmetic expressions with + and * operators.