• ↑↓ pour naviguer
  • ↵ pour ouvrir
  • ⟶ pour sélectionner
  • ⌘ ⌥ ↵ pour ouvrir dans un panneau
  • ←→ pour naviguer
  • esc pour rejeter
⌘ '
raccourcis clavier
semantic not available yet

ambiguous-grammar

The Problem A grammar that allows more than one parse tree for the same input string means the compiler cannot determine the unique syntactic structure of the program.

  • published

  • modified

  • length

    3 min read (421 words)

  • source

    llms.txt

The Problem

A grammar that allows more than one parse tree for the same input string means the compiler cannot determine the unique syntactic structure of the program. This leads to unpredictable behavior — different parsers may interpret the same program differently.

Core Idea

A grammar is ambiguous if there exists a string in its language that has more than one leftmost derivation (equivalently, more than one parse tree). Ambiguity is a property of the grammar, not necessarily of the language — many ambiguous grammars can be rewritten as unambiguous ones.

How It Works

Ambiguity arises when a non-terminal can be expanded in multiple ways that lead to the same input. Classic examples: dangling else (if x if y ... else ... — which if does else belong to?), and expression associativity (E → E + E | id allows two trees for a + b + c). The parser resolves ambiguity through precedence rules, associativity declarations, or grammar rewriting.

Visual Explanation

ambiguous_grammar Input Input: a + b * c Grammar Grammar: E → E + E | E * E | id Input->Grammar Tree1 Parse Tree 1    +   / \  a   *     / \    b   c Grammar->Tree1 a + (b * c) Tree2 Parse Tree 2    *   / \  +   c / \ a   b Grammar->Tree2 (a + b) * c

Key Properties

  • Definition: More than one leftmost derivation for some string
  • Not always a language property: The same language can have both ambiguous and unambiguous grammars
  • Dangling else: Classic ambiguity in languages with nested if-then-else
  • Expression ambiguity: Operator precedence and associativity are typically ambiguous in naive expression grammars
  • Parser resolution: Yacc and Bison allow precedence and associativity declarations to resolve ambiguities

Connections

Edge Cases & Gotchas

  • Inherent ambiguity: Some languages are inherently ambiguous — every grammar for them is ambiguous
  • Ambiguity detection is undecidable: There is no algorithm that can determine whether an arbitrary CFG is ambiguous
  • Yacc/Bison resolution: By default, yacc resolves shift-reduce conflicts in favor of shift — this may not always be what the user wants
  • Disambiguating rules: Associativity declarations (%left, %right) and precedence levels resolve ambiguity without grammar rewriting

you might also like

  • page-fault
  • spring-jdbc-template
  • java-multilevel-inheritance
  • back-pressure
  • algorithm
  • jump game
  • cross-validation
  • Software Development Life Cycle (SDLC)
  • Introduction of B+ Tree
    • classification-of-context-free-grammars
    The Problem Not all context-free grammars are equally useful for parsing.
    context-free-grammar
    The Problem Natural language descriptions of syntax (“an if statement consists of the keyword if, followed by a parenthesized expression, followed by a statement”) are imprecise, ambiguous, and cannot be processed by software.
    first-and-follow-sets
    The Problem Top-down predictive parsers need to decide which production to apply based on the current input token.
    operator-precedence-parser
    The Problem Expression parsing is the most common parsing task, yet full LR parsing is overkill for expression grammars.
    shift-reduce-parser
    The Problem Building a parse tree bottom-up requires an algorithm to decide when a group of tokens forms a complete grammatical unit (a handle) and should be replaced by a non-terminal.
    syntax-analysis
    The Problem A token stream is still flat and lacks structure.
    top-down-parsing
    The Problem Bottom-up parsers (LR) are powerful but complex to implement manually.
    unambiguous-grammar
    The Problem Ambiguous grammars create non-determinism in parsing — the parser doesn’t know which parse tree is the intended one.