Cours 7 : Analyse syntaxique ascendante

Analyse syntaxique ascendante

Automate (simple = un seul état non précisé) avec inspection de pile :: $𝒜 ≝ ⟨ 𝛤, 𝛴, 𝛿, F ⟩$ , $𝛿 \subseteq 𝛤^{*} \times (𝛴 \cup {𝜀}) \times 𝛤^{*}$ fini

Sémantique

Configurations :: $\underset{contenu de pile}{\underset{⏟}{𝛤^{*}}} \times \underset{reste d’entrée}{\underset{⏟}{𝛴^{*}}}$
Transitions :: $𝛾 𝛾^{'} ⟶_{𝒜}^{a} 𝛾 𝛾^{″}$ si $(𝛾^{'}, a, 𝛾^{″}) \in 𝛿$
Langage :: $L (𝒜) ≝ {w \in 𝛴^{*} ∣ \exists z \in F; 𝜀 ⟶_{𝒜}^{w} z}$

Lien avec les grammaires algébriques

Automate ascendant de $G = ⟨ N, 𝛴, P, S ⟩$ :

$𝒜 ≝ ⟨ 𝛤, 𝛴, 𝛿, F ⟩$ où

$𝛤 ≝ N \cup 𝛴$
$F = {S}$
$\begin{matrix} 𝛿 ≝ {(𝛼, 𝜀, A) ∣ A ⟶ 𝛼 \in P} (reduce) \\ \cup {(𝛼, 𝜀, a) ∣ a \in 𝛴} (shift) \end{matrix}$

Lemme : $\forall 𝛼, 𝛽 \in (N \cup 𝛴)^{*}$ et $w \in 𝛴^{*}$

i) si $𝛽 {\overset{w}{⟶}}_{𝒜}^{*} 𝛼$ alors $𝛼 ⟹_{G, r m}^{*} 𝛽 w$

ii) si $𝛼 ⟹_{G, r m}^{*} 𝛽 w$ et $𝛽 \in {𝜀} \cup (N \cup 𝛴)^{*} N$ alors $𝛽 {\overset{w}{⟶}}_{𝒜}^{*} 𝛼$

Corollaire : $L (G) = L (𝒜)$

pour l’automate ascendant de $G$

Preuve du Corollaire : $𝛽 = 𝜀, 𝛼 = S$ dans le lemme

Preuve du lemme :

Preuve de i)

Par induction sur la longueur de l’exécution.

cas de base : $𝛽 = 𝛼, w = 𝜀$ , et alors $𝛼 ⟹_{G, r m}^{0} 𝛽 w$
étape d’induction :

