Unterschied zwischen einem LL- und einem rekursiven Abstiegsparser?

Ich habe kürzlich versucht, mir selbst beizubringen, wie Parser (für Sprachen / kontextfreie Grammatiken) funktionieren, und das meiste davon scheint sinnvoll zu sein, abgesehen von einer Sache. Ich konzentriere mich insbesondere auf LL (k) -Grammatiken , für die die beiden Hauptalgorithmen der LL-Parser (unter Verwendung der Stapel- / Analysetabelle) und der Parser für rekursiven Abstieg (einfach unter Verwendung der Rekursion) zu sein scheinen .

Soweit ich sehen kann, funktioniert der rekursive Abstiegsalgorithmus für alle LL (k) -Grammatiken und möglicherweise mehr, während ein LL-Parser für alle LL (k) -Grammatiken funktioniert. Ein rekursiver Abstiegsparser ist jedoch deutlich einfacher zu implementieren als ein LL-Parser (genau wie ein LL-Parser einfacher als ein LR-Parser ist).

Meine Frage ist also, welche Vorteile / Probleme bei der Verwendung eines der Algorithmen auftreten können. Warum könnte man jemals LL über rekursiven Abstieg wählen, da es mit denselben Grammatiken arbeitet und schwieriger zu implementieren ist?

LL ist normalerweise eine effizientere Analysetechnik als rekursiver Abstieg. Tatsächlich ist ein naiver Parser mit rekursivem Abstieg im schlimmsten Fall tatsächlich O (k ^ n) (wobei n die Eingabegröße ist). Einige Techniken wie das Auswendiglernen (was einen Packrat- Parser ergibt ) können dies verbessern und die vom Parser akzeptierte Grammatikklasse erweitern, aber es gibt immer einen Kompromiss zwischen Leerzeichen. LL-Parser sind (meines Wissens) immer lineare Zeit.

Auf der anderen Seite haben Sie Recht mit Ihrer Intuition, dass Parser mit rekursivem Abstieg eine größere Klasse von Grammatiken verarbeiten können als LL. Rekursiver Abstieg kann jede Grammatik verarbeiten, die LL (*) ( dh unbegrenzter Lookahead) ist, sowie eine kleine Menge mehrdeutiger Grammatiken. Dies liegt daran, dass rekursiver Abstieg tatsächlich eine direkt codierte Implementierung von PEGs oder Parser Expression Grammatik (en) ist . Insbesondere ist der disjunktive Operator ( a | b) nicht kommutativ, was bedeutet, dass a | bdies nicht gleich ist b | a. Ein Parser mit rekursivem Abstieg versucht jede Alternative der Reihe nach. Wenn also adie Eingabe übereinstimmt, ist sie auch dann erfolgreich, wenn b sie mit der Eingabe übereinstimmt. Dies ermöglicht klassische "längste Übereinstimmungen" wie das Baumelnelse Problem einfach durch korrekte Reihenfolge der Disjunktionen zu lösen.

Nach alledem ist es möglich , einen LL (k) -Parser unter Verwendung eines rekursiven Abstiegs zu implementieren, so dass er in linearer Zeit ausgeführt wird. Dies erfolgt durch im Wesentlichen Inlining der Vorhersagesätze, so dass jede Analyseroutine die geeignete Produktion für eine gegebene Eingabe in konstanter Zeit bestimmt. Leider verhindert eine solche Technik, dass eine ganze Klasse von Grammatiken behandelt wird. Sobald wir mit dem prädiktiven Parsen beginnen, sind Probleme wie das Baumeln elsenicht mehr so ​​einfach zu lösen .

Warum LL vor rekursivem Abstieg gewählt wird, ist hauptsächlich eine Frage der Effizienz und Wartbarkeit. Parser mit rekursivem Abstieg sind deutlich einfacher zu implementieren, aber normalerweise schwieriger zu pflegen, da die von ihnen dargestellte Grammatik in keiner deklarativen Form vorhanden ist. Die meisten nicht trivialen Parser-Anwendungsfälle verwenden einen Parser-Generator wie ANTLR oder Bison. Bei solchen Tools spielt es keine Rolle, ob der Algorithmus direkt codierter rekursiver Abstieg oder tabellengesteuertes LL (k) ist.

Interessanterweise lohnt es sich auch, den rekursiven Aufstieg zu untersuchen. Hierbei handelt es sich um einen Parsing-Algorithmus, der direkt nach der Art des rekursiven Abstiegs codiert ist, jedoch jede LALR-Grammatik verarbeiten kann. Ich würde mich auch mit Parser-Kombinatoren befassen, die eine funktionale Möglichkeit sind, Parser mit rekursivem Abstieg zusammenzustellen.