formal languages - Solving a first-follow conflict in a grammar -
i'm having problems solving kind of conflict in grammar:
a -> (a)a' -> 0a' -> 1a' a'-> nand a' a'-> eps
the problem first of a' nand - part of follow set. , since there's a' -> eps rule, creates conflict. there way resolve conflict? substitution or factorization don't yield results - guess i'm missing something.
the problem grammar ambiguous. example 0 nand 0 nand 0
has @ least 2 leftmost derivations:
a => 0 a' => 0 nand a' => 0 nand 0 a' a' => 0 nand 0 nand a' a' => => 0 nand 0 nand 0 a' a' a' =>* 0 nand 0 nand 0 => 0 a' => 0 nand a' => 0 nand 0 a' a' => 0 nand 0 a' => => 0 nand 0 nand a' => 0 nand 0 nand 0 a' a' =>* 0 nand 0 nand 0
rewriting ell syntax it's easier (for me) see there 2 possible recursions, in nand a
, or star (a' in original grammar).
a -> ( '(' ')' | 0 | 1 ) ( nand )*
you solve ambiguity making star choice add nands, , using '(' ')' | 0 | 1
operands:
a -> x ( nand x )* x -> '(' ')' | 0 | 1
Comments
Post a Comment