Konvertieren Sie PEG in BNF

Das Analysieren von Ausdrucksgrammatiken (PEGs) ist eindeutig und hat eine oberflächlich ähnliche Syntax wie BNF , enthält jedoch drei wichtige Unterschiede:

Der bestellte Auswahloperator e1 / e2 / e3.
Das und Prädikat &.
Der Nicht-Operator !.

Ich habe ein paar Fragen:

Sind die von PEGs erkannten Sprachen alle kontextfrei?
Wenn die Antwort auf (1) Nein lautet, gibt es ausdrucksstarke Grammatikformalismen, die garantiert nur eindeutige Grammatiken erzeugen? Insbesondere würde fallen &und !nur kontextfreie Grammatiken ergeben?
Wenn alle PEGs kontextfrei sind, können sie über einen Algorithmus in eine äquivalente BNF umgewandelt werden?

Der Kontext ist, dass ich Generierungsfunktionen für eine PEG-Bibliothek unter Verwendung des Chomsky-Schützenberger-Aufzählungssatzes berechnen möchte . Dies scheint eine Spezifikation der Grammatik in einer Standardform ähnlich BNF zu erfordern.

context-free formal-grammars normal-forms RekursivIronic
quelle

Sind die von PEGs erkannten Sprachen alle kontextfrei?

Nein, wie Brian Ford in seiner Veröffentlichung von PEGs aus dem Jahr 2004 hervorhob , aus der das folgende kurze Zitat hervorgeht:

Satz: Die Klasse der PELs enthält nicht kontextfreie Sprachen.

Beweis: Die klassische Beispielsprache $a^nb^nc^n$ ist nicht kontextfrei, aber wir können es mit einem PEG erkennen $G = (\{A, B, D\}, \{a, b, c\}, R, D)$ , wobei R die folgenden Definitionen enthält:
$EIN \leftarrow ein EIN b /. ε$ $A \leftarrow aAb / ε$ $B. \leftarrow b B. c /. ε$ $B \leftarrow bBc / ε$ $D. \leftarrow & (EIN! b) {ein}^{*} B.! .$ $D \leftarrow \&(A !b) a^∗ B !.$

Wenn die Antwort auf (1) Nein lautet, gibt es ausdrucksstarke Grammatikformalismen, die garantiert nur eindeutige Grammatiken erzeugen? Insbesondere würde fallen $\&$ und $!$ nur kontextfreie Grammatiken liefern?

Auch ohne $!$ (und daher ohne $\&$ , da es formal definiert ist in Bezug auf $!$ ) müssten Sie sich immer noch mit der impliziten Ergänzung befassen, die in der Definition der geordneten Wahl verborgen ist. Ich habe kein konkretes Beispiel für eine geordnete Auswahl, die zu einer Nicht-CFL führt, aber ich würde versuchen, eine zu finden, indem ich mit zwei CFGs beginne $L_1$ und $L_2$ deren Differenz keine CFL ist und die in PEGs umgewandelt werden kann $P_1$ und $P_2$ . Nun, wenn $\mathbb{c}$ ist ein Symbol nicht in beiden Sprachen, dann die PEG $P_2 / P_1\mathbb{c}$ sollte erkennen $L_2 \cup (L_1- L_2)\mathbb{c}$ , die keine CFL ist.

Wenn alle PEGs kontextfrei sind, können sie über einen Algorithmus in eine äquivalente BNF umgewandelt werden?

Wenn meine obige Vermutung richtig ist, ist diese Frage nicht zutreffend, aber auf jeden Fall gibt es keinen mir bekannten Algorithmus zum Konvertieren zwischen PEGs und CFGs, und ich glaube, dass die Gleichwertigkeit eines PEG und eines CFG unentscheidbar ist. Diese Tatsache erschwert das oben vorgeschlagene Beweisverfahren. :) :)

Rici
quelle

Ich bin mir nicht sicher, ob ich dir folge

P_{1} / P_{2} C

$P_1/P_2\mathbb{C}$ Beispiel. Aus dem Artikel "PEGs verwenden einen priorisierten Auswahloperator '/'. Dieser Operator listet alternative Muster auf, die der Reihe nach getestet werden sollen, bedingungslos unter Verwendung der ersten erfolgreichen Übereinstimmung." Beliebige Zeichenfolge einschließlich

C

$\mathbb{C}$ würde die erste Bedingung nicht bestehen, so ist die erkannte Sprache

L_{1} \cup (L_{2} C)

$L_1\cup (L_2\mathbb{C})$ , was eindeutig kontextfrei ist.

RekursivIronic

"Ich glaube, dass die Gleichwertigkeit von PEG und CFG unentscheidbar ist." Das ist wahrscheinlich wahr, aber irrelevant. Viele Verfahren erzeugen äquivalente Spezifikationen (z. B. Konvertierung in die Chomsky-Normalform), auch wenn die Entscheidung über die Äquivalenz beliebiger Grammatiken nicht entschieden werden kann.

RekursivIronic

@rekursiv: So funktioniert die von PEG bestellte Auswahl nicht. Der Fallback zu

L_{2} c

$L_2\mathbb{c}$ passiert nur wenn

L_{1}

$L_1$ passt nicht zusammen. Wenn es übereinstimmt, verursacht die Tatsache, dass das Muster anschließend fehlschlägt, keinen Fallback. Eine geordnete Auswahl ist nicht nur eine Möglichkeit, Parses zu unterscheiden.

Rici

Ah OK, bis. Wäre die Sprache dann nicht

L_{1} \cup (L_{2} - L_{1}) c

$L_1\cup (L_2 - L_1)\mathbb{c}$ ? In jedem Fall scheint Ihr zugrunde liegender Punkt korrekt zu sein, sodass das Chomsky-Schützenberger-Theorem nicht gilt. Ich muss mein Projekt wechseln, um eine Standard-Parsing-Bibliothek zu unterstützen, die auf CFGs basiert. Vielen Dank!

RekursivIronic

@RecursivelyIronic: Ja, Sie haben Recht, ich hätte es als festgelegten Unterschied schreiben sollen, und ich habe die Antwort korrigiert. Vielen Dank. (Ich persönlich finde es schwierig, über die PEG-Semantik nachzudenken, aber ein Teil davon ist mangelnde Erfahrung. Das ist alles sehr zirkulär. Aber ich würde sie nicht in einem Kontext verwenden, in dem ich die Grammatik analysieren oder transformieren wollte, gerade wegen der Schwierigkeiten beim Analysieren und / oder Transformieren von PEG-Grammatiken.)

Rici

Konvertieren Sie PEG in BNF

Antworten: