Linke Rekursion aus kontextfreien Grammatiken entfernen - Reihenfolge der Nichtterminale

  • Ich habe vor kurzem den Paull-Algorithmus implementiert, um Linksrekursionen aus kontextfreien Grammatiken zu entfernen:

    Weisen Sie eine Reihenfolge $ zu A_1, \ dots, A_n $ zu den Nichtterminals der Grammatik.

    für $ i: = 1 $ bis $ n $ beginnen
    $ \ quad $ for $ j: = 1 $ bis $ i-1 $ beginnen
    $ \ quad \ quad $ für jede Produktion der Form $ A_i \ bis A_j \ alpha $ fangen
    $ \ quad \ quad \ quad $ entfernen Sie $ A_i \ auf A_j \ alpha $ aus der Grammatik
    $ \ quad \ quad \ quad $ für jede Produktion der Form $ A_j \ to \ beta $ beginnen Sie
    $ \ quad \ quad \ quad \ quad $ fügen Sie $ A_i \ zu \ beta \ alpha $ der Grammatik hinzu
    $ \ quad \ quad \ quad $ end
    $ \ quad \ quad $ end
    $ \ quad $ end
    $ \ quad $ transformiert die $ A_i $ -Produktionen, um die direkte Rekursion links zu eliminieren
    Ende

    Gemäß dieses Dokument , die Effizienz des Algorithmus hängt entscheidend von der Reihenfolge der zu Beginn gewählten Nichtterminals ab; Das Papier behandelt dieses Problem ausführlich und schlägt Optimierungen vor.

    Einige Notation:

    Wir werden das sagen Ein Symbol $ X $ ist eine direkte linke Ecke von ein Nichtterminals $ A $, wenn es eine $ A $ -Produktion mit $ X $ als das am weitesten links stehende Symbol auf der rechten Seite gibt. Handseite. Wir definieren die Linke-Ecke-Relation als reflexives transitives Schließen der direkten Linke-Ecke-Relation, und wir definieren die richtige Linke-Ecke-Relation als das Transitive Schließung der direkten Links-Ecke-Beziehung. Ein Nichtterminal ist rekursiv , wenn es eine richtige linke Ecke von sich selbst ist. ein Nichtterminal ist direkt rekursiv , wenn es sich um eine direkte linke Ecke von sich selbst handelt; und ein Nichtterminal ist indirekt rekursiv , wenn es rekursiv bleibt, aber nicht direkt rekursiv.

    Hier ist, was der Autoren pr

    23 January 2014
    Raphael
1 answer
  • Das ist eigentlich nicht sehr kompliziert. Ich gehe davon aus, dass Epsilon-Produktionen bereits aus der Sprache entfernt wurden, weil dadurch nur das Schlüsselkonzept der "linken Ecke" verdeckt wird alle Nicht-Terminals der Grammatik. Zeichnen Sie nun eine gerichtete Kante von A nach B, wenn es eine Produktionsregel gibt, die wie "A - & gt; B [...]" aussieht. Das Papier nennt B eine "direkte linke Ecke" von A. Im Allgemeinen wird ein anderes Nicht-Terminal C als "linke Ecke" von A bezeichnet, wenn entlang der Kanten dieses Diagramms ein Pfad von A nach C verläuft. Dies kann durch Berechnen der transitiven Schließung von G erfolgen, nennen Sie es H.

    Der Artikel schlägt vor, die Scheitelpunkte zu ordnen, indem die Anzahl der linken Ecken jedes Scheitelpunkts A gezählt wird (dh wie viele andere Nicht-Terminals Sie von A erreichen können, oder den Ausschlaggrad von A im Diagramm H) ) und sortiert sie in absteigender Reihenfolge nach dieser Nummer.

    Eine Handwavy-Motivation für diese Richtlinie ist, dass es ein wichtiges Nicht-Terminal (Startsymbol S) mit Verbindungen gibt zu vielen anderen Symbolen), dann ist es sinnvoll, die Linke Rekursion frühzeitig von S zu löschen, denn wenn Sie sie erst später verlassen, werden weitere Kopien von S vorhanden sein, die Sie erweitern müssen. Ich denke, dass die Erklärung in der Zeitung überzeugender ist, aber vielleicht weniger offensichtlich.

    14 June 2012
    Erick Wong