LR1 Parser et Epsilon

Question

J'essaie de comprendre le fonctionnement des analyseurs syntaxiques LR1, mais je suis tombé sur un problème étrange: que se passe-t-il si la grammaire contient Epsilons? Par exemple: si j'ai la grammaire:

S -> A
A -> a A | B
B -> a

Il est clair comment commencer:

S -> .A
A -> .a A 
A -> .B

... et ainsi de suite

mais je ne sais pas comment faire pour une telle grammaire:

S -> A
A -> a A a | \epsilon

Est-il correct de faire:

S -> .A
A -> .a A a
( A -> .\epsilon )

Et ensuite faire accepter cet État dans le DFAE?

Toute aide serait vraiment appréciée!

Answer 1

Oui, exactement (pensez à epsilon comme un espace vide, où il n'y a pas deux places pour le point sur les côtés).

Dans un automate LR (0), vous feriez en sorte que l’État accepte et réduise à A. Toutefois, en raison de la A->a A a production, il y aurait un décalage / conflit en conflit.

Dans un automate LR (1), vous déterminez s'il faut déplacer ou réduire en utilisant une anticipation (a - > shift, tout élément de FOLLOW(A) - > réduire)

Voir le article de Wikipedia