Niejednoznaczna gramatyka

Question

Patrzę na następującą gramatykę i uważam ją za wieloznaczną na linii 3, ale nie jestem pewna.

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

znalazłem ten ciąg xi13yi5xeyx wierzę generuje dwa różne drzewa analizowania, ale nie jestem pewien, czy robię to źle.

Czy ktoś może zweryfikować moje wyniki?

Answer 1

Tak, twoja gramatyka jest niejednoznaczną gramatyką!
_{Nie wspominając Ale myślę <SL> jest rozpocząć realną}

Korzystanie z reguły gramatyczne możemy wyciągnąć więcej niż jedno drzewo parse (dwa) dla ukręcić i5i5yey jak 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 z obu drzew parse są dwa różne gramatyka jest niejednoznaczna gramatyka!

można przedłużyć powyżej schematu wygenerować drzewo ciąg xi13yi5xeyx, (Wyjeżdżam to jako ćwiczenie dla ciebie)

ważny jest język generowania przez ten gramatyki not ambiguous language .A jego możliwości napisać odpowiednik jednoznacznej gramatyki dla tej gramatyki, która zawsze generuje unikalne drzewo dla każdego ciągu w języku gramatyki.

WSKAZÓWKA: Pisanie jednoznacznej gramatyki.

Gramatyka jest bardzo podobna do gramatyki dla if loop w języku C (należy zauważyć inny język o innej składni dla if loop). i rozwiązano go prawie we wszystkich książkach do projektowania kompilatorów.
Resolving the General Dangling Else/If-Else Ambiguity

referencyjny: Book Kompilatory Zasady, techniki i narzędzia, Aho, Ullman punkt 4.5 konflikty w trakcie zmiany i-Zmniejszyć parsowania.