𝛽 {\overset{w}{⟶}}_{𝒜}^{*} 𝛼 = 𝛾 𝛾^{'} {\overset{w}{⟶}}_{𝒜}^{a} 𝛾 𝛾^{″}

pour $(𝛾^{'}, a, 𝛾^{″}) \in 𝛿$

Par HR : $𝛼 ⟹_{G, r m}^{*} 𝛽 w$

puis (shift) :

\begin{matrix} 𝛾^{'} = 𝜀 et 𝛾^{″} = a \in 𝛴 \\ 𝛾 𝛾^{'} = 𝛼 a ⟹_{G, r m}^{*} 𝛽 w a \end{matrix}

ou (reduce)

𝛾^{'} = 𝛼^{'}, a = 𝜀 et 𝛾^{″} = A \in N

pour $A ⟶ 𝛼^{'} \in P$ :

𝛾 𝛾^{'} = 𝛾 A ⟹_{G, r m} 𝛾 𝛼^{'} = 𝛼 ⟹_{G, r m}^{*} 𝛽 w

Preuve de ii)

par induction sur la longueur de la dérivation.

Cas de base : $𝛼 = 𝛽 w$ , alors $𝛽 {\overset{w}{⟶}}_{𝒜}^{*} 𝛼$ par une séquence de (shift).
Étape d’induction :

\begin{matrix} 𝛼 = 𝛼_{1} A u ⟹_{G, r m} 𝛼_{1} 𝛼^{'} u \\ ⟹_{G, r m}^{*} v u \end{matrix}

La sous-dérivation $𝛼_{1} 𝛼^{'} ⟹_{r m, G}^{*} 𝛽 v$ donne par HR :

𝛽 {\overset{v}{⟶}}_{𝒜} 𝛼_{1} 𝛼^{'}

puis

\begin{matrix} 𝛼_{1} 𝛼^{'} {\overset{𝜀}{⟶}}_{𝒜} 𝛼_{1} A (reduce) \\ {\overset{𝜀}{⟶}}_{𝒜} 𝛼_{1} A u (shift u) \end{matrix}

Ex :

\begin{matrix} S ⟶ a S b ∣ a b \\ 𝜀 ⟶^{a} a ⟶^{a} a a ⟶^{b} a a b \\ ⟶^{𝜀} a S ⟶^{b} a S b ⟶^{𝜀} S \end{matrix}

a a b b \in L (G) = L (𝒜)

Conflits

Ex 2 :

\begin{matrix} S ⟶ a A ∣ b B ∣ c C \\ A ⟶ a A b ∣ a b \\ B ⟶ a B b ∣ a b \\ C ⟶ a C b ∣ a b b \end{matrix}

𝜀 ⟶^{a a^{n + 1} b} a a^{n + 1} b {\begin{cases} ⟶^{𝜀} a a^{n} A ⟶^{b^{n}} a A ⟶ S \\ ⟶^{𝜀} a a^{n} B ⟶^{b^{n}} a B \\ ⟶^{b} a a^{n + 1} b b ⟶^{𝜀} a a^{n} C ⟶^{b^{n}} a C \end{cases}

Conflit shift/reduce:

si $S ⟹_{r m}^{*} 𝛾 A u ⟹_{r m} 𝛾 𝛼 u S ⟹_{r m}^{*} 𝛾^{'} A^{'} u^{'} ⟹_{r m} 𝛾^{'} 𝛼_{1} a 𝛼_{2} u^{'}$

et $𝛾 𝛼 = 𝛾^{'} 𝛼_{1}$

Conflit reduce/reduce:

si $S ⟹_{r m}^{*} 𝛾 A u ⟹_{r m} 𝛾 𝛼 u S ⟹_{r m} 𝛾^{'} A^{'} u^{'} ⟹_{r m} 𝛾^{'} 𝛼^{'} u^{'}$

et $𝛾 𝛼 = 𝛾^{'} 𝛼^{'}$ mais $A ⟶ 𝛼 \neq A ⟶ 𝛼^{'}$

Grammaires $L R (0)$

Grammaire $L R (0)$ :: si sa $\underset{G^{'} ≝ ⟨ N ⊔ {S^{'}}, 𝛴 ⊔ {$}, P ⊔ {S^{'} ⟶ S $}, S^{'} ⟩}{\underset{⏟}{grammaire étendue}}$ n’a pas de conflit

Construction d’un automate déterministe pour une grammaire $L R (0)$

Item $L R (0)$ :: c’est une production pointée $A ⟶ 𝛼_{1} \cdot 𝛼_{2}$ pour $A ⟶ 𝛼_{1} 𝛼_{2} \in P, 𝛼_{1}, 𝛼_{2} \in (N \cup 𝛴)^{*}$
Item $L R (0)$ est valide pour $𝛾 \in (N \cup 𝛴)^{*}$ :: ssi $S ⟹_{r m}^{*} 𝛾^{'} A u ⟹_{r m} 𝛾^{'} 𝛼_{1} 𝛼_{2} u$ avec $𝛾^{'} 𝛼_{1} = 𝛾$ .

On note $V_{0} (𝛾)$ l’ens. des items valides de $𝛾$ .

Équivalence de $L R (0)$ :: $𝛾 \sim_{0} 𝛾^{'} ⟺ V_{0} (𝛾) = V_{0} (𝛾^{'})$

NB :

$\sim_{0}$ est d’index fini $\leq \underset{nb max. d’ens. d’items, puisqu’il y a | G | items}{\underset{⏟}{2^{| G |}}}$ où $G ≝ \sum_{A ⟶ 𝛼 \in P} | 𝛼 | + 1$

$𝛾$ est viable :: ssi $S ⟹_{r m}^{*} 𝛾^{'} A u ⟹_{r m} 𝛾^{'} 𝛼_{1} 𝛼_{2} u = 𝛾 𝛼_{2} u$ ssi $V_{0} (𝛾) \neq \emptyset$

$𝛾 \sim_{0} 𝛾^{'} \land 𝛾 X, 𝛾^{'} X viables ⟹ 𝛾 X \sim_{0} 𝛾^{'} X$
si $A ⟶ 𝛼_{1} \cdot B 𝛼_{2} \in V_{0} (𝛾)$ , alors $B ⟶ \cdot 𝛽 \in V_{0} (𝛾)$ $\forall B ⟶ 𝛽 \in P$ :
$\begin{matrix} S ⟹_{r m}^{*} 𝛾^{'} A u ⟹_{r m} 𝛾^{'} 𝛼_{1} B 𝛼_{2} u (A ⟶ 𝛼_{1} \cdot B 𝛼_{2}) \\ ⟹_{r m}^{*} 𝛾^{'} 𝛼_{1} B v u \\ ⟹_{r m} 𝛾^{'} 𝛼_{1} 𝛽 v u (B ⟶ \cdot 𝛽) \end{matrix}$
Si $𝛾 = 𝜀$ , alors ${S ⟶ \cdot 𝛼 ∣ S ⟶ 𝛼 \in P} \subseteq V_{0} (𝜀)$

Automate des contextes :

un automate fini $𝒞 ≝ (Q, N \cup 𝛴, g o t o, q_{0})$ dét. complet, où :

$q_{0} ≝ V_{0} (𝜀)$
$Q ≝ {V_{0} (𝛾) ∣ 𝛾 \in (N \cup 𝛴)^{*}}$
$g o t o (q, X) ≝ V_{O} (𝛾 X)$ si $q = V_{0} (𝛾)$

Construction des $V_{0} (𝛾)$ :

Clôture de $E \subseteq {A ⟶ 𝛼_{1} \cdot 𝛼_{2} ∣ A ⟶ 𝛼_{1} 𝛼_{2} \in P}$

\overset{―}{E} ≝ 𝜇 x . E \cup {B ⟶ \cdot 𝛽 ∣ A ⟶ 𝛼_{1} \cdot B 𝛼_{2} \in x}

Transitions $g o t o$ :

g o t o (E, X) ≝ \overset{―}{{S ⟶ 𝛼 ∣ S ⟶ 𝛼 \in P}}

Ex :

Automate à pile $L R (0)$ :: on construit l’automate de contextes de $G$ .
$\begin{matrix} 𝒜 ≝ (𝛤, 𝛴, 𝛿, q_{0}, F ≝ V_{0} (S $)) \\ 𝛿 ≝ {(q q_{1} \dots q_{m}, 𝜀, q q^{'}) ∣ A ⟶ X_{1} \dots X_{m} \cdot \in q_{m} et g o t o (q, A) = q^{'}} (reduce) \\ \cup {(q, a, q q^{'}) ∣ a \in 𝛴, A ⟶ 𝛼_{1} \cdot a 𝛼_{2} \in q et g o t o (q, a) = q^{'}} (shift) \end{matrix}$

Ex :

\begin{aligned} q_{0} & ⟶^{a} q_{0} q_{1} ⟶^{a} q_{0} q_{1} q_{2} & q_{0} a a \\ ⟶^{a} q_{0} q_{1} q_{2} q_{3} & q_{0} a a a \\ ⟶^{b} q_{0} q_{1} q_{2} q_{2} q_{3} & q_{0} a a a b \\ ⟶^{𝜀} q_{0} q_{1} q_{2} q_{4} & q_{0} a a A \\ ⟶^{b} q_{0} q_{1} q_{2} q_{4} q_{6} & q_{0} a a A b \\ ⟶^{𝜀} q_{0} q_{1} q_{5} & q_{0} a A \\ ⟶^{𝜀} q_{0} q_{7} \\ ⟶^{𝜀} q_{0} q_{7} q_{8} & (accepte) \end{aligned}

Ex :

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

Automate de contextes :

$S L R (k)$ :

$\forall 𝛾, \forall A_{1} ⟶ 𝛼_{1} \cdot \neq A_{2} ⟶ 𝛼_{2} \cdot \in V_{0} (𝛾)$ ,

S u i v_{k} (A_{1}) \cap S u i v_{k} (A_{2}) = \emptyset

et $\forall 𝛾, \forall A_{1} ⟶ 𝛼 \cdot, A_{2} ⟶ 𝛼_{1} \cdot a 𝛼_{2} \in V_{0} (𝛾)$ ,

S u i v_{k} (A_{1}) \cap P r e m_{k} (a 𝛼_{2} S u i v_{k} (A_{2})) = \emptyset

Ex : $S u i v_{1} (E) = {$, +,)}$

la grammaire est $S L R (1)$

$L A L R (k)$ :: $\begin{matrix} L A_{k} (A ⟶ 𝛼, 𝛾) ≝ {k : w ∣ \exists 𝛾^{'} 𝛼_{1} \sim_{0} 𝛾; S^{'} ⟹_{r m}^{*} 𝛾^{'} A^{'} u ⟹_{r m} 𝛾^{'} 𝛼_{1} 𝛼_{2} u ⟹_{r m}^{*} 𝛾^{'} 𝛼_{1} w} \\ \subseteq S u i v_{k} (A) \end{matrix}$

remplacer $S u i v_{k}$ par $L A_{k}$ dans la déf ci-dessus

NB :

utilisé dans OcamL yacc, Bison, etc…
ascendants plus difficiles à déboguer à cause des conflits que descendants

Inclusion des langages

(graphe)

NB : Il existe des grammaires $S L L (1)$ non $L A L R (k)$ :

\forall k, L L (k) \subseteq L R (k)

Share on

Twitter Facebook Google+ LinkedIn

Analyse syntaxique ascendante

Sémantique

Lien avec les grammaires algébriques

Preuve de i)

Preuve de ii)

Conflits

Grammaires LR(0)

Construction d’un automate déterministe pour une grammaire LR(0)

Inclusion des langages

Share on

Leave a comment

Grammaires $L R (0)$

Construction d’un automate déterministe pour une grammaire $L R (0)$