Machen Sie eine kontextfreie Grammatik nicht mehrdeutig

Ich habe diese Woche einen Test. Es gibt die folgende Grammatik für Boolesche Aussagen:Machen Sie eine kontextfreie Grammatik nicht mehrdeutig

B -> B and B | not B | (B) | id

B ein nicht-Terminal ist und die Anschlüsse sind: and, not, (, ), id

Diese Grammatik mehrdeutig ist. Ich muss es neu schreiben und eine äquivalente Grammatik erstellen, die nicht mehrdeutig und ohne linke Rekursion ist, so dass not in hoher Priorität, 'und' ist assoziativ nach links.

Ich habe versucht, es selbst zu tun:

B -> not B' | (B' | id B'

aber ich denke, das ist falsch, und ich bin wirklich für eine lange Zeit fest: mein Anfang.

Quelle

2016-06-27 CnR

Was genau meinen Sie mit "mehrdeutig"? Die anfängliche Grammatik erlaubt eine Auswahl der Substitution und Ihr Vorschlag erlaubt auch eine Substitution. Bitte klären Sie. – Codor

zweideutig bedeutet, dass es zwei syntaktische Strukturen für ein Wort in der Sprache gibt. Zum Beispiel das Wort: a und b und c, hat 2 Parsing Bäume – CnR

@Codor sieht mehrdeutig, weil 'nicht A und B' entweder' nicht (A und B) 'oder' (nicht A) und B', es gibt keine Vorrangregeln in der ursprünglichen Grammatik. –

Wenn Sie mehrere Nicht-Terminals verwenden, können Sie die Priorität für alle Operatoren festlegen (ich hoffe, ich bekomme die Schreibweise, die Sie verwenden, richtig).

Dies ist von rechts nach links Assoziativität für und zu erhalten: id und id und id analysiert wird als ID und [id und id]

B -> NotExpr | NotExpr and B 
NotExpr -> PrimaryExpr | not NotExpr 
PrimaryExpr -> id | (B)

Dies ist von links nach rechts zu bekommen Assoziativität für und: id und id und id wird analysiert, wie [id und id] und id

B -> NotExpr | B and NotExpr 
NotExpr -> PrimaryExpr | not NotExpr 
PrimaryExpr -> id | (B)

Quelle

2016-06-27 07:15:35

Aber Ihre Priorität ist nur in den Namen der onterminals - es ist nicht real ... –

Der Vorrang ist real: zum Beispiel kann "nicht ID und ID" nur als "[nicht ID] und ID" und nicht geparst werden als "nicht [ID und ID]", weil "ID und ID" kein PrimaryExpr ist. Das Hinzufügen eines Nicht-Terminals für jede Prioritätsebene bis hinunter zu einem primären Ausdruck und das anschließende Sichern in Klammern ist eine typische Methode zum Erstellen von Grammatiken, siehe z. B. die XQuery-Grammatik. –

Jetzt sehe ich. Es tut uns leid. –

Ein weiterer Ansatz der folgenden sein könnte (nach bearbeiten, dank @ Peter):

B -> not B | B' 
B' -> (B) | B' and B | id

Quelle

2016-06-27 07:20:12 maxik

Unsinn. Sie können nur einen NOT bekommen. –

Machen Sie eine kontextfreie Grammatik nicht mehrdeutig

Antwort

Verwandte Themen