Lors de la construction d'un analyseur syntaxique vers un langage de programmation, ce que je gagne et ce que j'ai perdu en choisissant l'un ou l'autre?
comparison
compiler
Maniero
la source
la source
Réponses:
Je vais comparer l'analyse LL et LR pour un certain nombre de critères:
Complexité
LL gagne ici, haut la main. Vous pouvez facilement écrire à la main un analyseur LL. En fait, cela se fait couramment: le compilateur Microsoft C # est un analyseur de descente récursif manuscrit (source ici , recherchez un commentaire de Patrick Kristiansen - le blog est également très intéressant).
L'analyse LR utilise une méthode plutôt contre-intuitive pour analyser un texte. Cela fonctionne, mais il m'a fallu un certain temps pour comprendre comment cela fonctionne exactement. Il est donc difficile d'écrire un tel analyseur à la main: vous implémenteriez plus ou moins un générateur d'analyseur LR.
Généralité
LR gagne ici: toutes les langues LL sont des langues LR, mais il y a plus de langues LR que de langues LL (une langue est une langue LL si elle peut être analysée avec un analyseur LL, et une langue est une langue LR si elle peut être analysée avec un analyseur LR).
LL a assez peu de nuisances qui va vous embêter la mise en œuvre à peu près tout langage de programmation. Voir ici pour un aperçu.
Il existe des langues non ambiguës qui ne sont pas des langues LR, mais celles-ci sont assez rares. Vous ne rencontrez presque jamais de telles langues. Cependant, LALR a quelques problèmes.
LALR est plus ou moins un hack pour les analyseurs LR pour rendre les tables plus petites. Les tables d'un analyseur LR peuvent généralement devenir énormes. Les analyseurs LALR renoncent à la capacité d'analyser tous les langages LR en échange de tables plus petites. La plupart des analyseurs LR utilisent réellement LALR (mais pas en secret, vous pouvez généralement trouver exactement ce qu'il implémente).
Le LALR peut se plaindre des conflits de réduction et de réduction des déplacements. Cela est dû au piratage de la table: il «replie» des entrées similaires ensemble, ce qui fonctionne car la plupart des entrées sont vides, mais lorsqu'elles ne le sont pas, cela génère un conflit. Ces types d'erreurs ne sont pas naturels, difficiles à comprendre et les correctifs sont généralement assez étranges.
Erreurs du compilateur et récupération d'erreurs
LL gagne ici. Dans une analyse LL, il est généralement assez facile d'émettre des erreurs de compilation utiles, en particulier dans les analyseurs manuscrits. Vous savez ce que vous attendez ensuite, donc si cela ne se produit pas, vous savez généralement ce qui s'est mal passé et quelle serait l'erreur la plus sensible.
De plus, dans l'analyse LL, la récupération d'erreur est beaucoup plus facile. Si une entrée n'analyse pas correctement, vous pouvez essayer de sauter un peu et déterminer si le reste de l'entrée est correctement analysé. Si, par exemple, une instruction de programmation est mal formée, vous pouvez passer à l'étape suivante et analyser l'instruction suivante, afin de pouvoir détecter plus d'une erreur.
L'utilisation d'un analyseur LR est beaucoup plus difficile. Vous pouvez essayer d'augmenter votre grammaire afin qu'elle accepte les entrées erronées et imprime des erreurs dans les domaines où les choses ont mal tourné, mais cela est généralement assez difficile à faire. La chance que vous vous retrouvez avec une grammaire non LR (ou non LALR) augmente également.
La vitesse
La vitesse n'est pas vraiment un problème avec la façon dont vous analysez votre entrée (LL ou LR), mais plutôt la qualité du code résultant et l'utilisation des tables (vous pouvez utiliser des tables pour LL et LR). LL et LR sont donc comparables à cet égard.
Liens
Voici un lien vers un site contrastant également LL et LR. Recherchez la section près du bas.
Ici vous pouvez trouver une conversation concernant les différences. Ce n'est pas une mauvaise idée de regarder d'un œil critique les opinions exprimées là-bas, il y a un peu de guerre sainte qui s'y déroule.
Pour plus d'informations, voici et voici deux de mes propres articles sur les analyseurs, bien qu'ils ne concernent pas strictement le contraste entre LL et LR.
la source