Ambiguity Analysis of an Expression Grammar with +, , Parentheses, and id | AI Research

Ambiguity Analysis of an Expression Grammar with +, *, Parentheses, and id

Verified Sources

Nov 4, 2026

Consider the grammar:

E \rightarrow E + T \mid T

T \rightarrow T * F \mid F

F \rightarrow (E) \mid id

To decide whether it is ambiguous, we must determine whether there exists at least one string of terminals (e.g., a token sequence like $id+id*id$ ) that has two distinct parse trees (equivalently, two distinct leftmost derivations / rightmost derivations). A grammar is ambiguous if some string has multiple parse trees; it is unambiguous if every string has exactly one parse tree.

Key keyword ambiguity} questions to answer here:

Where can $+$ and $*$ appear in the derivations?
Does the grammar enforce operator precedence ( $*$ binds tighter than $+$ )?
Does the grammar enforce left associativity for both $+$ and $*$ ?

We’ll show that the grammar enforces:

$*$ has higher precedence than $+$ , because $E$ expands into $T$ ’s and only $E$ adds $+$ .
Both $+$ and $*$ are left-associative, because the recursion is of the form $E \to E + T$ and $T \to T * F$ (left recursion).

As a result, the parse structure for any expression is forced: $+$ “splits” the expression into a sequence of $T$ terms, and each $T$ “splits” further into a sequence of $F$ factors separated by $*$ , with parentheses handled by $F \to (E)$ .

The grammar is therefore unambiguous.

type="tip" title="Pro Tip" content="To prove unambiguity, it’s often enough to argue uniqueness of the operator-level decomposition: show that every string has exactly one way to split into top-level $+$ terms and then into $*$ factors."

Operator decomposition idea (why the grammar structure is forced)

Observe the nonterminals’ roles:

$E$ represents expressions built from $+$ connecting one or more $T$ ’s.
$T$ represents terms built from $*$ connecting one or more $F$ ’s.
$F$ represents the smallest units: either $(E)$ or $id$ .

So any derivation for a string of the form:

$E$ will produce some sequence containing $+$ at the “top level”.
$T$ will produce some sequence containing $*$ at the “next level”.
$F$ will never introduce $+$ or $*$ by itself—those operators can appear only via expanding $E$ or $T$ .

This immediately yields precedence: a $*$ cannot “escape” to become a $+$ at the $E$ level, because $E$ only creates $+$ by using the production $E \to E + T$ .

keyword precedence] and keyword associativity] here follow from the grammar’s stratification:

$*$ happens inside $T$
$+$ happens inside $E$

Unambiguity justification by forced grouping at each operator level

1
Step 1
Let $w$ be a string derived from $E$ (e.g., $id+id*id$ , $(id+id)*id$ , etc.).
2
Step 2
At the top level, the only way to introduce a $+$ token in a derivation from $E$ is via $E \to E + T$ . Therefore any derived string that contains $+$ must have a unique decomposition into a left part and a right $T$ at the outermost $+$ that is not inside parentheses.
3
Step 3
When $+$ occurs inside parentheses, it is generated only inside $F \to (E)$ . This prevents $+$ from interfering with the outer $E$ -level decomposition because the parentheses create a boundary for the substring derived by that $E$ .
4
Step 4
Once the outer split produces a left $E$ and a right $T$ , each $T$ substring can contain $*$ only through $T \to T * F$ . Thus each $T$ substring has a forced decomposition into left and right parts around $*$ at the corresponding $T$ level.
5
Step 5
Similarly, if a $T$ substring contains $*$ , it must correspond to repeated use of $T \to T * F$ with $F$ units as the leaves. Parentheses again isolate $F \to (E)$ occurrences uniquely.
6
Step 6
Because the recursion is $E \to E + T$ (not $E \to T + E$ ) and $T \to T * F$ (not $T \to F * T$ ), the grouping of a chain like $id+id+id$ is forced to left association: $((id+id)+id)$ . Likewise, $id*id*id$ groups as $((id*id)*id)$ .
7
Step 7
Since the outermost $+$ decomposition is unique (thanks to operator placement rules and parentheses boundaries), and each produced $T$ substring has a unique $*$ decomposition, and each $F$ leaf is either $(E)$ or $id$ , the entire parse tree for $w$ is unique. Hence the grammar is unambiguous.

type="warning" title="Common Pitfall" content="A grammar with left recursion can still be ambiguous in some cases (e.g., if both parse structures can introduce the same operators at the same syntactic level). Here, the separation into E (only +) and T (only *) is what prevents competing parse trees."

Worked micro-examples (showing uniqueness)

Example 1: $id+id*id$

The $*$ must be inside $T$ because $E$ only adds with $E \to E+T$ .
There is only one plausible hierarchy:
- $E \Rightarrow E + T$
- left $E \Rightarrow T \Rightarrow F \Rightarrow id$
- right $T \Rightarrow T * F$
- $T \Rightarrow F \Rightarrow id$ for the left factor
- $F \Rightarrow id$ for the right factor

So the structure corresponds to:

$id + (id * id)$

Example 2: $(id+id)*id$

Parentheses force the $id+id$ part to be parsed as an $E$ inside a single $F$ :

$T \Rightarrow T * F$
the $F$ on the left is $(E)$ , and inside it the $E$ must be $E \Rightarrow E + T$

So it becomes:

$(id+id) * id$

These examples illustrate precedence: without parentheses, $*$ groups tighter; with parentheses, the $E$ inside $F$ groups first.

How the grammar enforces structure from tokens to parse tree

Leaves

1) Token level

Only $id$ or $(E)$ appear as $F$ ."

Build products

2) Factor level

$T \to T * F$ constructs sequences of $F$ connected by $*$ ."

Build sums

3) Term level

$E \to E + T$ constructs sequences of $T$ connected by $+$ . "

Recursive isolation

4) Parentheses boundary

$F \to (E)$ creates a boundary so outer operators cannot regroup inside."

Knowledge Check

Question 1 of 3

Q1Single choice

The grammar $E \to E + T \mid T$ , $T \to T * F \mid F$ , $F \to (E) \mid id$ is best classified as:

Ambiguous

Unambiguous

Ambiguous only for strings without parentheses

Unambiguous only for single-token strings

Explore Related Topics

FIRST and FOLLOW Sets for the Grammar $E \rightarrow E+T/T$, $T \rightarrow T*F/F$, $F \rightarrow (E)/id$

Ambiguity in Grammar and a Proof of Ambiguity for a Given CFG

Synthesized Attributes for Evaluating Arithmetic Expressions (E→E+T|T, T→T*F|F)

Browse all research articles