Cours 7 : Analyse syntaxique ascendante

Analyse syntaxique ascendante

Automate (simple = un seul état non précisé) avec inspection de pile :

$𝒜 ≝ ⟨𝛤, 𝛴, 𝛿, F⟩$, $𝛿⊆𝛤^\ast × (𝛴∪ \lbrace 𝜀 \rbrace) × 𝛤^\ast$ fini

Sémantique

Configurations :
\[\underbrace{𝛤^\ast}_{\text{ contenu de pile}} × \underbrace{𝛴^\ast}_{\text{ reste d'entrée}}\]
Transitions :

\(𝛾𝛾' ⟶^a_𝒜 𝛾𝛾''\) si $(𝛾’, a, 𝛾’’) ∈ 𝛿$

Langage :
\[L(𝒜) ≝ \lbrace w∈𝛴^\ast \mid ∃z∈F; 𝜀⟶^w_𝒜 z \rbrace\]

Lien avec les grammaires algébriques

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

\(𝒜 ≝ ⟨𝛤, 𝛴, 𝛿, F⟩\) où

  • $𝛤 ≝ N∪𝛴$
  • $F = \lbrace S \rbrace$
  • \[𝛿 ≝ \lbrace (𝛼, 𝜀, A) \mid A⟶𝛼∈P \rbrace \quad\text{ (reduce)} \\ ∪ \lbrace (𝛼, 𝜀, a) \mid a∈𝛴 \rbrace \quad\text{ (shift)}\]

Lemme : $∀𝛼, 𝛽∈ (N∪ 𝛴)^\ast$ et $w∈𝛴^\ast$

  • i) si $𝛽\overset{w}{⟶}^\ast_𝒜 𝛼$ alors $𝛼⟹^\ast_{G, rm} 𝛽w$
  • ii) si $𝛼⟹^\ast_{G, rm} 𝛽w$ et $𝛽∈\lbrace 𝜀\rbrace ∪ (N∪ 𝛴)^\ast N$ alors $𝛽\overset{w}{⟶}^\ast_𝒜 𝛼$

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 $𝛼⟹^0_{G, rm} 𝛽w$

  • étape d’induction :

\[𝛽\overset{w}{⟶}^\ast_𝒜 𝛼 = 𝛾𝛾' \overset{w}{⟶}^a_𝒜 𝛾𝛾''\]

pour $(𝛾’, a, 𝛾’’)∈𝛿$

Par HR : $𝛼⟹^\ast_{G, rm} 𝛽w$

puis (shift) :

\[𝛾'=𝜀 \text{ et } 𝛾''=a∈𝛴 \\ 𝛾𝛾' = 𝛼a ⟹^\ast_{G, rm} 𝛽wa\]

ou (reduce)

\[𝛾'= 𝛼', a=𝜀 \text{ et } 𝛾''=A∈N\]

pour $A⟶𝛼’∈P$ :

\[𝛾𝛾' = 𝛾A ⟹_{G, rm} 𝛾𝛼' = 𝛼 ⟹^\ast_{G, rm} 𝛽w\]

Preuve de ii)

par induction sur la longueur de la dérivation.

  • Cas de base : $𝛼=𝛽w$, alors $𝛽 \overset{w}{⟶}^\ast_𝒜 𝛼$ par une séquence de (shift).

  • Étape d’induction :

\[𝛼 = 𝛼_1 A u ⟹_{G, rm} 𝛼_1𝛼'u \\ ⟹^\ast_{G, rm} vu\]

La sous-dérivation $𝛼_1𝛼’⟹^\ast_{rm, G} 𝛽v$ donne par HR :

\[𝛽 \overset{v}{⟶}_𝒜 𝛼_1𝛼'\]

puis

\[𝛼_1𝛼' \overset{𝜀}{⟶}_𝒜 𝛼_1 A \quad \text{(reduce)}\\ \overset{𝜀}{⟶}_𝒜 𝛼_1 A u \quad \text{(shift u)}\]

Ex :

\[S ⟶ aSb \mid ab \\ 𝜀 ⟶^a a ⟶^a aa ⟶^b aab \\ ⟶^𝜀 aS ⟶^b aSb ⟶^𝜀 S\] \[aabb∈ L(G) = L(𝒜)\]

Conflits

Ex 2 :

\[S ⟶ aA \mid bB \mid cC \\ A ⟶ aAb \mid ab \\ B ⟶ aBb \mid ab \\ C ⟶ aCb \mid abb\] \[𝜀 ⟶^{aa^{n+1}b} aa^{n+1}b \begin{cases} ⟶^𝜀 aa^n A ⟶^{b^n} aA ⟶ S \\ ⟶^𝜀 aa^n B ⟶^{b^n} aB \\ ⟶^b a a^{n+1}bb ⟶^𝜀 a a^n C ⟶^{b^n} aC \\ \end{cases}\]
Conflit shift/reduce:

si \(S ⟹^\ast_{rm} 𝛾Au ⟹_{rm} 𝛾𝛼u \\ S ⟹^\ast_{rm} 𝛾'A'u' ⟹_{rm} 𝛾'𝛼_1 a 𝛼_2 u'\)

et $𝛾𝛼 = 𝛾’𝛼_1$

Conflit reduce/reduce:

si \(S ⟹^\ast_{rm} 𝛾Au ⟹_{rm} 𝛾𝛼u \\ S ⟹_{rm} 𝛾'A'u' ⟹_{rm} 𝛾'𝛼' u'\)

et $𝛾𝛼 = 𝛾’𝛼’$ mais $A⟶𝛼 ≠ A ⟶𝛼’$

Grammaires $LR(0)$

Grammaire $LR(0)$ :

si sa $\underbrace{\textit{grammaire étendue}}_{G’≝ ⟨N\sqcup \lbrace S’ \rbrace, 𝛴\sqcup \lbrace $ \rbrace, P \sqcup \lbrace S’⟶S$ \rbrace, S’⟩}$ n’a pas de conflit

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

Item $LR(0)$ :

c’est une production pointée $A⟶ 𝛼_1 \cdot 𝛼_2$ pour $A⟶𝛼_1 𝛼_2 ∈P, 𝛼_1, 𝛼_2∈(N∪𝛴)^\ast$

Item $LR(0)$ est valide pour $𝛾∈(N∪ 𝛴)^\ast$ :

ssi $S ⟹^\ast_{rm} 𝛾’ A u ⟹_{rm} 𝛾’𝛼_1𝛼_2 u$ avec $𝛾’𝛼_1 = 𝛾$.

On note $V_0(𝛾)$ l’ens. des items valides de $𝛾$.

Équivalence de $LR(0)$ :
\[𝛾 \sim_0 𝛾' ⟺ V_0(𝛾)= V_0(𝛾')\]

NB :

  • $\sim_0$ est d’index fini $≤ \underbrace{2^{\vert G \vert}}_{\text{nb max. d'ens. d'items, puisqu'il y a } \vert G \vert \text{ items}}$ où $G ≝ \sum\limits_{A⟶𝛼∈P} \vert 𝛼 \vert+1$
$𝛾$ est viable :

ssi \(S ⟹_{rm}^\ast 𝛾'Au ⟹_{rm} 𝛾'𝛼_1 𝛼_2 u = 𝛾𝛼_2 u\) ssi $V_0(𝛾) ≠∅$

  • \[𝛾 \sim_0 𝛾' ∧ 𝛾X, 𝛾'X \text{ viables } ⟹ 𝛾X \sim_0 𝛾'X\]

  • si $A⟶ 𝛼_1 \cdot B 𝛼_2 ∈ V_0(𝛾)$, alors $B⟶ \cdot 𝛽 ∈ V_0(𝛾)$ $∀B⟶ 𝛽∈P$ :

    \[S ⟹_{rm}^\ast 𝛾'Au ⟹_{rm} 𝛾' 𝛼_1 B 𝛼_2 u \quad (A⟶ 𝛼_1 \cdot B 𝛼_2) \\ ⟹_{rm}^\ast 𝛾'𝛼_1 B v u \\ ⟹_{rm} 𝛾'𝛼_1 𝛽 v u (B ⟶ \cdot 𝛽)\]
  • Si $𝛾 =𝜀$, alors $\lbrace S⟶ \cdot 𝛼 \mid S⟶𝛼 ∈ P\rbrace⊆ V_0(𝜀)$
Automate des contextes :

un automate fini $𝒞 ≝ (Q, N∪ 𝛴, goto, q_0)$ dét. complet, où :

  • $q_0 ≝ V_0(𝜀)$
  • $Q ≝ \lbrace V_0(𝛾) \mid 𝛾∈(N∪𝛴)^\ast \rbrace$
  • $goto(q, X) ≝ V_O(𝛾X)$ si $q = V_0(𝛾)$
Construction des $V_0(𝛾)$ :

Clôture de $E⊆ \lbrace A⟶𝛼_1 \cdot 𝛼_2 \mid A⟶ 𝛼_1 𝛼_2 ∈ P \rbrace$

\[\overline{E} ≝ 𝜇x . E ∪ \lbrace B ⟶ \cdot 𝛽 \mid A ⟶ 𝛼_1 \cdot B 𝛼_2 ∈ x \rbrace\]

Transitions $goto$ :

\[goto(E, X) ≝ \overline{\lbrace S ⟶ 𝛼 \mid S ⟶ 𝛼 ∈P\rbrace}\]

Ex :

  digraph {
    A[label="q_0 \n S'⟶ .S$ \n S ⟶ .aA \n S⟶ .bB \n S⟶ .cC", shape="square"];
    B[shape="square", label="q_7 \n S'⟶S.$"];

    C[shape="box3d", label="q_8 \n S'⟶S$."];

    D[shape="square", label="q_1 \n S⟶a.A\n A⟶.aAb \n A⟶.ab"];

    E[shape="square", label="q_5 \n S⟶aA."];

    F[shape="square", label="q_2 \n A⟶a.Ab\n A⟶a.b\n A⟶.aAb\n A⟶.ab"];

    G[shape="square", label="q_4 \n A⟶aA.b"];

    H[shape="square", label="q_6 \n A⟶aAb."];

    I[shape="square", label=" q_3 \n A⟶ab."];

    A -> B[label="S"];
    A -> D[label="a"];
    B -> C[label="$"];
    D -> E[label="A"];
    D -> F[label="a"];
    F -> G[label="A"];
    F -> F[label="a"];
    G -> H[label="b"];
    F -> I[label="b"];

  }
Automate à pile $LR(0)$ :

on construit l’automate de contextes de $G$.

\[𝒜≝ (𝛤, 𝛴, 𝛿, q_0, F ≝ V_0(S\$)) \\ 𝛿 ≝ \lbrace (q q_1 ⋯ q_m, 𝜀, qq') \mid A⟶X_1 ⋯ X_m \cdot ∈ q_m \text{ et } goto(q, A) = q' \rbrace \quad \text{ (reduce)} \\ ∪ \lbrace (q, a, qq') \mid a∈𝛴, A⟶𝛼_1 \cdot a 𝛼_2 ∈ q \text{ et } goto(q, a) = q' \rbrace \quad \text{ (shift)}\]

Ex :

\[\begin{align*} q_0 &⟶^a q_0 q_1 ⟶^a q_0 q_1 q_2 &&q_0 aa \\ &⟶^a q_0 q_1 q_2 q_3 &&q_0 aaa \\ &⟶^b q_0 q_1 q_2 q_2 q_3 &&q_0 aaa b \\ &⟶^𝜀 q_0 q_1 q_2 q_4 &&q_0 aa A \\ &⟶^b q_0 q_1 q_2 q_4 q_6 &&q_0 aa A b \\ &⟶^𝜀 q_0 q_1 q_5 &&q_0 a A \\ &⟶^𝜀 q_0 q_7 \\ &⟶^𝜀 q_0 q_7 q_8 && \text{ (accepte)} \\ \end{align*}\]

Ex :

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

Automate de contextes :

  digraph {
    A[label="q_0 \n S'⟶ .E$ \n E ⟶ .E + T \n E⟶ .T \n T⟶ .T * F \n T ⟶ .F \n F ⟶ .(E) \n F ⟶ .i", shape="square"];

    B[shape="square", label="q_7 \n S'⟶S.$"];

    C[shape="box3d", label="q_8 \n S'⟶S$."];

    D[shape="square", label="q_1 \n S⟶a.A\n A⟶.aAb \n A⟶.ab"];

    E[shape="square", label="q_5 \n S⟶aA."];

    F[shape="square", label="q_2 \n A⟶a.Ab\n A⟶a.b\n A⟶.aAb\n A⟶.ab"];

    G[shape="square", label="q_4 \n A⟶aA.b"];

    H[shape="square", label="q_6 \n A⟶aAb."];

    I[shape="square", label=" q_3 \n A⟶ab."];

    A -> B[label="S"];
    A -> D[label="a"];
    B -> C[label="$"];
    D -> E[label="A"];
    D -> F[label="a"];
    F -> G[label="A"];
    F -> F[label="a"];
    G -> H[label="b"];
    F -> I[label="b"];

  }
$SLR(k)$ :

$∀𝛾, ∀A_1 ⟶ 𝛼_1 \cdot ≠ A_2 ⟶ 𝛼_2 \cdot ∈ V_0(𝛾)$,

\[Suiv_k(A_1) ∩ Suiv_k(A_2) = ∅\]

et $∀𝛾, ∀ A_1 ⟶ 𝛼\cdot, A_2 ⟶ 𝛼_1 \cdot a 𝛼_2 ∈ V_0(𝛾)$,

\[Suiv_k(A_1)∩ Prem_k(a 𝛼_2 Suiv_k(A_2)) = ∅\]

Ex : \(Suiv_1(E) = \lbrace \$, +, )\rbrace\)

la grammaire est $SLR(1)$

$LALR(k)$ :
\[LA_k(A⟶ 𝛼, 𝛾) ≝ \lbrace k:w \mid ∃𝛾' 𝛼_1 \sim_0 𝛾; S' ⟹_{rm}^\ast 𝛾'A' u ⟹_{rm} 𝛾' 𝛼_1 𝛼_2 u ⟹^\ast_{rm} 𝛾' 𝛼_1 w\rbrace \\ ⊆ Suiv_k(A)\]

remplacer $Suiv_k$ par $LA_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 $SLL(1)$ non $LALR(k)$ :

\[∀k, LL(k)⊆LR(k)\]

Leave a comment