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

Need a 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

Need a 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

Need a 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

Need a hint?

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