Geek asks and answers

Ambiguous Grammar

I am considering the following grammar, and I find it ambiguous in line 3, but not sure.

<SL> → <S>
<SL> → <SL> <S>
<S> → i <B> <S> e <S>
<S> → i <B> <S> 
<S> → x
<S> → y
<B> → 5
<B> → 13

I found this line. xi13yi5xeyxI believe that it generates two different parsing trees, but I'm not sure im doing it wrong.

Can someone please confirm my findings?

+5
source share
1 answer

Yes, your grammar is an ambiguous grammar!
You have not mentioned, but I think it <SL>will become viable

Using your grammar rules, we can draw more than one parse tree (two) for extraction i5i5yeyas follows:

       <SL>                              <SL>
        |                                 |  
       <S>                               <S>   
     / /|\ \                            / | \ 
    / / | \ \                          /  |  \
   / /  |  \ \                        /   |   \
  / /   |   \ \                      i   <B>   <S>      
 /  |   |   |  \                          |  / /|\ \     
 i <B> <S>  e  <S>                        5 / / | \ \
   /  / | \     |                          / /  |  \ \  
  /  /  |  \    y                         / /   |   \ \
 5  i  <B> <S>                           /  |   |   |  \  
        |   |                           i  <B> <S>  e  <S> 
        5   y                               |   |       |  
                                            5   y       y

The structure of both parse trees is different from the two grammars with an ambiguous grammar!

, xi13yi5xeyx ( )

, , , . , .

. .

if loop C ( , if loop). .
/

: , Aho-Ullman 4.5 Shift -Reduce.

+5

More articles:


All Articles