Entfernen der Linksrekursion aus kontextfreien Grammatiken – Reihenfolge von Nichtterminalen

Question

Ich habe kürzlich den Paull-Algorithmus zum Entfernen der Linksrekursion aus kontextfreien Grammatiken implementiert:

Weisen Sie den Nichtterminalen der Grammatik eine Ordnung $A_1, \dots, A_n$ zu.

für $i := 1$ bis $n$ beginnen
$\quad$ für $j:=1$ bis $i-1$ beginnen
$\quad\quad$ für jede Produktion der Form $A_i o A_j\alpha$ beginnen
$\quad\quad\quad$ entfernt $A_i o A_j\alpha$ aus der Grammatik
$\quad\quad\quad$ für jede Produktion der Form $A_j o \beta$ beginnen
$\quad\quad\quad\quad$ füge $A_i o \beta\alpha$ zur Grammatik hinzu
$\quad\quad\quad$ Ende
$\quad\quad$ Ende
$\quad$ Ende
$\quad$ transformiert die $A_i$-Produktionen, um die direkte Linksrekursion zu eliminieren
Ende

Entsprechend dieses Dokument, hängt die Effizienz des Algorithmus entscheidend von der zu Beginn gewählten Reihenfolge der Nichtterminale ab;Das Papier geht ausführlich auf dieses Thema ein und schlägt Optimierungen vor.

Einige Notationen:

Wir werden sagen, dass ein Symbol $X$ ein ist direkte linke Ecke von einem nicht terminalen $ a $, wenn es eine $ -Produktion mit $ x $ als linksmeistes Symbol auf der rechten Seite gibt.Wir definieren die Linke-Eck-Relation als reflexiver transitiver Abschluss der Direkt-Links-Ecken-Beziehung, und wir definieren die Beziehung zwischen rechter und linker Ecke die transitive Schließung der Direktlinks-Eckners-Beziehung sein.Ein Nichtterminal ist links rekursiv wenn es eine richtige linke Ecke von sich selbst ist;ein Nichtterminal ist direkt linksrekursiv wenn es eine direkte linke Ecke von sich selbst ist;und ein Nichtterminal ist indirekt linksrekursiv wenn es rekursiv bleibt, aber nicht direkt rekursiv bleibt.

Folgendes schlagen die Autoren vor:

In der inneren Schleife von Paulls Algorithmus ersetzen wir für Nichtterminale $A_i$ und $A_j$, so dass $i > j$ und $A_j$ eine direkte linke Ecke von $A_i$ ist, alle Vorkommen von $A_j$ als direkte linke Ecke von $A_i$ mit allen möglichen Erweiterungen von $A_j$.

Dies trägt nur dann zur Eliminierung der Linksrekursion aus der Grammatik bei, wenn $A_i$ ein linksrekursives Nichtterminal ist und $A_j$ auf einem Pfad liegt, der $A_i$ linksrekursiv macht;das heißt, wenn $A_i$ eine linke Ecke von $A_j$ ist (zusätzlich dazu, dass $A_j$ eine linke Ecke von $A_i$ ist).

Wir könnten Ersetzungen eliminieren, die beim Entfernen der Linksrekursion nutzlos sind, wenn wir die Nichtterminale der Grammatik so ordnen könnten, dass, wenn $i > j$ und $A_j$ eine direkte linke Ecke von $A_i$ ist, $A_i$ auch a ist linke Ecke von $A_j$.

Wir können dies erreichen, indem wir die Nichtterminale in absteigender Reihenfolge nach der Anzahl ihrer unterschiedlichen linken Ecken ordnen.

Da die Beziehung der linken Ecke transitiv ist, ist jede linke Ecke von C auch eine linke Ecke von B, wenn C eine direkte linke Ecke von B ist.

Da wir außerdem die Beziehung der linken Ecke als reflexiv definiert haben, ist B eine linke Ecke seiner selbst.

Wenn also C eine direkte linke Ecke von B ist, muss es B in abnehmender Reihenfolge der Anzahl verschiedener linker Ecken folgen, es sei denn, B ist eine linke Ecke von C.

Ich möchte am Anfang nur wissen, wie man die Nichtterminale ordnet, aber ich verstehe es nicht aus der Zeitung.Kann es jemand einfacher erklären?Pseudocode würde mir helfen, es besser zu verstehen.

Answer 1

Das ist eigentlich nicht sehr kompliziert.Ich gehe davon aus, dass Epsilon-Produktionen bereits aus der Sprache entfernt wurden, da dies nur das Schlüsselkonzept der „linken Ecke“ verschleiern wird.

Bilden Sie einen Graphen G, in dem die Eckpunkte alle Nichtterminale der Grammatik sind.Zeichnen Sie nun eine gerichtete Kante von A nach B, wenn es eine Produktionsregel gibt, die wie folgt aussieht: „A -> B[...]“.Das Papier nennt B eine „direkte linke Ecke“ von A.Allgemeiner wird ein anderes nichtterminales C als „linke Ecke“ von A bezeichnet, wenn es entlang der Kanten dieses Graphen einen Pfad von A nach C gibt.Dies kann durch die Berechnung erfolgen Transitive Schließung von G, nenne es H.

Das Papier schlägt vor, die Eckpunkte zu ordnen, indem man die Anzahl der linken Ecken zählt, die jeder Eckpunkt A hat (d. h.wie viele andere Nichtterminale Sie von A aus erreichen können, oder den Out-Grad von A im Diagramm H), und sortieren Sie sie dann in absteigender Reihenfolge nach dieser Zahl.

Eine einfache Motivation für diese Richtlinie besteht darin, dass es sinnvoll ist, die Linksrekursion frühzeitig aus S zu entfernen, wenn es ein wichtiges Nichtterminal (z. B. das Startsymbol S) mit Verbindungen zu vielen anderen Symbolen gibt, denn wenn Sie es verlassen Bis später wird es weitere Kopien von S geben, die Sie erweitern müssen.Ich denke, die Erklärung in dem Papier ist überzeugender, aber vielleicht weniger offensichtlich.