Laut "Rekursiver Descent-Parser" auf Wikipedia ist ein rekursiver Abstieg ohne Backtracking (auch als Predictive Parsing bezeichnet) nur für LL (k) Grammatiken.
An anderer Stelle habe ich gelesen, dass die Implementierung von Lua einen solchen Parser verwendet. Die Sprache ist jedoch nicht LL (k). In der Tat ist Lua von Natur aus zweideutig: does a = f(g)(h)[i] = 1 mean a = f(g); (h)[i] = 1 oder a = f; (g)(h)[i] = 1 ? Diese Zweideutigkeit wird durch die Gierigkeit im Parser gelöst (so wird das Obige als das fehlerhafte a = f(g)(h)[i]; = 1 geparst).
Dieses Beispiel scheint zu zeigen, dass prädiktive Parser mit Grammatiken umgehen können, die nicht LL (k) sind. Stimmt es, dass sie tatsächlich eine Obermenge von LL (k) handhaben können? Wenn ja, gibt es eine Möglichkeit herauszufinden, ob eine gegebene Grammatik in dieser Obermenge ist?
Mit anderen Worten, wenn ich eine Sprache entwerfe, die ich unter Verwendung eines vorhersagenden Parsers parsen möchte, muss ich die Sprache auf LL (k) beschränken? Oder gibt es eine lockere Einschränkung, die ich anwenden kann?
Für eine geeignete Definition dessen, was ein rekursiver Descent-Parser ist, ist es absolut richtig, dass nur LL (k) Sprachen durch rekursiven Abstieg geparst werden können.
Lua kann mit einem rekursiven Descent-Parser genau analysiert werden, weil die Sprache LL (k) ist; Das heißt, eine LL (k) Grammatik existiert für Lua. [Anmerkung 1]
Eine Sprache ist LL (k), wenn es eine LL (k) Grammatik gibt, die die Sprache erkennt. Das bedeutet nicht, dass jede Grammatik, die die Sprache erkennt, LL (k) ist; Es könnte eine beliebige Anzahl von Nicht-LL (k) Grammatiken geben, die die Sprache erkennen. Die Tatsache, dass einige Grammatik nicht LL (k) ist, sagt absolut nichts über die Sprache selbst aus.
In der formalen Sprachtheorie ist eine Sprache inhärent mehrdeutig nur dann, wenn Jede Grammatik für die Sprache ist mehrdeutig. Es ist wahrscheinlich sicher zu sagen, dass keine praktische Programmiersprache an sich mehrdeutig ist, da praktische Programmiersprachen (irgendwie) deterministisch geparst werden. [Anmerkung 2].
Da das Schreiben einer streng nicht zweideutigen Grammatik mühsam sein kann, ist es ziemlich üblich, dass die Sprachdokumentation eine mehrdeutige Grammatik liefert, zusammen mit einem Textmaterial, das angibt, wie die Mehrdeutigkeiten gelöst werden sollen.
Zum Beispiel sind viele Sprachen (einschließlich Lua) mit einer Grammatik dokumentiert, die nicht explizit die Vorrangstellung des Operators enthält, was eine einfache Regel für Ausdrücke erlaubt:
%Vor%Diese Regel ist eindeutig mehrdeutig, aber angesichts einer Liste von Operatoren, ihrer relativen Präzedenz und einer Angabe, ob jeder Operator links- oder rechtsassoziativ ist, kann die Regel mechanisch zu einer unzweideutigen Ausdrucksgrammatik erweitert werden. Tatsächlich erlauben viele Parsergeneratoren dem Benutzer, die Rangfolgedeklarationen getrennt bereitzustellen und die mechanische Erweiterung im Verlauf der Erzeugung des Parsers durchzuführen. Es sollte beachtet werden, dass der resultierende Parser ein Parser für die disambiguated Grammatik ist, so dass die Mehrdeutigkeit der ursprünglichen Grammatik nicht impliziert, dass der Parsing-Algorithmus mit mehrdeutigen Grammatiken umgehen kann.
Ein weiteres bekanntes Beispiel für mehrdeutige Referenzgrammatiken, die mechanisch disambiguiert werden können, ist die "dangling else" Mehrdeutigkeit in Sprachen wie C (aber nicht in Lua). Die Grammatik:
%Vor%ist sicherlich mehrdeutig; Die Absicht ist, dass der Parse "gierig" sein soll. Auch hier ist die Mehrdeutigkeit nicht inhärent. Es gibt eine mechanische Transformation, die eine unzweideutige Grammatik erzeugt, etwa so:
%Vor%Es ist durchaus üblich, dass Parsergeneratoren diese Transformation implizit ausführen. (Für einen LR-Parser-Generator wird die Umwandlung tatsächlich durch das Löschen von Reduzierungsaktionen implementiert, wenn sie mit einer Verschiebungsaktion in Konflikt stehen. Dies ist einfacher als das Transformieren der Grammatik, hat aber genau den gleichen Effekt.)
So ist Lua (und andere Programmiersprachen) nicht inhärent mehrdeutig; und daher können sie mit Parsing-Algorithmen analysiert werden, die eindeutige deterministische Parser erfordern. In der Tat könnte es sogar ein wenig überraschend sein, dass es Sprachen gibt, für die jede mögliche Grammatik mehrdeutig ist. Wie in dem oben zitierten Wikipedia-Artikel ausgeführt, wurde die Existenz solcher Sprachen von Rohit Parikh 1961 nachgewiesen; Ein einfaches Beispiel für eine inhärent mehrdeutige kontextfreie Sprache ist
{anbmcmdn|n,m≥0} ∪ {anbncmdm|n,m≥0} .
Wie bei der obigen dangling else-Konstruktion wird die Disambiguierung von Lua-Anweisungssequenzen durchgeführt, indem nur das gierige Parse erlaubt wird. Intuitiv ist das Verfahren geradlinig; Es basiert auf dem Verbot von zwei aufeinanderfolgenden Anweisungen (ohne dazwischenliegendes Semikolon), wobei die zweite mit einem Token beginnt, das den ersten fortsetzt.
In der Praxis ist es nicht wirklich notwendig, diese Transformation durchzuführen; Dies kann implizit während der Konstruktion des Parsers geschehen. Also werde ich mir nicht die Mühe machen, hier eine vollständige Lua-Grammatik zu erstellen. Aber ich vertraue darauf, dass die kleine Teilmenge der Lua-Grammatik hier ausreicht, um zu zeigen, wie die Transformation funktionieren kann.
Die folgende Teilmenge (weitgehend basierend auf der Referenzgrammatik) zeigt genau die Mehrdeutigkeit, die im OP angegeben ist:
%Vor% (Hinweis: (Ich verwende Ø , um die leere Zeichenfolge darzustellen, eher ε , λ oder %empty .)
Die Lua-Grammatik ist wie links-rekursiv, also ist sie eindeutig nicht LL (k) (unabhängig von der Mehrdeutigkeit). Das Entfernen der Linksrekursion kann mechanisch erfolgen; Ich habe genug davon getan, um zu zeigen, dass die Untermenge LL (1) ist.Leider behält die transformierte Grammatik nicht die Struktur des Syntaxbaums bei, was ein klassisches Problem mit LL (k) Grammatiken ist. Es ist normalerweise einfach, den korrekten Syntaxbaum während eines rekursiven Abstiegs zu rekonstruieren, und ich werde nicht auf die Details eingehen.
Es ist einfach, eine LL (1) -Version von exp anzugeben, aber das Ergebnis beseitigt die Unterscheidung zwischen var (die zugewiesen werden kann) und function-call (was nicht möglich ist):
Aber jetzt müssen wir die Unterscheidung neu erstellen, um sowohl Zuweisungsanweisungen als auch Funktionsaufrufe analysieren zu können. Das ist einfach (aber fördert nicht das Verständnis der Syntax, IMHO):
%Vor% Um das gierige Parsen eindeutig zu machen, müssen wir (aus der Grammatik) jedes Vorkommen von S1 S2 verbieten, wobei S1 mit einem exp endet und S2 mit einem '(' beginnt Je nachdem, ob die Anweisung mit einem ( beginnt, oder unabhängig davon, ob die Anweisung mit einem exp endet, müssen wir verschiedene Arten von Anweisungen unterscheiden. (In der Praxis gibt es nur drei Typen, weil es dort keine gibt) sind keine Anweisungen, die mit einem ( beginnen und nicht mit einem exp enden. [Anmerkung 4])
In der gebräuchlichsten Verwendung ist ein prädiktiver rekursiver Descent-Parser eine Implementierung des LL (k) -Algorithmus, in dem jedes Nicht-Terminal einer Prozedur zugeordnet ist. Jede nichtterminale Prozedur beginnt mit einer Tabelle möglicher Lookahead-Sequenzen der Länge k , um zu entscheiden, welche alternative Produktion für dieses Nichtterminal zu verwenden ist, und führt dann das Produktionssymbol einfach symbolweise aus: Terminalsymbole bewirken die nächste Eingabe Symbol, das verworfen wird, wenn es übereinstimmt oder ein Fehler gemeldet wird, wenn es nicht übereinstimmt; Nicht-terminale Symbole bewirken, dass die Nicht-Terminal-Prozedur aufgerufen wird.
Die Tabellen der Lookahead-Sequenzen können mit FIRST k und FOLLOW k-Sets erstellt werden. (Eine Produktion A→ω wird einer Sequenz α von Terminals zugeordnet, wenn α ∈ FIRSTk(ω FOLLOWk(A)) .) [Anmerkung 5]
Mit dieser Definition des rekursiven Descent-Parsens kann ein rekursiver Descent-Parser genau und ausschließlich LL (k) -Sprachen behandeln. [Anmerkung 6]
Die Ausrichtung von LL (k) - und rekursiven Descent-Parsern ignoriert jedoch einen wichtigen Aspekt eines rekursiven Descent-Parsers, nämlich dass es in erster Linie ein Programm ist, das normalerweise in Turing geschrieben wird -vollständige Programmiersprache Wenn dieses Programm geringfügig von der oben beschriebenen starren Struktur abweichen darf, könnte es eine viel größere Anzahl von Sprachen parsen, sogar Sprachen, die nicht kontextfrei sind. (Siehe z. B. die C-Kontextsensitivität, auf die in Anmerkung 2 verwiesen wird.)
Insbesondere ist es sehr einfach, eine "Standard" -Regel zu einem Tabellenzuordnungs-Lookaheads zu Produktionen hinzuzufügen. Dies ist eine sehr verlockende Optimierung, da sie die Größe der Lookahead-Tabelle erheblich verringert. Im Allgemeinen wird die Standardregel für Nicht-Terminals verwendet, deren Alternativen eine leere rechte Seite umfassen, die im Falle einer LL (1) -Grammatik einem beliebigen Symbol im FOLLOW -Eintrag zugeordnet wäre das Nicht-Terminal. In dieser Implementierung enthält die Lookahead-Tabelle nur Lookaheads aus der FIRST Menge, und der Parser erzeugt automatisch eine leere rechte Seite, die einer sofortigen Rückgabe entspricht, für jedes andere Symbol. (Wie bei der ähnlichen Optimierung in LR (k) Parsern kann diese Optimierung die Erkennung von Fehlern verzögern, aber sie werden immer noch erkannt, bevor ein zusätzliches Token gelesen wird.)
Ein LL (1) -Parser kann kein Nullable-Nicht-Terminal enthalten, dessen FIRST und FOLLOW -Sätze ein gemeinsames Element enthalten. Wenn der rekursive Descent-Parser jedoch die Optimierung "Standardregel" verwendet, wird dieser Konflikt während der Konstruktion des Parsers nie bemerkt. In der Tat erlaubt die Ignorierung des Konflikts die Konstruktion eines "gierigen" Parsers aus (bestimmten) nicht-deterministischen Grammatiken.
Das ist enorm praktisch, denn wie wir oben gesehen haben, ist das Produzieren von eindeutigen gierigen Grammatiken eine Menge Arbeit und führt zu nichts, das einer klaren Darstellung der Sprache ähnelt. Der modifizierte rekursive Analysealgorithmus ist jedoch nicht leistungsfähiger. es analysiert einfach eine äquivalente SLL (k) Grammatik (ohne diese Grammatik tatsächlich aufzubauen).
Ich beabsichtige nicht, einen vollständigen Beweis für die obige Behauptung zu liefern, aber ein erster Schritt besteht darin, zu beobachten, dass jedes Nicht-Terminal als eine Disjunktion von neuen Nicht-Termen umgeschrieben werden kann, jede mit einem einzelnen FIRST Token und möglicherweise ein neues Nicht-Terminal mit einer leeren rechten Seite. Es ist dann "nur" notwendig, Nicht-Terminals aus dem FOLLOW Satz von nullbaren Nicht-Terminals zu entfernen, indem neue Disjunktionen erstellt werden.Hier spreche ich über die Grammatik, die auf einem tokenisierten Stream arbeitet, in dem Kommentare entfernt wurden und andere Konstrukte (wie Strings, die durch "lange Klammern" begrenzt sind) auf ein einzelnes Token reduziert wurden. Ohne diese Transformation wäre die Sprache nicht LL (k) (da Kommentare - die beliebig lang sein können - die Sichtbarkeit des Lookahead-Tokens beeinträchtigen). Damit kann ich auch die Frage umgehen, wie lange Brackets mit einer LL (k) Grammatik erkannt werden können, die für diese Frage nicht besonders relevant ist.
Es gibt Programmiersprachen, die von einer kontextfreien Grammatik nicht deterministisch geparst werden können. Das bekannteste Beispiel ist wahrscheinlich Perl, aber es gibt auch das bekannte C-Konstrukt (x)*y , das nur deterministisch unter Verwendung von Informationen über das Symbol% co_de% - ob es sich um einen Variablennamen oder um einen Typalias handelt - analysiert werden kann die Schwierigkeiten beim korrekten Parsen von C ++ - Ausdrücken mit Vorlagen. (Siehe zum Beispiel die Fragen Warum kann C ++ nicht mit einem LR (1) -Parser analysiert werden? und Ist C ++ kontextfrei oder kontextsensitiv? )
Der Einfachheit halber habe ich die verschiedenen literalen Konstanten (Strings, Zahlen, boolesche Werte usw.) sowie Tabellenkonstruktoren und Funktionsdefinitionen entfernt. Diese Token können nicht das Ziel eines Funktionsaufrufs sein, was bedeutet, dass ein Ausdruck, der mit einem dieser Token endet, nicht mit einem geklammerten Ausdruck erweitert werden kann. Das Entfernen von ihnen vereinfacht die Veranschaulichung der Begriffsklärung; Das Verfahren ist immer noch mit der vollen Grammatik möglich, aber es ist noch mühsamer.
Bei der vollständigen Grammatik müssen wir auch Ausdrücke berücksichtigen, die nicht mit x erweitert werden können. Daher gibt es vier verschiedene Optionen.
Es gibt deterministische LL (k) Grammatiken, die unter Verwendung dieses Algorithmus keine eindeutigen Parsingtabellen erzeugen können, welche Sippu & amp; Soisalon-Soininen nennen den Strong LL (k) -Algorithmus. Es ist möglich, den Algorithmus unter Verwendung eines zusätzlichen Parsing-Zustands zu erweitern, ähnlich dem Zustand in einem LR (k) Parser. Dies mag für bestimmte Grammatiken zweckmäßig sein, ändert jedoch nicht die Definition von LL (k) -Sprachen. Als Sippu & amp; Soisalon-Soininen demonstrieren, dass es möglich ist, mechanisch von jeder LL (k) Grammatik eine SLL (k) Grammatik abzuleiten, die genau dieselbe Sprache produziert. (Siehe Theorem 8.47 in Band 2).
Der rekursive Definitionsalgorithmus ist eine genaue Implementierung des kanonischen stackbasierten LL (k) Parsers, wobei der Parserstack implizit während der Ausführung des Parsers unter Verwendung der Kombination der aktuellen Fortsetzung und des Stacks von Aktivierungsdatensätze
Tags und Links parsing context-free-grammar lua recursive-descent ll