Welche modernen Computersprachen sind LL (1)?

Ich denke, ich wäre versucht, dieses Wikipedia-Zitat mit [Zitat benötigt] zu kennzeichnen; Die Annahmen sind zumindest fragwürdig. Zum Beispiel gibt es eine große Anzahl von Compiler-Konstruktionstools basierend auf yacc , die es in der Praxis extrem einfach machen konstruiere einen Parser unter Verwendung des leistungsstärkeren (und ebenso schnellen) LALR-Algorithmus, und einige implementieren auch den GLR-Algorithmus mit noch mehr Leistung (und fast so schnell in den meisten praktischen Grammatiken). Handschrift Parser war seit Jahrzehnten nicht notwendig. [Anmerkung 1]

Um eine Antwort auf die Frage zu versuchen:

1. Die meisten Computersprachen sind "technisch" nicht LL, weil sie nicht einmal kontextfrei sind. Dazu gehören Sprachen, die die Angabe von Bezeichnern erfordern (C, C ++, C #, Java usw.), sowie Sprachen mit Präprozessoren und / oder Makrofunktionen (ua C und C ++), Sprachen mit Mehrdeutigkeiten, die nur sein können gelöst mit semantischen Informationen (Perl wäre hier der schlimmste Täter, aber auch C und C ++ sind da oben). Und um die Freude noch weiter zu verbreiten, enthält es auch Sprachen, die Python-ähnliche Layout-Kenntnisse haben (natürlich Python und auch Haskell).

   Ich setze Angstzitate um "technisch", weil es viele Leute gibt, die sagen, dass diese Ausnahmen "nicht zählen". Das ist ihre Meinung, und sie haben Anspruch darauf (und sowieso habe ich es aufgegeben, darüber zu streiten, obwohl ich diese Meinung nicht teile). Sie könnten beispielsweise den Präprozessor aus C / C ++ entfernen, indem Sie den Text vor dem Anwenden der Grammatik vorbearbeiten, oder indem Sie whitespace-fähige Sprachen vorverarbeiten, indem Sie statt des Whites Leerzeichen einfügen, NEWLINE und DEDENT, nach denen Sie eine Art von Anspruch erheben könnten über eine mystische "Kernsprache". (Das ist viel schwieriger auf C ++ - Vorlagen anzuwenden, was nur durch das Parsen des Textes behoben werden kann, so dass Sie nicht behaupten können, dass die Erweiterung vor dem Parsing durchgeführt werden kann.)

   Die Behauptung, dass eine Sprache nicht kontextfrei ist, weil die Angabe von Bezeichnern erforderlich ist, ist vielleicht ein wenig umstrittener. In einigen Sprachen (nicht in C / C ++, in denen die semantische Analyse zur Vermeidung von Mehrdeutigkeiten erforderlich ist) könnten Sie argumentieren, dass ein Syntaxbaum konstruiert werden könnte, ohne die Deklarationsregel zu validieren, wodurch diese Regel "nicht syntaktisch" wird. Es bleibt jedoch der Fall, dass Sie die Deklarationsregel syntaktisch durchsetzen können; Sie können es einfach nicht mit einer kontextfreien Grammatik machen (Sie können beispielsweise eine Van Wijngaarden Grammatik verwenden).

   In jedem Fall besteht eine gängige Syntaxanalyse darin, eine Obermenge einer Sprache zu erkennen und dann nichtkonforme Programme durch eine nachfolgende Analyse des resultierenden Syntaxbaums abzulehnen; In diesem Fall stellt sich die Frage, ob die Obermenge LL ist oder nicht. Meiner Meinung nach ist es notwendig, damit jedes gültige Programm in den korrekten Syntaxbaum zerlegt werden kann, was die Verwendung semantischer Analyse zur Disambiguierung überflüssig macht.

2. Das Ziel des Parsens besteht darin, einen Syntaxbaum zu erzeugen, nicht nur um zu erkennen, ob ein Text gültig ist oder nicht. (Sie könnten diese wichtige Tatsache übersehen, wenn Sie formale Sprachlehrbücher überfliegen, die sich auf die Erkennung konzentrieren, möglicherweise weil die Konstruktion von Syntaxbäumen weniger interessant ist.) Es scheint daher vernünftig zu sein, darauf zu bestehen, dass eine vorgeschlagene Grammatik tatsächlich die syntaktische Struktur darstellt der Sprache.

   Sie können beispielsweise algebraische Ausdrücke mit einer einfachen regulären Sprache erkennen:

   %Vor%

   wobei PREFIX die Menge der Präfixoperatoren sowie ( ist, POSTFIX die Menge der Postfixoperatoren (falls vorhanden) sowie ) ist, INFIX die Menge der Infixoperatoren (Addition, Subtraktion, Multiplikation, usw.), und OPERAND ist ein Identifikator oder eine Konstante.

   Dieser reguläre Ausdruck lehnt Ausdrücke mit unsymmetrischen Klammern nicht korrekt ab, aber wir waren uns bereits einig, dass es OK war, eine Obermenge der Sprache zu erkennen, richtig? : -)

   Falls gewünscht, könnten wir die Klammern aus den PREFIX- und POSTFIX-Sets entfernen und OPERAND zu einer rekursiven Produktion machen. Die resultierende Grammatik ist trivialerweise LL (1) [Anmerkung 2]:

   %Vor%

   Das Problem besteht jedoch darin, dass diese Grammatik die Vorrangstellung des Operators nicht erfasst. Es versucht nicht einmal, die Tatsache zu erkennen, dass a+b*c und a*b+c beide Summen sind, so dass der Operator auf oberster Ebene in beiden Fällen + ist und nicht der Operator, der im Ausdruck zuerst kommt. (Wenn Sie APL analysieren würden, wäre das kein Problem. Die meisten Sprachen entsprechen jedoch den üblichen Erwartungen bezüglich der Rangfolge der Operatoren.)

   Dieser Punkt ist wichtig, da eine LL-Grammatik keine linksrekursiven Produktionen verarbeiten kann und Sie eine linksorientierte Produktion benötigen, um einen linksassoziativen Operator korrekt analysieren zu können.(Das heißt, a-b-c korrekt als ((a-b)-c) statt (a-(b-c)) zu analysieren, was einen anderen Wert hätte.) Auch hier könnte man argumentieren, dass dies ein Fehler ist, da Sie den Parse-Baum der Reihe nach nachbearbeiten könnten um die Assoziativität zu korrigieren. Dies ist sicherlich richtig, aber das Ergebnis ist, dass die Grammatik, die Sie zum parse verwenden, anders ist als die Grammatik, mit der Sie die Syntax der Sprache erklären. Das könnte oder könnte dich nicht stören.

   Es lohnt sich hier hinzuzufügen, dass es Sprachen gibt (Haskell, Prolog, wahrscheinlich viele mehr), in denen Sie im Programmtext Operatoren und ihre Priorität definieren können. Dies macht es offensichtlich unmöglich, einen korrekten Syntaxbaum ohne semantische Analyse zu erzeugen, und der übliche Ansatz zum Parsen solcher Sprachen besteht darin, genau die vereinfachte Sprache "alternierender Operand und Operator" zu verwenden, die oben umrissen wurde. Sobald die Operatorvorgaben alle bekannt sind, vermutlich am Ende des Parsens, werden alle Ausdrücke erneut unter Verwendung von etwas wie dem Shunting Yard-Algorithmus analysiert, um das korrekte Parsen zu erzeugen.

