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

Popular posts from this blog

android - MPAndroidChart - How to add Annotations or images to the chart -

javascript - Add class to another page attribute using URL id - Jquery -

firefox - Where is 'webgl.osmesalib' parameter? -