Étudie actuellement des grammaires sans contexte et des méthodes pour les analyser. D'après ma compréhension, les grammaires sans contexte peuvent être analysées via top down/LL ou bottom up/LR. Est-il correct de comprendre que les analyseurs LL exigent que les grammaires aient des règles de production strictement non ambiguës avant de pouvoir être analysées ? Et que les parseurs LR, d'autre part, exigent également que les grammaires soient sans ambiguïté, mais au lieu d'avoir à réécrire des règles de production ambiguës, des règles de priorité supplémentaires peuvent être ajoutées aux règles de production pour résoudre leur ambiguïté ? Mais comment l'avenir s'intègre-t-il dans tout cela ?

1
84d7dc197 22 oct. 2020 à 19:00

1 réponse

Meilleure réponse

D'après ma compréhension, les grammaires sans contexte peuvent être analysées via top down/LL ou bottom up/LR.

Oui, l'analyse LL fonctionne de haut en bas. L'analyse LR est généralement considérée comme une approche d'analyse ascendante, bien que certains auteurs la considèrent comme un hybride de haut en bas et de bas en haut, car elle utilise le contexte de ce qui peut apparaître où dans un arbre d'analyse généré.

Est-il correct de comprendre que les analyseurs LL exigent que les grammaires aient des règles de production strictement non ambiguës avant de pouvoir être analysées ?

Les parseurs LL ne fonctionnent que pour les grammaires non ambiguës. Les classes les plus courantes d'analyseurs LL (LL(1), LL(*)) ne fonctionnent pas sur toutes les grammaires et nécessitent des restrictions supplémentaires au-delà du fait que la grammaire est sans ambiguïté. Par exemple, les parseurs LL(1) ne peuvent pas gérer la récursivité à gauche.

Et que les parseurs LR, d'autre part, exigent également que les grammaires soient sans ambiguïté, mais au lieu d'avoir à réécrire des règles de production ambiguës, des règles de priorité supplémentaires peuvent être ajoutées aux règles de production pour résoudre leur ambiguïté ?

Oui et non. Il est vrai que, comme les parseurs LL, les types les plus courants d'analyseurs LR (LR(0), SLR(1), LALR(1), LR(1), IELR(1)) nécessitent que la grammaire soit sans ambiguïté. Vous avez raison de dire que de nombreuses ambiguïtés peuvent être résolues avec des déclarations de priorité qui brisent des grammaires autrement ambiguës, mais cela ne peut pas résoudre toutes les ambiguïtés. De plus, certaines grammaires non ambiguës ne peuvent être analysées par aucun analyseur LR(k).

Mais comment l'avenir s'intègre-t-il dans tout cela ?

L'ajout de l'anticipation à un analyseur LL ou LR donne à l'analyseur plus de contexte pour décider des règles de production à appliquer (pour les analyseurs LL) ou s'il faut décaler ou réduire (analyseurs LR). Intuitivement, être capable de voir plus loin dans la séquence de jetons permet à l'analyseur d'exclure certaines options qui ne pourraient pas fonctionner car elles ne pourraient pas correspondre à ce qui vient ensuite. Les règles spécifiques concernant le fonctionnement de cette anticipation dépendent de l'algorithme d'analyse ; par exemple, LR(2 ) les parseurs ont quelques nuances qui n'apparaissent pas dans les parseurs LR(1). Vous trouverez probablement les informations que vous recherchez en lisant spécifiquement sur l'analyse LL(1), l'analyse LR(0) et l'analyse LR(1) et vous pouvez l'utiliser comme point de lancement.

0
Dharman 22 oct. 2020 à 18:54