Transformez la grammaire en LL (1), identifiez si c'est LL (1)

Question

Je n'arrive pas à comprendre comment déterminer si la grammaire est LL (1) ou non. J'ai donné la grammaire suivante:

S → Y | 1X 
X → 1X | 0 
Y → Y0|1X1|2X2 

Je déclare que cette grammaire n'est pas LL (1), car il Y0 reste récursive.

Alors je suis venu avec la solution suivante:

S → Y | 1X 
X → 1X | 0 
Y → 1X1F | 2X2F 
F → ε | 0F 

Mais je ne sais pas si cela est exact. Je pense toujours que j'ai dû manquer une règle comme l'affacturage de quelque sorte. Devrais-je prendre 1X et 2X dans une variable différente?

Merci de votre aide à l'avance. J'aimerais aussi savoir s'il existe des moyens plus simples de déterminer si la grammaire est LL (1) J'ai rencontré beaucoup de tables "first" et "follow", mais je n'ai pas réussi à en construire une moi-même.

Answer 1

Une grammaire LL (1) doit être capable de prédire une production basée sur un jeton de recherche unique ((1)). Cependant, les deux Y et 1X peuvent commencer par 1, il est donc impossible de prédire s'il faut utiliser S→Y ou S→1X étant donné le premier symbole d'entrée 1. Donc ni la grammaire originale ni la grammaire transformée ne sont LL (1).

Answer 2

Si le facteur de notre 1X puis-je obtenir ce qui suit:

S → Y | Z 
X → Z | 0 
Y → Z1F | 2X2F 
F → ε | 0F 
Z → 1X | ε 

Ce qui signifie que S → Y | Z et je crois que ce n'est pas permis.