Qu'est-ce que l'analyse sans scanner a à voir avec le «autre problème pendant»?

Je ne comprends pas cette phrase de l'article Wikipedia sur le problème Dangling Else :

[Le problème Dangling Else] est un problème qui survient souvent dans la construction du compilateur, en particulier l'analyse sans scanner.

Quelqu'un peut-il m'expliquer comment les techniques d'analyse sans scanner peuvent aggraver ce problème? Il me semble que le problème vient de la grammaire - car elle est ambiguë - et non du choix de la technique d'analyse. Qu'est-ce que je rate?

Ma meilleure supposition est que la phrase de l'article Wikipedia résulte d'une mauvaise compréhension du travail d'E. Visser.

Les grammaires pour les analyseurs sans scanner (c'est-à-dire les grammaires décrivant une langue comme un ensemble de séquences de caractères au lieu d'un ensemble de séquences de jetons avec les jetons décrits séparément comme des chaînes de caractères) ont tendance à avoir beaucoup d'ambiguïtés. E. Visser paper Desambiguation Filters for Scannerless Generalized LR Parsers (*) propose plusieurs mécanismes pour résoudre les ambiguïtés, dont l'un est utile pour résoudre le problème de balancement ailleurs. Mais le document n'indique pas que l'ambiguïté précise nommée "problème de balancement d'autre chose" est liée aux analyseurs sans scanner (ni même que le mécanisme est particulièrement utile pour les analyseurs sans scanner).

