LL est généralement plus efficace de l'analyse technique que récursive de la descente. En fait, un naïf récursive de la descente de l'analyseur sera effectivement en O(k^n) (où n est la taille de saisie) dans le pire des cas. Certaines techniques, telles que memoization (qui donne un Packrat analyseur) peut améliorer ce ainsi que de prolonger la classe de grammaires accepté par l'analyseur, mais il y a toujours un espace de compromis. LL analyseurs sont (à ma connaissance) toujours le temps linéaire.
Sur le revers de la médaille, vous avez raison de votre intuition qui récursive de la descente des analyseurs peuvent traiter une plus grande classe de grammaires que LL. Récursive de la descente peut gérer n'importe quelle grammaire est LL(*) (qui est, illimité d'anticipation) ainsi que d'un petit ensemble de grammaires ambiguës. C'est parce que récursive de la descente est en fait un directement codé de la mise en œuvre des Chevilles, ou un Analyseur de l'Expression de la Grammaire(s). Plus précisément, l'opérateur disjonctif (a | b
) n'est pas commutatif, ce qui signifie qu' a | b
n'est pas égal à b | a
. Un appel récursif à la descente de l'analyseur va essayer chaque alternative dans l'ordre. Donc, si a
correspond à l'entrée, il va tactique soit payante même si b
aurait correspondait à l'entrée. Cela permet classique "le plus long match" ambiguïtés comme le balançant else
problème à être traitées simplement par la commande de disjonctions correctement.
Avec tout cela étant dit, il est possible de mettre en œuvre un LL(k) de l'analyseur à l'aide de récursive de la descente de sorte qu'il s'exécute en temps linéaire. Ceci est fait pour l'essentiel par l'in-lining le prédire ensembles, de sorte que chaque parse routine qui détermine la production pour une entrée donnée en temps constant. Malheureusement, cette technique élimine toute une classe de grammaires d'être traités. Une fois que nous obtenons dans l'analyse prédictive, des problèmes comme les balançant else
ne sont plus solvables, avec une telle facilité.
Quant à savoir pourquoi LL serait choisi plus de récursive de la descente, c'est essentiellement une question d'efficacité et de facilité de maintenance. Récursive de la descente analyseurs sont nettement plus facile à mettre en œuvre, mais ils sont généralement plus difficiles à maintenir, puisque la grammaire qu'ils représentent n'existe pas de forme déclarative. La plupart des non-trivial analyseur cas d'utilisation d'employer un analyseur générateur comme ANTLR ou de Bison. Avec de tels outils, il n'a vraiment pas d'importance si l'algorithme est directement codé récursive de la descente ou de la table-driven LL(k).
Comme une question d'intérêt, il est également utile dans la recherche récursive de l'ascension, qui est un algorithme d'analyse d'encodées directement après le mode de récursive de la descente, mais capable de traiter toute la grammaire LALR. Je voudrais également creuser dans l'analyseur combinators, qui sont une fonctionnel manière de composer récursive de la descente des analyseurs ensemble.