Comment étendre l'ensemble d'éléments pour cette grammaire?

Question

J'ai cette grammaire

E -> E + i
E -> i

La grammaire augmentée

E' -> E
E -> E + i
E -> i

Maintenant, j'essaye d'étendre l'ensemble d'objets 0

I0)
 E' -> .E
+E  -> .E + i
+E  -> .i

Alors, depuis que je suis .Edans I0je l' étendre , mais je vais obtenir une autre Erègle, et ainsi de suite, c'est mon premier doute.

En supposant que tout va bien, les ensembles d'articles suivants sont

I0)
 E' -> .E
+E  -> .E + i
+E  -> .i

I1) (I moved the dot from I0, no variables at rhs of dot)
E' -> E.
E -> E. + i
E -> i.

I2) (I moved the dot from I1, no vars at rhs of dot)
E -> E +. i

I3) (I moved the dot from I2, also no vars)
E -> E + i.

Ensuite, j'aurai ce DFA

I0 -(E, i)-> I1 -(+)-> I2 -(i)-> I3
              |                   |
              +-(∅)-> acpt <-(∅)--+

Il me manque quelque chose car je E -> E + idois accepter, i + i + ..mais le DFA ne revient pas au I0, donc cela me semble incorrect. Je suppose qu'il devrait avoir une transition de I0 à I0, mais je ne sais pas que cela a à voir avec le point.

Answer 1

Ce que vous appelez «l'expansion» de l'ensemble d'articles est en fait une fermeture; c'est ainsi que cela est décrit dans toutes les descriptions de l'algorithme que j'ai vu (au moins dans les manuels). Comme toute opération de fermeture, vous continuez simplement à faire la transformation jusqu'à ce que vous atteigniez un point fixe; une fois que vous avez inclus les productions pour E, elles sont incluses.

Mais l'essentiel est que vous ne créez pas de DFA. Vous construisez un automate déroulant, et le DFA n'en est qu'une partie. Le DFA est utilisé pour les opérations de quart; lorsque vous déplacez un nouveau terminal (car la pile d'analyse actuelle n'est pas un handle), vous effectuez une transition d'état selon le DFA. Mais vous poussez également l'état actuel sur la pile du PDA.

La partie intéressante est ce qui se passe lorsque l'automate décide d'effectuer une réduction, qui remplace le côté droit d'une production par son côté gauche non terminal. (Le côté droit en haut de la pile est appelé une "poignée".) Pour effectuer la réduction, vous déroulez la pile, en faisant apparaître chaque symbole de droite (et l'état DFA correspondant) jusqu'à ce que vous atteigniez le début de la production. Cela ramène le DFA à l'état dans lequel il était avant de déplacer le premier symbole du côté droit. (Notez que ce n'est qu'à ce stade que vous savez avec certitude quelle production a été utilisée.) Avec le DFA ainsi réinitialisé, vous pouvez maintenant décaler le non-terminal qui a été rencontré, effectuer la transition DFA correspondante et poursuivre l'analyse.

La base de cette procédure est le fait que la pile de l'analyseur est à tout moment un "préfixe viable"; c'est-à-dire une séquence de symboles qui sont le préfixe d'une forme sententielle droite qui peut être dérivée du symbole de départ. Ce qui est intéressant à propos de l'ensemble de préfixes viables pour une grammaire sans contexte, c'est qu'il s'agit d'une langue standard , et par conséquent peut être reconnue par un DFA. La procédure de réduction donnée ci-dessus représente précisément cette procédure de reconnaissance lorsque les poignées sont "élaguées" (pour utiliser le vocabulaire original de Knuth).

En ce sens, peu importe la procédure utilisée pour déterminer quelle poignée doit être élaguée, du moment qu'elle fournit une réponse valide. Vous pouvez, par exemple, effectuer l'analyse à chaque fois qu'une poignée potentielle est remarquée en haut de la pile, et continuer en parallèle avec les deux fourchettes. Avec une gestion intelligente de la pile, cette recherche parallèle peut être effectuée dans le pire des cas O (n ³ ) pour toute grammaire sans contexte (et cela peut être réduit si la grammaire n'est pas ambiguë). C'est une description très approximative des analyseurs Earley.

Mais dans le cas d'un analyseur LR (k), nous exigeons que la grammaire soit sans ambiguïté, et nous exigeons également que nous puissions identifier une réduction en ne regardant pas plus de kplus de symboles du flux d'entrée, qui est un O (1) opération depuis kest fixe. Si, à chaque point de l'analyse, nous savons s'il faut réduire ou non, et si oui quelle réduction choisir, alors les réductions peuvent être mises en œuvre comme je l'ai souligné ci-dessus. Chaque réduction peut être effectuée en temps O (1) pour une grammaire fixe (puisque la taille maximale d'un membre droit dans une grammaire particulière est fixe), et puisque le nombre de réductions dans une analyse est linéaire dans la taille du entrée, l'analyse entière peut être effectuée en temps linéaire.

Tout cela était un peu informel, mais j'espère que cela servira d'explication intuitive. Si vous êtes intéressé par la preuve formelle, l'article original de Donald Knuth de 1965 ( Sur la traduction des langues de gauche à droite ) est facile à trouver et très lisible au fur et à mesure.