Examen de compilation : 4. Synthèse et commandes

LL(1) : lecture gauche à droite, dérivation gauche, un token de prévision. La compilation produit une représentation cible ; l’interprétation exécute une représentation du programme. Pour pref(L), rendre finaux tous les états pouvant atteindre un ancien final. Pour fact(L), prendre de plus comme initiaux tous les états accessibles depuis l’ancien initial. Un nouvel initial relié par ε permet de représenter cet ensemble : on obtient un AFN, donc un langage régulier.

Initial : q00 ; seul final : q01. Lire a inverse la première parité ; lire b inverse la seconde. Les quatre états sont accessibles par ε, a, b, ab. Depuis chaque état, il existe un suffixe de longueur au plus deux menant à q01 ; appliqué à tout autre état, ce suffixe conserve une différence de parité, donc le distingue. Les quatre états sont nécessaires. ε est refusé, b et aab sont acceptés, ab est refusé.

α#α#α& possède deux regroupements : (α#α)#α et α#(α#α). Choisissons :

S → C &
C → P C′
C′ → # C | ε
P → A R
R → @ R | ε
A → α | [ C ]

R applique zéro ou plusieurs @ au seul atome précédent. C′ renvoie à C après # : l’arbre abstrait de α#α#α est #(α,#(α,α)), donc l’associativité est à droite. Les crochets forcent un regroupement.

Convention : sommet de pile à gauche ; $ marque la fin de l’entrée et le fond de pile.

L1={aⁿbⁿcᵐ | n,m≥0} et L2={aᵐbⁿcⁿ | n,m≥0} sont hors contexte. Exemples de grammaires : S1 → U V ; U → aUb | ε ; V → cV | ε, et S2 → W X ; W → aW | ε ; X → bXc | ε. Leur intersection est {aⁿbⁿcⁿ | n≥0}, qui n’est pas hors contexte.

Justification par pompage : choisir aᵖbᵖcᵖ. Une fenêtre de longueur au plus p rencontre au plus deux blocs de lettres. Pomper les deux segments modifiés change au moins un compte sans changer les trois de façon égale, ou détruit l’ordre des blocs. On sort du langage. Enfin, si les langages hors contexte étaient clos par complémentation, leur clôture par union et la loi de De Morgan impliqueraient la clôture par intersection : contradiction.