72 votes

Différence entre un analyseur LL et un analyseur récursif de descente?

J'ai récemment essayer de m'enseigner comment analyseurs (pour les langues/context-free grammars) de travail, et plus il semble faire sens, sauf pour une chose. Je me concentre mon attention en particulier sur LL(k) grammaires, dont les deux principaux algorithmes semblent être l' analyseur LL (à l'aide de la pile/analyser la table) et la Descente Récursive de l'analyseur (il suffit d'utiliser la récursivité).

Aussi loin que je peux voir, la descente récursive de l'algorithme fonctionne sur tous les LL(k) les grammaires et peut-être plus, alors qu'un analyseur LL fonctionne sur tous les LL(k) les grammaires. Un appel récursif à la descente de l'analyseur est clairement beaucoup plus simple qu'un analyseur LL à mettre en œuvre, cependant (un peu comme un LL, on est tout simplement qu'un LR).

Donc ma question est, quels sont les avantages et les problèmes que l'on peut rencontrer lors de l'utilisation des algorithmes? Pourquoi peut-on choisir LL plus de descente récursive, étant donné qu'il fonctionne sur le même ensemble de grammaires et est plus délicate à mettre en œuvre?

Nous espérons que cette question prend une certaine quantité de sens. Désolé si ce n'est pas - je blâme mon le fait que l'ensemble de ce sujet est presque entièrement nouveau pour moi.

94voto

Daniel Spiewak Points 30706

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.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X