Wie kann ich zeigen, dass diese Grammatik mehrdeutig ist?

Question

Ich möchte beweisen, dass diese Grammatik mehrdeutig ist, aber ich bin nicht sicher, wie ich das tun soll. Muss ich Parse Bäume verwenden?

S -> if E then S | if E then S else S | begin S L | print E 
    L -> end | ; S L 
    E -> i 

Answer 1

Sie können die Grammatik in einen Parsergenerator einfügen, der alle kontextfreien Grammatiken unterstützt, einen kontextfreien allgemeinen Parsergenerator. Generieren Sie den Parser, parsen Sie dann einen String, den Sie für zweideutig halten, und finden Sie heraus, indem Sie sich die Ausgabe des Parsers ansehen.

Ein kontextfreier genereller Parsergenerator erzeugt Parser, die alle Ableitungen in polynomieller Zeit erzeugen. Beispiele für solche Parser-Generatoren umfassen SDF2, Rascal, DMS, Elkhound, ART. Es gibt auch eine Backtracking-Version von yacc (btyacc), aber ich glaube nicht, dass es in polynomieller Zeit funktioniert. Normalerweise wird die Ausgabe als ein Diagramm codiert, in dem alternative Bäume für Untersätze mit einer verschachtelten Menge alternativer Bäume codiert sind.

Answer 2

können Sie zeigen es eindeutig ist, wenn Sie eine Zeichenfolge, die mehr als eine Art und Weise analysiert finden:

if i then (if i then print i else print i ;) 
if i then (if i then print i) else print i ; 

Dies geschieht Mehrdeutigkeit der klassische „dangling else“ zu sein. Googeln Sie Ihre Tag (s), Titel & Grammatik gibt andere Treffer.

Wenn Sie jedoch nicht bei einer mehrdeutigen Zeichenfolge zu erraten passieren googling your tag(s) & title dann:

how can i prove that this grammar is ambiguous?

Es gibt keine einfache Methode für eine kontextfreie Grammatik mehrdeutig erweist sich - in Tatsache, the question is undecidable, durch Reduktion auf die Post correspondence problem.