LL-Grammatiken und linke Recursivität

Question

Warum sind LL (k) und LL (∞) mit der linken Rezeption unvereinbar? Ich verstehe, dass eine LL (K) -Proke die linke Rekursivität unterstützen kann, vorausgesetzt, dass mit K-OverAead-Token jegliche Mehrdeutigkeit gelöst werden kann. Aber welche Art von Unklarheiten können mit einer LL (∞) -Kegrammatik nicht gelöst werden?

Answer 1

Das Problem, dass $ ll $ Varianten mit der linken Rekursion die Art und Weise inhärent sind, wie $ ll $ funktioniert: Es handelt sich um einen Parser von Top-Down-Typ, was bedeutet, dass es Nicht-Terminals durch ihre Produktionen ersetzt.

Ein Parser im Stil von $ ll $ im Stil funktioniert wie folgt. Es durchquert die Eingabe von links nach rechts auf einmal. Wenn wir uns irgendwann in der Eingabe befinden, wissen wir, dass alles links von diesem Punkt in Ordnung ist. Für alles rechts von diesem Punkt hat der Parser eine "Annäherung" dessen erstellt, was er als nächstes erwartet. Betrachten Sie zum Beispiel diese Grammatik:

1: $ e bis e + e $
2: $ e bis x $

Beachten Sie, dass die Grammatik nicht $ ll $ ist, aber wir können immer noch Inputs in $ ll $ -Style analysieren. Bei Input $ x+x+x $ kann ein Parser im Stil von $ ll $ im Stil $ $ x+ Bullet x+x $ enden. Nehmen wir an, es hat beschlossen, dass der linke Teil $ x+$ in Ordnung ist, und für den Rest des Eingangs wird es erwartet, $ x+e $ zu sehen. Es wird dann herausfinden, dass $ x+x+$ in Ordnung ist, mit $ e $ verbleiben. Es kann dann diese $ e $ durch eine Produktion ersetzen, insbesondere durch Produktion 2 oben. Mit $ x $ wird der Parser die Eingabe akzeptiert.

Der Trick besteht dann darin, die Ersatzproduktion für einen bestimmten Nicht -terminalen Ersatz korrekt zu entscheiden. Eine Grammatik ist $ ll (k) $, wenn wir dies tun können, indem wir uns nur die nächsten $ K $ -Input -Symbole ansehen, und andere Techniken sind bekannt, die leistungsfähiger sind.

Betrachten Sie nun die folgende Grammatik:

1: $ a bis a $ $
2: $ a bis varepsilon $

Wenn ein $ ll $ parser versucht, $ A $ durch eine Produktion zu ersetzen, muss er zwischen der Produktion 1 und 2 entscheiden.

Überlegen wir, was die richtige Vorgehensweise sein würde, wenn unser Parser allwissend wäre. Jedes Mal, wenn es die $ a $ durch Produktion 1 ersetzt, "fügt" ein $ a $ zu dem hinzu, was es für den verbleibenden Input erwartet (der erwartete Rest geht von $ $ $ $ aa $ $ $ AAA $ ...). Aber die $ a $ am Start verschwinden nicht. Schließlich muss es Production 2 auswählen, danach verschwindet die $ a $ und es kann nie wieder $ a $ S zur Erwartung hinzufügen.

Da es keine Chance gibt, ein paar weitere Eingangssymbole zu erreichen, muss der Parser genau in dieser Eingabeposition entscheiden, wie oft Produktion 1 übereinstimmt. Dies bedeutet, dass es genau wissen muss, wie oft in unserem Fall die $ a $ im Rest des Inputs in diesem Moment erscheinen werden.

$ Ll (k) $ kann jedoch nur $ K $ -Symbole vor sich sehen. Dies bedeutet, dass der Parser dies nicht sehen kann, wenn die Produktion 1 mehr als $ k $ -mal ausgewählt werden muss, und daher zum Scheitern verurteilt wird. $ Ll (*) $ kann besser analysieren als $ ll (k) $, da es in der Eingabe willkürlich weit voraus sehen kann, aber das entscheidende Detail (das nicht immer erwähnt wird) ist, dass diese Lookahead ist regulär.

Um sich vorzustellen, was passiert, können Sie den Algorithmus wie folgt betrachten: Wenn er entscheiden muss, welche Produktion Sie einnehmen müssen, startet er eine endliche Zustandsmaschine (eine DFA, die regelmäßigen Ausdrücken entspricht) und lässt diese Maschine das betrachten Rest des Eingangs. Diese Maschine kann dann "diese Produktion verwenden" melden. Diese Maschine ist jedoch stark eingeschränkt in dem, was sie kann. Obwohl es streng besser ist, als nur die nächsten $ k $ -Symbole zu betrachten, kann es zum Beispiel "zählen", was bedeutet, dass es in der obigen Situation nicht helfen kann.

Selbst wenn Sie in einer Zählfunktion in diesem endlichen Automaten "hacken" würden, gibt es immer noch linksrekursive Grammatiken, für die Sie wirklich mehr Strom benötigen. Zum Beispiel für diese Grammatik:

$ A bis ab $
$ A bis varepsilon $
$ B bis (b) $
$ B bis varepsilon $

Sie müssten sich mit 'Türmen' von passenden Zahnspangen anpassen, was ein endlicher Automat nicht kann. Schlimmer noch:

$ A bis bcade $
$ A zu a '$
$ A ' to a' de $
$ A ' bis varepsilon $
$ B bis a b a mid b b b b b mid aa mid bb $
$ C bis c c c mid d c d mid cc mid dd $
$ D bis e d e mid f d f mid ee mid ff $
$ E bis g e g mid h e h mid gg mid hh $

ist eine völlig schreckliche Grammatik, für die ich mir ziemlich sicher bin, dass keine lineare Zeitsparalgorithmus -Werke und alle bekannten allgemeinen Parsing -Algorithmen quadratische Zeit haben. Schlimmer noch, jede Grammatik, die diese Sprache beschreibt, ist notwendigerweise linksrekursiv. Die Grammatik ist jedoch immer noch eindeutig. Sie brauchen einen handgefertigten Parser, um diese Monster in linearer Zeit zu analysieren.