Ambiguity in grammars in Compiler Design - Time & Space Complexity

Time Complexity: Ambiguity in grammars

O(2^n)

Understanding Time Complexity

When we analyze ambiguity in grammars, we want to understand how hard it is to detect if a grammar can produce more than one parse tree for the same sentence.

The question is: how does the effort to find ambiguity grow as the grammar gets bigger?

Scenario Under Consideration

Analyze the time complexity of checking ambiguity by trying all possible parse trees.

function isAmbiguous(grammar) {
  for each sentence in language(grammar) {
    parseTrees = generateAllParseTrees(sentence, grammar)
    if (count(parseTrees) > 1) return true
  }
  return false
}
    

This code tries to find if any sentence has more than one parse tree, indicating ambiguity.

Identify Repeating Operations

Look for repeated work in the code.

• Primary operation: Generating all parse trees for each sentence.
• How many times: For every sentence in the language, which can be very large or infinite.

How Execution Grows With Input

As the grammar grows, the number of sentences and parse trees grows very fast.

Input Size (grammar rules)	Approx. Operations
10	Thousands of parse trees to check
100	Millions or more parse trees to check
1000	Billions or more parse trees, practically impossible

Pattern observation: The effort grows very fast, much faster than the grammar size itself.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed doubles or more as the grammar size increases, making ambiguity detection very costly.

Common Mistake

[X] Wrong: "Checking ambiguity is easy because we just need to find one sentence with two parses quickly."

[OK] Correct: The number of sentences and parse trees can be huge, so checking all possibilities takes a very long time.

Interview Connect

Understanding how ambiguity checking grows helps you appreciate why some compiler tasks are hard and need smart approaches.

Self-Check

"What if we limit the grammar to only a certain type, like unambiguous grammars? How would the time complexity change?"