程序代写代做代考 Context-Free Grammars: Ambiguity, Associativity and

Context-Free Grammars: Ambiguity, Associativity and
Precedence

• Context-Free, or Type 2, Grammars, are used to for-
mally define the syntax of programming languages.
They are also known as BNF, or Backus-Naur Form.

• Two grammars are equivalent if they generate the
same language.

1

• A derivation in a context-free grammar can be rep-
resented by a parse tree.

– the root is the start symbol

– the interior nodes are non-terminals

– the leaves in left-to-right order form a sentential
form

– X1, X2,…,Xm are the children of A only if A ->
X1X2…Xm is a production

2

• A grammar is ambiguous if it generates a string with
two distinct parse trees.

Example:

< expr > ::= x|y|z|(< expr >)
| < expr > + < expr >
| < expr > ∗ < expr >

Ambiguous: x + y + z.

Rule: A grammar is ambiguous if it is both left and
right recursive.

Fix: remove right recursion

< expr > ::= < element >
| < expr > + < element >
| < expr > ∗ < element >

< element > ::= x|y|z|(< expr >)

3

Example: ”Dangling Else” Problem

S ::= if E then S
| if E then S else S
| other

Ambiguous: if E then if E then S else S

Fix:

S → S1 | S2
S1 → if E then S1 else S1
S1 → other
S2 → if E then S
S2 → if E then S1 else S2

4

Associativity

• Productions that are left-recursive force evaluation
in left-to-right order (left associativity).

• Productions that are right-recursive force evaluation
in right-to-left order (right associativity).

• Example: This left-recursive grammar enforces left-
associativity:

< expr > ::= < element >
| < expr > + < element >
| < expr > ∗ < element >

< element > ::= x|y|z|(< expr >)

– Parse x + y + z again.

– Parse x+y∗z and x∗y+z; note that left-associativity
is maintained, but + and * have the same prece-
dence.

5

Precedence

• Precedence is introduced by adding new non-terminal
symbols.

• Cascade symbols with lowest precedence closest to
the start symbol.

• Example

< expr > ::= < term >
| < expr > + < term >

< term > ::= < element >
| < term > ∗ < element >

< element > ::= x|y|z|(< expr >)

Now Parse x + y ∗ z and x ∗ y + z; note that left-
associativity and the correct precedence are enforced.

6

• Example

• Precedence: (), – (unary), ↑, */, +-

• Associativity:
left: */+-
right: ↑

< expr > ::= < term >
| < expr > + < term >
| < expr > − < term >

< term > ::= < factor >
| < term > ∗ < factor >
| < term > / < factor >

< factor > ::= < primary >↑< factor >
| < primary >

< primary > ::= − < primary >
| < element >

< element > ::= x|y|z|(< expr >)

7