CODEWITHSUNDEEP
grammarformal-languagesll-grammar
prkist
prkist

Reputation: 431

Solving a first-follow conflict in a grammar

I'm currently having problems solving this kind of a conflict in a grammar:

A -> (A)A'
A -> 0A'
A -> 1A'
A'-> NAND A A'
A'-> eps

The problem is that FIRST of A' is NAND - as well as a part of its FOLLOW set. And since there's the A' -> eps rule, that creates a conflict. Is there any way to resolve this conflict? Substitution or factorization don't yield any results - so I guess that I'm missing something.

Upvotes: 0

Views: 773

Answers (1)

1010
1010

Reputation: 1858

The problem is that your grammar is ambiguous. For example 0 NAND 0 NAND 0 has at least two leftmost derivations:

A => 0 A' => 0 NAND A A' => 0 NAND 0 A' A' => 0 NAND 0 NAND A A' A' =>
  => 0 NAND 0 NAND 0 A' A' A' =>* 0 NAND 0 NAND 0

A => 0 A' => 0 NAND A A' => 0 NAND 0 A' A' => 0 NAND 0 A' => 
  => 0 NAND 0 NAND A A' => 0 NAND 0 NAND 0 A' A' =>* 0 NAND 0 NAND 0

rewriting it with ELL syntax it's easier (for me) to see that there are two possible recursions, with A in NAND A, or with the star (A' in the original grammar).

A -> ( '(' A ')' | 0 | 1 ) ( NAND A )*

you could solve the ambiguity making the star the only choice to add NANDs, and using '(' A ')' | 0 | 1 as its operands:

A -> X ( NAND X )*
X -> '(' A ')' | 0 | 1

Upvotes: 2

Related Questions