Cours 6 : Partie avant d’un compilateur

Partie avant d’un compilateur

  digraph {
    rankdir=LR;
    AL[label="Analyse lexicale (Lex) : expr. rat."];
    AS[label="Analyse syntaxique (Yacc) : gramm. alg."];
    Programme[label="Programme (alphabet UTF8/ASCII)"];
    ASem[label="Analyse sémantique : optimisation/interprétation/prod. de code"];
    Programme -> AL;
    AL -> AS[label="𝛴^*"];
    AS -> ASem[label="Abres de syntaxe"];
  }

On veut générer des analyseurs syntaxiques qui sont des automates à pile déterministes pour une exécution en temps linéaire.

• Lex : générateur d’analyseurs lexicaux
• Yacc : générateurs d’analyseurs syntaxiques ⟶ donne un AST

---

Construction d’un automate à pile à partir d’une grammaire

• $q, A ⟶^𝜀 q, 𝛼^R$ pour $A⟶𝛼∈P$ (guess)
• $q, a ⟶^a q, 𝜀$ pour $a∈𝛴$ (check)

Cet automate est déterministe ssi $∀A∈N$, il existe au plus une règle $A⟶𝛼∈P$

i.e la classe $LL(0)$ de langages associés est :

• soit les singletons sur $𝛴^\ast$
• soit le vide

NB : problème : on ne peut donc reconnaître qu’un programme au plus, il nous faut donc étendre un peu la définition

Automate à $k$-fenêtres :

$q, z⟶^{u,a} q’, 𝛾$

• où $u∈𝛴^{≤k}, a∈ 𝛴∪{𝜀}, q,q’∈Q, z∈𝛤, 𝛾∈𝛤^\ast$
• NB : on peut, sans perte de généralité, supposer $u∈𝛴^{k}$ quitte à compléter avec des $EOF$ à la fin du fichier
• $u$ est notre fenêtre de lecture (de $k$ lettres) ⟶ on ne touche pas à $u$ (à part sa première lettre), $a$ le symbole couramment lu (première lettre de $u$) _____

Sémantique :

$q, 𝛾z, uw ⟶^a q’, 𝛾𝛾’, w’$ si $(q, z, u, a, q’, 𝛾’) ∈𝛿$ tq $uw = aw’$

On accepte dans une configuration $(q, 𝜀, $^k)$ :

\[N(𝒜) ≝ \lbrace w∈𝛴^\ast \mid (q_0, z_0, w\$^k) ⟶^w_𝒜 (q, 𝜀, \$^k) \text{ pour } q∈Q\rbrace\]

Syntaxe :

\[𝒜 = (Q, 𝛤, 𝛴, 𝛿, q_0, z_0)\]

mais $𝛿⊆ Q×𝛤×𝛴^k×(𝛴∪ \lbrace 𝜀 \rbrace ) × Q × 𝛤^\ast$ fini

---

Déterministe si $∀ q, z, u∈Q ×𝛤×𝛴^k$ :

• soit il existe une seule transitions $q, z⟶^{u,𝜀} q’, 𝛾$
• soit il n’y en a pas et alors $∀a∈𝛴$, il existe au plus une transition $q, z⟶^{u,a} q’, 𝛾$

---

Soit un automate à pile à $k$ fenêtres. On peut construire un automate équivalent (avec $N(𝒜)\cdot $^k = L(𝒜’)$) qui de plus est dét. si $𝒜$ l’est.

Preuve :

