LR Parser GOTO Fonction et Epsilon

Question

J'essaie d'apprendre la construction de compilateurs et je viens de lire le chapitre Dragon Book sur les analyseurs SLR. J'ai donc décidé de faire une grammaire simple et d'essayer de coder à la main l'analyseur. La grammaire ressemble à ceci:

S -> A 
A -> (A)A 
A -> e, 

où e est la production de chaîne vide.

Selon another question sur StackOverflow, les éléments de l'état de départ devrait ressembler à

S -> .A 
A -> .(A)A 
A -> .e, 

mais à quoi ressemblerait les fonctions GOTO comme. Je sais que GOTO('(') = *some state with A -> (.A)A*, mais je ne peux pas vraiment envelopper ma tête autour de GOTO(e). Cela n'a pas vraiment de sens pour un analyseur de voir une chaîne vide. Le fait?

Merci d'avance!

Michael

Answer 1

Non, l'analyseur ne voit pas de chaîne vide. Ce qu'il voit est le symbole entrant (le jeton suivant). Si le symbole entrant n'entraîne pas une action goto (passer à un nouvel état), alors l'analyseur est forcé de faire une réduction (A -> e), puis un goto basé sur A (une transition non-terminale).

In State: 

A -> '(' . A ')' A 
A -> . '(' A ')' A 
A -> e 

if the input symbol is not '(', then the parser will make the reduction: 

A -> e 

and go to the new state: 

A -> '(' A . ')' A