Ambiguity in grammars in Compiler Design - Mini Project: Build & Apply

Understanding Ambiguity in Grammars

📖 Scenario: You are learning about how programming languages are designed. One important concept is whether a grammar is ambiguous or not. Ambiguity means a sentence can be understood in more than one way, which can cause confusion for a compiler.Imagine you are designing a simple grammar for arithmetic expressions. You want to check if the grammar is ambiguous by looking at how expressions can be parsed.

🎯 Goal: Build a simple grammar using Python dictionaries to represent production rules. Then, identify if the grammar is ambiguous by checking if a sentence can have multiple parse trees.

📋 What You'll Learn

Create a dictionary called grammar with specific production rules

Add a variable called test_sentence with the exact string to test

Write a function called is_ambiguous that checks if the sentence has multiple parse trees

Add a final variable ambiguous_result that stores the result of the ambiguity check

💡 Why This Matters

🌍 Real World

Understanding ambiguity helps language designers create clear and unambiguous programming languages, avoiding confusion in code interpretation.

💼 Career

Compiler developers and language designers must detect and resolve ambiguity to build reliable compilers and interpreters.

1

Create the grammar dictionary

Create a dictionary called grammar with these exact production rules:
'E': ['E + E', 'E * E', 'id']

Compiler Design

# Create the grammar dictionary with the given production rules
# Your code here

Hint

Use a Python dictionary with key 'E' and a list of strings as values.

2

Add the test sentence

Add a variable called test_sentence and set it to the string 'id + id * id' exactly.

Compiler Design

grammar = {
    'E': ['E + E', 'E * E', 'id']
}
# Add the test sentence string
# Your code here

Hint

Assign the exact string including spaces to test_sentence.

3

Write the ambiguity check function

Write a function called is_ambiguous that takes grammar and sentence as parameters and returns true if the sentence can be parsed in more than one way, otherwise false. For this simple example, return true if the sentence is exactly 'id + id * id', else false.

Compiler Design

grammar = {
    'E': ['E + E', 'E * E', 'id']
}
test_sentence = 'id + id * id'
# Define the is_ambiguous function
# Your code here

Hint

Use a simple if statement to check the sentence string.

4

Store the ambiguity result

Add a variable called ambiguous_result and set it to the result of calling is_ambiguous with grammar and test_sentence.

Compiler Design

grammar = {
    'E': ['E + E', 'E * E', 'id']
}
test_sentence = 'id + id * id'

def is_ambiguous(grammar, sentence):
    if sentence == 'id + id * id':
        return true
    else:
        return false

# Store the ambiguity check result
# Your code here

Hint

Call the function with the exact variable names and assign the result.

Practice

1. What does ambiguity in a grammar mean?

easy

A. A sentence can have more than one meaning

B. The grammar has no rules

C. All sentences are correct

D. The grammar is too simple

Solution

1. Step 1: Understand the definition of ambiguity in grammar

   Ambiguity means a sentence can be interpreted in multiple ways within the grammar.

2. Step 2: Compare options with the definition

   Only A sentence can have more than one meaning correctly states that ambiguity means multiple meanings for a sentence.

3. Final Answer:

   A sentence can have more than one meaning -> Option A

4. Quick Check:

   Ambiguity = Multiple meanings [OK]

Hint: Ambiguity means multiple meanings for one sentence [OK]

Common Mistakes:

• Confusing ambiguity with grammar errors
• Thinking ambiguity means no rules
• Assuming ambiguity means all sentences are correct

2. Which of the following grammar rules is ambiguous?

easy

A. S -> aSb | ab

B. S -> aS | b

C. S -> aSb | aSb

D. S -> ab | ba

Solution

1. Step 1: Analyze the grammar rules for ambiguity

   Rule A allows multiple parse trees for strings like 'aabb', causing ambiguity.

2. Step 2: Check other options for ambiguity

   Options B, C, and D do not produce multiple parse trees for the same string.

3. Final Answer:

   S -> aSb | aSb -> Option C

4. Quick Check:

   Multiple parse trees = Ambiguous [OK]

Hint: Look for rules generating multiple parse trees [OK]

Common Mistakes:

• Ignoring repeated rules that cause ambiguity
• Confusing ambiguity with grammar repetition
• Assuming all recursive rules are ambiguous

3. Given the grammar:
E -> E + E | E * E | id
What is the ambiguity in parsing the expression id + id * id?

medium

A. The expression cannot contain '*'

B. The expression is invalid

C. The expression has only one parse tree

D. The expression can be parsed as (id + id) * id or id + (id * id)

Solution

1. Step 1: Understand the grammar's ambiguity

   The grammar allows both '+' and '*' without precedence rules, causing multiple parse trees.

2. Step 2: Analyze the expression parsing

   The expression 'id + id * id' can be parsed as either 'id + (id * id)' or '(id + id) * id', showing ambiguity.

3. Final Answer:

   The expression can be parsed as (id + id) * id or id + (id * id) -> Option D

4. Quick Check:

   Multiple parse trees = Ambiguity [OK]

Hint: Check if operator precedence is missing [OK]

Common Mistakes:

• Assuming only one parse tree exists
• Ignoring operator precedence
• Thinking expression is invalid

4. Identify the error in this ambiguous grammar and suggest a fix:
S -> S + S | S * S | id

medium

A. Ambiguity due to missing operator precedence; fix by defining precedence rules

B. No error, grammar is unambiguous

C. Grammar is invalid syntax; fix by removing recursion

D. Ambiguity due to missing terminals; fix by adding more terminals

Solution

1. Step 1: Identify the cause of ambiguity

   The grammar allows multiple parse trees because it lacks operator precedence rules.

2. Step 2: Suggest a fix

   Define separate rules for '+' and '*' with precedence to remove ambiguity.

3. Final Answer:

   Ambiguity due to missing operator precedence; fix by defining precedence rules -> Option A

4. Quick Check:

   Missing precedence = Ambiguity fix [OK]

Hint: Add precedence rules to fix ambiguity [OK]

Common Mistakes:

• Thinking recursion causes ambiguity
• Assuming grammar syntax is invalid
• Ignoring operator precedence importance

5. How can ambiguity be resolved in a grammar that allows multiple parse trees for the same sentence?

hard

A. By allowing multiple parse trees

B. By rewriting the grammar to enforce operator precedence and associativity

C. By removing all terminals

D. By adding more recursive rules

Solution

1. Step 1: Understand the cause of ambiguity

   Ambiguity arises when the grammar allows multiple parse trees for the same sentence.

2. Step 2: Apply a solution

   Rewriting the grammar to include operator precedence and associativity rules removes ambiguity.

3. Final Answer:

   By rewriting the grammar to enforce operator precedence and associativity -> Option B

4. Quick Check:

   Rewrite grammar with precedence = Resolve ambiguity [OK]

Hint: Use precedence and associativity rules to fix ambiguity [OK]

Common Mistakes:

• Adding recursion increases ambiguity
• Removing terminals breaks grammar
• Accepting ambiguity as normal