Mehrdeutige Grammatik

Question

Ich schaue mir die folgende Grammatik an und ich glaube ihre Ambiguous in Zeile 3, aber nicht sicher.

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

fand ich diese Zeichenfolge xi13yi5xeyx I erzeugt zwei verschiedene Syntaxbäume glauben, aber ich bin nicht sicher, ob im es falsch zu machen.

Kann jemand meine Ergebnisse bitte bestätigen?

Answer 1

Ja, deine Grammatik ist eine mehrdeutige Grammatik!
_{Sie haben nicht erwähnt, aber ich denke, <SL> beginnen lebensfähig ist}

Ihre Grammatikregeln verwenden können wir mehr als ein Parse-Baum (zwei) zeichnen für wringen i5i5yey als 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 

Struktur von beiden Parse Baum sind zwei verschiedene die Grammatik ist eine mehrdeutige Grammatik!

Sie obigen Diagramm erweitern können Baum Zeichenfolge xi13yi5xeyx, (Ich lasse dies als eine Übung für Sie)

wichtig ist, die Sprache generieren durch diese Grammatik not ambiguous language zu erzeugen .Und sein mögliches ein schreiben gleichwertige unzweideutige Grammatik für diese Grammatik, die immer einen eindeutigen Baum für jeden String in der Sprache der Grammatik erzeugt.

HINWEIS: Um eine eindeutige Grammatik zu schreiben.

Die Grammatik ist ziemlich ähnlich zu Grammatik für if loop in C-Sprache (beachten Sie, dass andere Sprache unterschiedliche Syntax für if loop hat). und es löste sich in fast allen Compiler-Design-Buch.
Resolving the General Dangling Else/If-Else Ambiguity

Referenz: Buch Compilers Principles, Technik und Werkzeuge von Aho-Ullman Abschnitt 4.5 Konflikte Während Shift-and-Reduce Parsing.