3. Nehmen wir an, wir verwerfen die obigen Einwände und fragen einfach "für welche gängigen Programmiersprachen könnte ein LL-Parser verwendet werden?"

   Um jedoch Betrug zu vermeiden, sollten wir wirklich verlangen, dass der LL-Parser ein festes Lookahead hat und kein Backtracking benötigt. Wenn Sie willkürliches Lookahead und Backtracking zulassen, erweitern Sie die Domäne der analysierbaren Sprachen beträchtlich, aber ich behaupte, dass Sie nicht mehr im Bereich von LL sind. Das wird zum Beispiel die Template- und Präprozessor-freie Teilmenge von C ++ eliminieren, obwohl die üblichen Compiler-Implementierungen rekursive Descent-Parser verwenden, da Backtracking erforderlich ist, um die " Most Vexing Parse " Mehrdeutigkeit. (Wie auch immer, Sie können Templates nicht wirklich aus C ++ entfernen, und die Analyse mit Templates ist wirklich schwer. [Anmerkung 3])

   Java und Python wurden beide als LL (1) "Pseudo-Parseable" entworfen. Ich glaube, Haskell fällt ebenfalls in diese Kategorie. C kann nicht ohne semantische Informationen syntaktisch analysiert werden (klassische Ambiguität: ist (x)*(y) ein Cast oder eine Multiplikation? - es hängt davon ab, ob x typedefiniert oder als Variable deklariert wurde), aber ich bin mir ziemlich sicher, dass es möglich ist mit einem nicht-zurückverfolgenden rekursiven Abstiegsparser erfasst werden. Ich habe C # nicht eingehend studiert, aber diese Antwort von Eric Lippert legt nahe, dass es in einigen Fällen ein Backtracking erfordert.

Notizen

1. Natürlich tun es die Leute immer noch, und in vielen Fällen aus guten Gründen (zum Beispiel, um bessere Fehlermeldungen zu erzeugen). Aber "es ist schwierig, einen LALR-Parser zu konstruieren" ist nicht ein guter Grund, da es nicht ist.

2. Das ist nicht ganz LL, weil ich nicht links gegangen bin. Aber es ist leicht genug zu tun; Ich werde es als Übung verlassen.

3. Siehe Ist C ++ kontextfrei oder kontextsensitiv ? . Auch Todd Veldhuizens klassische C ++ - Vorlagen sind Turing abgeschlossen