\[𝒜' ≝ ⟨Q', 𝛤, 𝛴, 𝛿', q_0, \bot z_0, F⟩\]

• $Q’ ≝ Q×𝛴^{≤k} \sqcup \lbrace q_f \rbrace$
• $F ≝ \lbrace q_f \rbrace$
• $𝛤’ = 𝛤 \sqcup \lbrace \bot \rbrace$
• \[𝛿' ≝ \lbrace \Big( (q, u), z, a, (q, ua), z \Big) \mid q∈Q, z∈𝛤, \vert u \vert<k, a∈𝛴\rbrace \\ ∪ \lbrace \Big( (q, u), z, 𝜀, (q', u'), 𝛾' \Big) \mid (q, z, u, a, q', 𝛾') ∈𝛿, u=au', \vert u \vert=k \rbrace \\ ∪ \lbrace \Big( (q, \$^k), \bot, 𝜀, q_f, 𝜀 \Big) \mid q∈Q \rbrace\]

---

Réciproque :

Premiers et suivants

\[Prem_k(𝛼) ≝ \lbrace \underbrace{k:w}_{\text{préfixe maximal de longueur } ≤ k \text{ de } w} \mid 𝛼⟹^\ast_{lm G} w\rbrace\]

Pour $A∈N$ :

\[Suiv_k(A) ≝ \bigcup \lbrace Prem_k(𝛾) \mid S ⟹^\ast_{lm G} uA𝛾 \rbrace \\ = \lbrace \underbrace{k:v}_{\text{préfixe de longueur } k \text{ de } v} \mid S⟹^\ast_{G} 𝜃Av \rbrace\]

Ex :

\[Prem_k(A) = \bigcup_{A⟶𝛼∈P} Prem_k(𝛼) \\ Prem(𝛼 \cdot 𝛽) = \lbrace k: ww' \mid w∈Prem_k(𝛼), w'∉Prem_k(𝛽) \rbrace \\ Prem_k(a∈𝛴) = \begin{cases} a \text{ si } k>0 \\ 𝜀 \text{ sinon} \end{cases} \\ Prem_k(𝜀) = \lbrace 𝜀 \rbrace\] \[Suiv_k(A) = \bigcup_{B⟶𝛼A𝛽∈B} \lbrace k: ww' \mid w∈Prem_k(𝛽), w'∈Suiv_k(B) \rbrace ∪ \lbrace 𝜀 \mid A=S \rbrace\]

Ex :

\[S ⟶ E \$ \\ E ⟶ E+T \mid T \\ T ⟶ T*F \mid F \\ F ⟶ (E) \mid i\]

N	Prem_1	Suiv_1
E	(, i	$, ), +
T	(, i	*, $, ), +
F	(, i	*, $, ), +

La $k$-fenêtre de $A⟶𝛼$ est :

\[LA_k(A⟶𝛼) ≝ Prem_k\Big(𝛼 \cdot Suiv_k(A) \Big)\]

---

Grammaire alg. $G$ fortement $LL(k)$ :

si $∀A⟶𝛼_1≠A⟶𝛼_2 ∈P$, $LA_k(A⟶𝛼_1) ∩ LA_k(A⟶𝛼_2) = ∅$

Th : Si $G$ est fortement $LL(k)$ alors son automate guess/check à $k$-fenêtres est déterministe.

Ex :

Dans l’exemple précédent, la grammaire n’est pas fortement $LL(1)$ :

\[LA_1(E ⟶ E+T) = \lbrace (, i \rbrace \\ LA_1(E ⟶ T) = \lbrace (, i \rbrace\]

Comment changer la grammaire pour que ce soit le cas ?

\[S ⟶ E \$ \\ E ⟶ T E' \\ E' ⟶ 𝜀 \mid + T E' \\ T ⟶ F T' \\ T' ⟶ 𝜀 \mid * F T' \\ F ⟶ (E) \mid i\]

N	Prem_1	Suiv_1
E	(, i	$, )
E’	𝜀, +	$, )
T	(, i	+, ), $
T’	𝜀, *	+, ), $
F	(, i	*, +, ), $

Maintenant :

\[LA_1(E' ⟶ 𝜀) = \lbrace \$, ) \rbrace \\ LA_1(E' ⟶ +TE') = \lbrace +\rbrace \\ LA_1(T' ⟶ 𝜀) = \lbrace +, ), \$\rbrace \\ LA_1(T' ⟶ *FT') = \lbrace *\rbrace \\\]

---

Analyseur récursif descendant

Exemple :

fonction $E$ : $𝛴^\ast \ni w \mapsto w’ \text{ suffixe de } w$

w = T(w)
return E'(w)

---

fonction $T$ : $𝛴^\ast \ni w \mapsto w’ \text{ suffixe de } w$

w = F(w)
return T'(w)

---

fonction $F$ : $𝛴^\ast \ni w \mapsto w’ \text{ suffixe de } w$

if w == (w':
  w = E(w')
  if w == )w':
    return w'

if w == iw':
  return w'

---

fonction $E’$ : $𝛴^\ast \ni w \mapsto w’ \text{ suffixe de } w$

if w == 𝜀 or w == )w':
  return w
  if w == +w':
    w = T(w')
    return E'(w)

---

Une grammaire est $LL(k)$ :

si $∀S⟹_{lm G} uA𝛿$ et $∀A⟶𝛼_1≠A⟶𝛼_2 ∈P$ :

\[Prem_k(𝛼_1𝛿) ∩ Prem_k(𝛼_2 𝛿) = ∅\]

Prop : Si $G$ est fortement $LL(k)$, alors elle est $LL(k)$

L’inverse est faux : il existe des grammaires $LL(2)$ qui ne sont fortement $LL(k)$ pour aucun $k$.

Prop : Si $G$ est $LL(1)$ alors elle est fortement $LL(1)$

Prop : Si $G$ est $LL(k)$, alors elle n’est pas ambiguë

Prop : Si $G$ est $LL(k)$, alors elle n’est pas récursive à gauche

Hiérarchies $LL(k)$

Langages algébriques

∨

Langages non ambigus

∨

Langages déterministes

∨

$\vdots$

∨

$LL(k)$ = fortement $LL(k)$

∨

$\vdots$

∨

$LL(1)$ = fortement $LL(1)$

∨

Langages rationnels

∨

$LL(0)$ (singleton ou vide)

---

Grammaires :

  digraph {
    rankdir=TB;
    GA[label="Grammaires algébriques"];
    GNA[label="Grammaires non ambiguës"];
    LD[label="Grammaires déterministes"];
    LLk[label="LL(k)"];
    fLLk[label="fortement LL(k)"];
    fLLk1[label="fortement LL(k-1)"];
    LLk1[label="LL(k-1)"];
    LL1[label="LL(1) = fortement LL(1)"];
    LL0[label="LL(0) : au plus une règle par non terminal"];
    LLk[label="LL(k)"];
    GA -> GNA -> LD;
    LD -> LLk[style="dashed"];
    LLk -> {LLk1, fLLk};
    LLk1 -> fLLk1;
    fLLk -> fLLk1;
    LLk1 -> LL1[style="dashed"];
    fLLk1 -> LL1[style="dashed"];
    LL1 -> LL0;
  }

---

Prop : Soit $G$ $LL(k)$. On peut construire une grammaire équivalente fortement $LL(k)$.