Cours 6 : Partie avant d’un compilateur

Partie avant d’un compilateur

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 ⟶ 𝛼 \in P$ (guess)
$q, a ⟶^{a} q, 𝜀$ pour $a \in 𝛴$ (check)

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

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

soit les singletons sur $𝛴^{*}$
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 \in 𝛴^{\leq k}, a \in 𝛴 \cup 𝜀, q, q^{'} \in Q, z \in 𝛤, 𝛾 \in 𝛤^{*}$
NB : on peut, sans perte de généralité, supposer $u \in 𝛴^{k}$ quitte à compléter avec des $E O F$ à 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, u w ⟶^{a} q^{'}, 𝛾 𝛾^{'}, w^{'}$ si $(q, z, u, a, q^{'}, 𝛾^{'}) \in 𝛿$ tq $u w = a w^{'}$

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

N (𝒜) ≝ {w \in 𝛴^{*} ∣ (q_{0}, z_{0}, w $^{k}) ⟶_{𝒜}^{w} (q, 𝜀, $^{k}) pour q \in Q}

Syntaxe :

𝒜 = (Q, 𝛤, 𝛴, 𝛿, q_{0}, z_{0})

mais $𝛿 \subseteq Q \times 𝛤 \times 𝛴^{k} \times (𝛴 \cup {𝜀}) \times Q \times 𝛤^{*}$ fini

Déterministe si $\forall q, z, u \in Q \times 𝛤 \times 𝛴^{k}$ :

soit il existe une seule transitions $q, z ⟶^{u, 𝜀} q^{'}, 𝛾$
soit il n’y en a pas et alors $\forall a \in 𝛴$ , 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(𝒜’) $) q u i d e p l u s e s t d é t . s i$ 𝒜$ l’est.

Preuve :

𝒜^{'} ≝ ⟨ Q^{'}, 𝛤, 𝛴, 𝛿^{'}, q_{0}, ⊥ z_{0}, F ⟩

$Q^{'} ≝ Q \times 𝛴^{\leq k} ⊔ {q_{f}}$
$F ≝ {q_{f}}$
$𝛤^{'} = 𝛤 ⊔ {⊥}$
$\begin{matrix} 𝛿^{'} ≝ {((q, u), z, a, (q, u a), z) ∣ q \in Q, z \in 𝛤, | u | < k, a \in 𝛴} \\ \cup {((q, u), z, 𝜀, (q^{'}, u^{'}), 𝛾^{'}) ∣ (q, z, u, a, q^{'}, 𝛾^{'}) \in 𝛿, u = a u^{'}, | u | = k} \\ \cup {((q, $^{k}), ⊥, 𝜀, q_{f}, 𝜀) ∣ q \in Q} \end{matrix}$

Réciproque :

Premiers et suivants

P r e m_{k} (𝛼) ≝ {\underset{préfixe maximal de longueur \leq k de w}{\underset{⏟}{k : w}} ∣ 𝛼 ⟹_{l m G}^{*} w}

Pour $A \in N$ :

\begin{matrix} S u i v_{k} (A) ≝ ⋃ {P r e m_{k} (𝛾) ∣ S ⟹_{l m G}^{*} u A 𝛾} \\ = {\underset{préfixe de longueur k de v}{\underset{⏟}{k : v}} ∣ S ⟹_{G}^{*} 𝜃 A v} \end{matrix}

Ex :

P r e m_{k} (A) = ⋃_{A ⟶ 𝛼 \in P} P r e m_{k} (𝛼) P r e m (𝛼 \cdot 𝛽) = {k : w w^{'} ∣ w \in P r e m_{k} (𝛼), w^{'} \notin P r e m_{k} (𝛽)} P r e m_{k} (a \in 𝛴) = {\begin{cases} a si k > 0 \\ 𝜀 sinon \end{cases} P r e m_{k} (𝜀) = {𝜀}

S u i v_{k} (A) = ⋃_{B ⟶ 𝛼 A 𝛽 \in B} {k : w w^{'} ∣ w \in P r e m_{k} (𝛽), w^{'} \in S u i v_{k} (B)} \cup {𝜀 ∣ A = S}

Ex :

\begin{matrix} S ⟶ E $ \\ E ⟶ E + T ∣ T \\ T ⟶ T * F ∣ F \\ F ⟶ (E) ∣ i \end{matrix}

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

La $k$ -fenêtre de $A ⟶ 𝛼$ est :: $L A_{k} (A ⟶ 𝛼) ≝ P r e m_{k} (𝛼 \cdot S u i v_{k} (A))$

Grammaire alg. $G$ fortement $L L (k)$ :: si $\forall A ⟶ 𝛼_{1} \neq A ⟶ 𝛼_{2} \in P$ , $L A_{k} (A ⟶ 𝛼_{1}) \cap L A_{k} (A ⟶ 𝛼_{2}) = \emptyset$

Th : Si $G$ est fortement $L L (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 $L L (1)$ :

\begin{matrix} L A_{1} (E ⟶ E + T) = {(, i} \\ L A_{1} (E ⟶ T) = {(, i} \end{matrix}

Comment changer la grammaire pour que ce soit le cas ?

\begin{matrix} S ⟶ E $ \\ E ⟶ T E^{'} \\ E^{'} ⟶ 𝜀 ∣ + T E^{'} \\ T ⟶ F T^{'} \\ T^{'} ⟶ 𝜀 ∣ * F T^{'} \\ F ⟶ (E) ∣ i \end{matrix}

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

Maintenant :

\begin{matrix} L A_{1} (E^{'} ⟶ 𝜀) = {$,)} \\ L A_{1} (E^{'} ⟶ + T E^{'}) = {+} \\ L A_{1} (T^{'} ⟶ 𝜀) = {+,), $} \\ L A_{1} (T^{'} ⟶ * F T^{'}) = {*} \end{matrix}

Analyseur récursif descendant

Exemple :

fonction $E$ : $𝛴^{*} ∋ w \mapsto w^{'} suffixe de w$

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

fonction $T$ : $𝛴^{*} ∋ w \mapsto w^{'} suffixe de w$

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

fonction $F$ : $𝛴^{*} ∋ w \mapsto w^{'} suffixe de w$

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

if w == iw':
  return w'

fonction $E^{'}$ : $𝛴^{*} ∋ w \mapsto w^{'} suffixe de w$

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

Une grammaire est $L L (k)$ :: si $\forall S ⟹_{l m G} u A 𝛿$ et $\forall A ⟶ 𝛼_{1} \neq A ⟶ 𝛼_{2} \in P$ :
$P r e m_{k} (𝛼_{1} 𝛿) \cap P r e m_{k} (𝛼_{2} 𝛿) = \emptyset$

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

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

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

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

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

Hiérarchies $L L (k)$

Langages algébriques

∨

Langages non ambigus

∨

Langages déterministes

∨

$⋮$

∨

$L L (k)$ = fortement $L L (k)$

∨

$⋮$

∨

$L L (1)$ = fortement $L L (1)$

∨

Langages rationnels

∨

$L L (0)$ (singleton ou vide)

Grammaires :

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

Share on

Twitter Facebook Google+ LinkedIn

Partie avant d’un compilateur

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

Premiers et suivants

Analyseur récursif descendant

Hiérarchies LL(k)

Share on

Leave a comment

Hiérarchies $L L (k)$