Analyse LL(1) et transformation de grammaires

Partie A : Quelques exercises

(1) La grammaire suivante contient de la récursion à gauche. Trouvez une grammaire équivalente (qui génère le même langage) qui ne contient pas de la récursion à gauche. (Voir notes de cours).

S --> SaA
S --> bB
A --> aB
A --> c
B --> Bb
B --> d

Note: S, A, et B sont des non-terminaux. S est le symbole de départ, et a, b, c, et d sont des terminaux.

(2) Nous considérons la grammaire suivante (a, b, et c sont des terminaux).  Utilisez la factorisation à gauche pour trouvez une grammaire LL(1) équivalente.

S --> aA
S --> bB
A --> bA
A --> bB
B --> cB
B --> c

(3) Nous considérons la grammaire suivante:

bexpr --> bterm A’
A’ --> or bterm A’ | ε
bterm --> bfactor B’
B’ --> and bfactor B’ | ε
bfactor --> not bfactor | (bexpr) | true | false

• Calculez les ensembles FIRST et FOLLOW pour tous les non-terminaux de la grammaire.
• Construisez une table d'analyse pour cette grammaire.
• Est-ce que la grammaire est LL(1) ? – Expliquez

Partie B: Extension du language simple the VSPL

Le langage VSPL est très simple (voir description).

B-1: Trouver une grammaire LL(1) pour VSPL - équivalente à celle donnée dans la description

1. Identifiez des problèmes avec la grammaire donnée - problèmes qui la rendent non LL(1).
2. Appliquez certains transformations (des changements équivalents) pour rendre la grammaire LL(1).
3. Calculez les ensembles First et Follow pour la nouvelle grammaire, et vérifiez que les conditions LL(1) sont satisfaites.

B-2: Étendre le langage

Votre travail consiste à étendre la grammaire de VSPL pour inclure les opérateurs +, -. *, / et les parenthèses ( et ); il faut aussi prendre en compte la priorité habituelle des opérateurs.

1. Étendre la grammaire pour inclure les opérateurs +, -. *, / et les parenthèses ( et ) - en prenant en compte la priorité habituelle des opérateurs.
2. Vérifier que la grammaire est LL(1). Sinon, appliquer des règles de transformations pour la rendre LL(1). - Répéter cette étape jusqu'à ce que vous avez une grammaire LL(1).
3. Une validation finale: Est-ce la grammaire accepte exactement les programmes corrects ? - Consultez avec le "stakeholder" - faites quelques validations informelles.