Le fait qu'il propose un mécanisme pour le résoudre n'est pas une déclaration implicite car un autre mécanisme de résolution d'ambiguïté (priorité et priorité de l'opérateur) semble également totalement indépendant de la nature sans scanner des analyseurs analysés (considérez par exemple que ces ambiguïtés ne peuvent pas être présents dans les grammaires régulières car ils résultent de l'imbrication, tandis que ceux traités par une règle de correspondance la plus longue peuvent).

(*) Qui est probablement l'article servant de base à l'article de Wikipedia sur les analyseurs sans scanner même s'ils en font référence à un autre, également par E. Visser, Scannerless Generalized-LR Parsing .

Juste pour énoncer le problème, le problème Dangling Else est une ambiguïté dans la spécification de la syntaxe du code où il peut ne pas être clair, dans le cas des ifs et des elses suivants, qui appartient à quel autre if.

L'exemple le plus simple et classique:

if(conditionA)
if(conditionB)
   doFoo();
else
   doBar();

Il n'est pas clair, pour ceux qui ne connaissent pas par cœur les spécificités de la spécification du langage, qui ifobtient le else(et cet extrait de code particulier est valide dans une demi-douzaine de langues, mais peut fonctionner différemment dans chacun).

La construction Dangling Else pose un problème potentiel pour les implémentations de l'analyseur sans scanner, car la stratégie consiste à accélérer le flux de fichiers un caractère à la fois, jusqu'à ce que l'analyseur voit qu'il a suffisamment de jetons (digest dans l'assembly ou le langage intermédiaire qu'il compile) . Cela permet à l'analyseur de maintenir un état minimal; dès qu'il pense avoir suffisamment d'informations pour écrire les jetons qu'il a analysés dans le fichier, il le fera. C'est l'objectif final d'un analyseur sans scanner; compilation rapide, simple et légère.

En supposant que les nouvelles lignes et les espaces avant ou après la ponctuation n'ont pas de sens (comme ils le sont dans la plupart des langages de style C), cette déclaration apparaîtra au compilateur comme:

if(conditionA)if(conditionB)doFoo();else doBar;

Parfaitement analysable sur un ordinateur, alors voyons. J'obtiens un personnage à la fois jusqu'à ce que j'aie:

if(conditionA)

Oh, je sais ce que cela signifie (en C #), cela signifie " pushconditionA sur la pile eval et ensuite appeler brfalsepour passer à l'instruction après le point-virgule suivant si ce n'est pas vrai". Pour le moment, je ne vois pas de point-virgule, donc pour l'instant je vais définir mon décalage de saut à l'espace suivant après cette instruction, et je vais incrémenter ce décalage lorsque j'insérerai plus d'instructions jusqu'à ce que je vois un point-virgule. Continuer d'analyser ...

if(conditionB)

OK, cela analyse une paire similaire d'opérations IL, et cela va immédiatement après l'instruction que je viens d'analyser. Je ne vois pas de point-virgule, donc je vais incrémenter le décalage de saut de ma déclaration précédente de la longueur de mes deux commandes (une pour la poussée et une pour la pause) et continuer à chercher.

doFoo();

Ok, c'est facile. C'est " calldoFoo". Et est-ce un point-virgule que je vois? Eh bien, c'est super, c'est la fin de la ligne. Je vais incrémenter les décalages de saut de mes deux blocs de la longueur de ces deux commandes et oublier que je m'en suis jamais soucié. OK, continuons ...

else

... Uh-oh. Ce n'est pas aussi simple qu'il y paraissait. OK, j'ai oublié ce que je faisais juste, mais cela elsesignifie qu'il y a une déclaration de pause conditionnelle quelque part que j'ai déjà vue, alors laissez-moi regarder en arrière ... oui, ça y est brfalse, juste après avoir poussé une "conditionB" sur la pile, quelle qu'elle soit. OK, maintenant j'ai besoin d'un inconditionnel breakcomme déclaration suivante. La déclaration qui viendra après cela est maintenant définitivement mon objectif de pause conditionnelle, donc je vais m'assurer que je l'ai bien, et je vais incrémenter la pause inconditionnelle que j'ai mise.

doBar();

C'est facile. " calldoBar". Et il y a un point-virgule, et je n'ai jamais vu d'accolades. Donc, l'inconditionnel breakdevrait passer à la déclaration suivante, quelle qu'elle soit, et je peux oublier que je m'en suis jamais soucié.

Alors, qu'avons-nous ... (note: il est 22h00 et je n'ai pas envie de convertir des décalages de bits en hexadécimal ou de remplir le shell IL complet d'une fonction avec ces commandes, donc c'est juste du pseudo-IL en utilisant des numéros de ligne où il y aurait normalement des décalages d'octets):

ldarg.1 //conditionA
brfalse <line 6> //jumps to "break"
ldarg.2 //conditionB
brfalse <line 7> //jumps to "call doBar"
call doFoo
break <line 8> //jumps beyond statement in scope
call doBar
<line 8 is here>

Eh bien, cela s'exécute correctement, SI la règle (comme dans la plupart des langages de style C) est que le elseva avec le plus proche if. Indenté pour suivre l'imbrication d'exécution, il s'exécuterait comme ceci, où si conditionA est fausse, le reste de l'extrait est ignoré:

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();

... mais il le fait par hasard, car la coupure associée à l' ifinstruction externe saute à l' breakinstruction à la fin de l' interne if , ce qui prend le pointeur d'exécution au-delà de l'instruction entière. C'est un saut supplémentaire inutile, et si cet exemple était plus complexe, il pourrait ne plus fonctionner s'il était analysé et symbolisé de cette façon.

De plus, que se passe-t-il si la spécification du langage dit qu'un balancement elseappartient au premier if, et si conditionA est fausse, alors doBar est exécuté, tandis que si conditionA est vraie mais pas conditionB alors rien ne se passe, comme ça?

if(conditionA)
    if(conditionB)
       doFoo();
else
   doBar();

L'analyseur avait oublié que le premier ifexistait, et donc ce simple algorithme d'analyseur ne produirait pas de code correct, pour ne rien dire de code efficace.

Maintenant, l'analyseur pourrait être assez intelligent pour se souvenir des ifs et elses qu'il a pendant plus longtemps, mais si la spécification de langue dit un seul elseaprès deux ifs correspond au premier if, cela pose un problème avec deux ifs avec elses correspondant :

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();
else
    doBaz();

L'analyseur verra le premier else, correspondra au premier if, puis verra le second et paniquera le mode "que diable fais-je encore". À ce stade, l'analyseur a plutôt obtenu beaucoup de code dans un état modifiable qu'il aurait de préférence préféré diffuser dans le flux de fichiers de sortie.

Il existe des solutions à tous ces problèmes et à toutes les hypothèses. Mais, soit le code devait être intelligent pour augmenter la complexité de l'algorithme de l'analyseur, soit la spécification de langue permettant à l'analyseur d'être aussi stupide augmente la verbosité du code source de la langue, par exemple en exigeant des instructions de terminaison comme end if, ou des crochets indiquant l'imbrication bloque si l' ifinstruction a un else(les deux étant couramment vus dans d'autres styles de langage).

Ce n'est qu'un exemple simple de quelques ifdéclarations, et regardez toutes les décisions que le compilateur a dû prendre, et où il aurait très facilement pu gâcher de toute façon. C'est le détail derrière cette déclaration inoffensive de Wikipedia dans votre question.