Comment l'algorithme LALR(1) de yacc/bison traite-t-il les règles "vides" ?

Question

Dans un analyseur LALR(1), les règles de la grammaire sont converties en une table d'analyse qui dit effectivement "Si vous avez cette entrée jusqu'ici, et que le token lookahead est X, alors passez à l'état Y, ou réduisez par la règle R".

J'ai réussi à construire un analyseur LALR(1) dans un langage interprété (ruby), sans utiliser de générateur, mais en calculant une table d'analyse à l'exécution et en évaluant l'entrée en utilisant cette table d'analyse. Cela fonctionne étonnamment bien et la génération de la table est assez triviale (ce qui m'a quelque peu surpris), supportant les règles autoréférentielles et l'association gauche/droite.

Cependant, j'ai du mal à comprendre comment yacc/bison traite conceptuellement les définitions de règles vides. Mon analyseur syntaxique ne peut pas les gérer, car en générant la table, il examine chaque symbole dans chaque règle, de manière récursive, et "vide" n'est tout simplement pas quelque chose qui viendra du lexer, ni qui sera réduit par une règle. Alors, comment les analyseurs LALR(1) traitent-ils la règle vide ? La traitent-ils spécialement, ou est-ce un concept "naturel" avec lequel un algorithme valide devrait simplement travailler, sans même avoir besoin d'avoir une conscience particulière d'un tel concept ?

Par exemple, une règle qui peut faire correspondre un nombre quelconque de parenthèses appariées sans rien au milieu :

expr:   /* empty */
      | '(' expr ')'
      ;

Une entrée comme la suivante correspondrait à cette règle :

((((()))))

Cela signifie qu'à la lecture de '(' et à la vue de ')' dans le token lookahead, l'analyseur choisit :

1. Décalez le ')' (pas possible)
2. Réduire l'entrée selon une autre règle (pas possible)
3. Autre chose...

ne correspondent pas tout à fait à l'algorithme de base de "shift" ou "reduce". L'analyseur syntaxique a effectivement besoin de ne rien déplacer sur la pile, de réduire "rien" en expr puis déplace le jeton suivant ')' donnant '(' expr ')' qui se réduit bien sûr à expr et ainsi de suite.

C'est le "shift nothing" qui me perturbe. Comment la table d'analyse syntaxique transmet-elle un tel concept ? Considérez également qu'il devrait être possible d'invoquer une action sémantique qui renvoie une valeur à $$ sur la réduction de la valeur vide, donc une vue plutôt simpliste de juste sauter cela de la table d'analyse et de dire que '(' sur la pile et ')' dans le lookahead devrait simplement se traduire par un décalage, ne produirait pas véritablement la séquence '(' expr ')' mais produirait simplement la séquence '(' ')' .

Answer 1

Bien que j'y aie pensé pendant des jours, que j'y aie réfléchi en écrivant la question et dans les minutes qui ont suivi, quelque chose m'a frappé comme étant incroyablement évident et simple.

La réduction par toutes les règles est toujours : retirer X entrées de la pile, où X est le nombre de composants de la règle, puis remettre le résultat sur la pile et passer à l'état indiqué dans le tableau après cette réduction.

Dans le cas de la règle du vide, il n'est pas nécessaire de considérer que "vide" est même un concept. La table d'analyse syntaxique doit simplement inclure une transition qui dit "given '(' sur la pile et "tout ce qui n'est pas '(' dans le lookahead, réduit par la règle du "vide"". Maintenant, puisque la règle vide a une taille de zéro composant, sortir zéro de la pile signifie que la pile ne change pas, alors quand le résultat de la réduction de rien est déplacé sur la pile, vous regardez quelque chose qui apparaît effectivement dans la grammaire et tout devient clair.

Stack       Lookahead    Remaining Input      Action
--------------------------------------------------------------
$           (            ())$                 Shift '('
$(          (            ))$                  Shift '('
$((         )            )$                   Reduce by /* empty */
$((expr     )            )$                   Shift ')'
$((expr)    )            $                    Reduce by '(' expr ')'
$(expr      )            $                    Shift ')'
$(expr)     $                                 Reduce by '(' expr ')'
$expr                                         Accept

La raison pour laquelle cela "fonctionne" est que pour réduire par la règle du vide, il suffit de sortir zéro élément de la pile.

Answer 2

Un autre point de vue pour peut-être compléter l'excellente réponse de d11wtq, si c'est possible :

Une règle nullable (une règle qui dérive ϵ) est comptabilisée pendant la construction de l'analyseur sous les fonctions FOLLOW(X) y FIRST(X) . Par exemple, si vous avez A -> B x et B peut dériver ϵ, alors nous devons inclure x dans l'ensemble calculé par FIRST(A) . Et aussi dans l'ensemble FOLLOW(B) .

De plus, les règles vides sont facilement représentées dans le modèle canonique LR(1) les ensembles d'articles.

Une chose utile est d'imaginer qu'il existe un symbole non terminal supplémentaire $ qui représente la fin du fichier.

Prenons la grammaire :

S -> X | ϵ
X -> id

Pour le premier canonique LR(1) l'ensemble des éléments, nous pouvons prendre le premier LR(0) l'élément set et add lookahead avec le symbole '$' :

S -> . X   , '$'
S -> .     , '$'
X -> . id  , '$'

Ensuite, nous en avons un pour le lookahead étant id :

S -> . X   , 'id'
S -> .     , 'id
X -> . id  , 'id'

Voyons maintenant le FIRST y FOLLOW ensembles :

S -> . X   , '$'

Il ne s'agit pas d'un élément "point final", donc nous voulons décaler, mais seulement si l'ensemble FIRST(X) contient notre symbole d'anticipation $ . C'est faux, donc nous ne remplissons pas l'entrée de la table.

Suivant :

S -> .     , '$'

Il s'agit d'un article "point final", il veut donc réduire. Pour valider le contexte d'une réduction, nous examinons les éléments suivants FOLLOW(S) : le symbole grammatical que nous souhaitons réduire peut-il être suivi de ce qui se trouve dans le lookahead ? En effet, oui. $ est toujours dans FOLLOW(S) car le symbole de début est par définition suivi de la fin de l'entrée. Donc oui, nous pouvons réduire. Et puisque nous réduisons le symbole S la réduction est en fait un accept action : l'analyse se termine. Nous remplissons l'entrée de la table avec un accept action.

De même, nous pouvons répéter pour l'ensemble d'éléments suivant avec lookahead. id . Passons à la règle du S-dérivé-vide :

S -> .     , 'id'

Can S être suivi par id ? Pas vraiment. Cette réduction n'est donc pas appropriée. Nous ne remplissons pas l'entrée de la table d'analyse.

Vous pouvez donc constater qu'une règle vide ne pose aucun problème. Elle se transforme immédiatement en un point final LR(0) o LR(1) (selon la méthode de construction de l'analyseur), et est traité de la même manière que n'importe quel autre point final en ce qui concerne la prise en compte du lookahead et le remplissage des tables.