Ambiguous grammar

ambiguous-grammar, context-free-grammar, grammar

Solution

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.

Problem

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?

Original source