Ambiguous grammar

Question

I am looking at the following grammar and I believe its Ambiguous at 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 string xi13yi5xeyx I believe generates two different parse trees, but I'm not sure if im doing it wrong.

Can some one please verify my findings?

Answer 1

Yes your grammar is an ambiguous grammar!
_{You have not mention But I think <SL> is start viable}

Using your grammar rules we can draw more then one parse tree(two) for wring i5i5yey as followes:

       <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   

Structure of both parse tree are different two the grammar is an ambiguous grammar!

You can extend above diagram to generate tree string xi13yi5xeyx, (I am leaving this as an exercise for you)

Important is the language generate by this grammar is not ambiguous language.And its possible to write an equivalent unambiguous grammar for this grammar that always generates unique tree for each string in language of grammar.

HINT: To write unambiguous grammar.

The grammar is quite similar to grammar for if loop in C language (notice different language having different syntax for if loop). and it solved in almost all compiler design book.
Resolving the General Dangling Else/If-Else Ambiguity

Reference: Book Compilers Principles, Technique, and tools by Aho-Ullman Section 4.5 conflicts During Shift and-Reduce Parsing.