Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’an

Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique Automates ` a pile Mirabelle Nebut Bureau 203 - extension M3 mirabelle.nebut at lifl.fr 2012-2013 Mirabelle Nebut Automates ` a pile 2/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique But de ce cours On sait maintenant ´ ecrire une grammaire alg´ ebrique. . . mais pas l’analyseur syntaxique qui va avec ! langage sp´ eciﬁcation mod` ele ex´ ecutable r´ egulier expression r´ eguli` ere AFD alg´ ebrique grammaire alg´ ebrique automate ` a pile Dans un premier temps : d´ ecouverte des automates ` a pile. Plus tard : comment on s’en sert pour l’analyse syntaxique. Mirabelle Nebut Automates ` a pile 3/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique Plan du cours Automates ` a pile g´ en´ eraux D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes L’automate des items Les diﬀ´ erents types d’analyse syntaxique Mirabelle Nebut Automates ` a pile 4/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Reconnaˆ ıtre un langage alg´ ebrique, intuition - 1 Pour reconnaˆ ıtre {anbn | n ≥0} : ▶un automate ` a nombre ﬁni d’´ etats pour lire des a puis des b ; ▶un compteur c pour compter les a et d´ ecompter les b ; ▶arrˆ et quand le ruban est vide et ´ etat ﬁnal et c vaut 0 . [c=0] c:=0 a / c := c+1 [c=0] b [ c≥1] / c := c-1 qb qa b [ c≥1] / c := c-1 Mirabelle Nebut Automates ` a pile 5/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Reconnaˆ ıtre un langage alg´ ebrique, intuition - 2 Pour reconnaˆ ıtre {m ∈Σ∗| m est un palindrome } : ▶un compteur ne suﬃt pas ! ▶il faut m´ emoriser les symboles lus puis les consulter ; ▶m´ emorisation par empilement, v´ eriﬁcation par d´ epilement. pile vide a / empiler luA b / empiler luB a,b a [top = luA] / depiler luA b [top = luB] / depiler luB [pile vide] ϵ q1 q2 Mirabelle Nebut Automates ` a pile 6/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Reconnaˆ ıtre un langage alg´ ebrique, intuition - 3 C ¸a marche aussi pour reconnaˆ ıtre {anbn|n ≥0} : ▶on empile luA quand on lit un a ; ▶on d´ epile luA quand on lit un b ; ▶arrˆ et quand le ruban est vide et ´ etat ﬁnal et la pile est vide. a / empiler luA [pile vide] [pile vide] qa b [top = luA] / depiler luA vide pile qb b [top = luA] / depiler luA Et ¸ ca marche pour tous les langages alg´ ebriques ! Mirabelle Nebut Automates ` a pile 7/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Automates ` a pile g´ en´ eraux D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes L’automate des items Les diﬀ´ erents types d’analyse syntaxique Mirabelle Nebut Automates ` a pile 8/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Automate ` a pile, intuition un automate ` a nombre ﬁni d’´ etats classique + une pile non born´ ee Et voil` a notre m´ emoire non born´ ee ! Mirabelle Nebut Automates ` a pile 9/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Automate ` a pile, intuition Automate ` a nombre ﬁni d’´ etats ex des palindromes : ▶ensemble d’´ etat Q ; ex : {q1, q2} ▶´ etat initial q0 ; ex : q1 ▶ensemble d’´ etats ﬁnaux F ⊆Q ; ex : {q2} ▶alphabet d’entr´ ee Σ. ex : {a,b} Pile ▶contient des ´ el´ ements de l’alphabet de pile Z ex : {luA, luB} Relation de transition ? Mirabelle Nebut Automates ` a pile 10/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Transitions, intuition - 1 Pour un AF, une transition c’est : ▶quand je suis dans l’´ etat q ∈Q ▶et que j’ai a ∈Σ sous la tˆ ete de lecture ▶ou que je transite sur ϵ ▶alors je passe dans l’´ etat q′ ∈Q q, a →q′ q, ϵ →q′ Mirabelle Nebut Automates ` a pile 11/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Transitions, intuition - 2 Pour un automate ` a pile, une transition c’est : ▶quand je suis dans l’´ etat q ∈Q ▶et que j’ai a ∈Σ sous la tˆ ete de lecture ▶ou que j’eﬀectue une ϵ-transition ▶et que le sommet de pile est z ∈Z ▶je passe dans l’´ etat q′ ∈Q ▶et je modiﬁe le sommet de pile en le rempla¸ cant par des ´ el´ ements de Z ou ϵ. q, a, z → q′, z1z2 q, ϵ, z → q′, z q, a, z → q′, ϵ Mirabelle Nebut Automates ` a pile 12/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Modiﬁcation de la pile, exemples q, a, z1 → q′, z1z2 empiler z2 q, ϵ, z → q′, z ne pas toucher ` a la pile q, a, z → q′, ϵ d´ epiler z Mirabelle Nebut Automates ` a pile 13/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Notation graphique a [luA] / empiler luA a [luB] / empiler luA a [luA] / empiler luA a [luA,luB] / empiler luA q1 q2 ⇔ ⇔ q1 q2 q1 q2 (q1, a, luA) →(q2, luAluA) Mirabelle Nebut Automates ` a pile 14/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Exemple des palindromes - 1 q2 b [luB] / depiler luB ϵ[z⊥] / depiler z⊥ a [luA] / depiler luA q1 b [luA, luB, z⊥] / empiler luB a [luA, luB, z⊥] / empiler luA a,b[luA,luB,z⊥] ϵ [luA,luB,z⊥] ▶dans l’´ etat q2 ∈Q ; ▶avec a ∈Σ sous la tˆ ete de lecture (Σ-transition) ; ▶et avec luA ∈Z en sommet de pile ; ▶alors on reste dans l’´ etat q2 ∈Q ; ▶et on d´ epile : on remplace luA par ϵ. q2, a, luA →q2, ϵ Mirabelle Nebut Automates ` a pile 15/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Exemple des palindromes - 2 q1 b [luA, luB, z⊥] / empiler luB a [luA, luB, z⊥] / empiler luA a,b[luA,luB,z⊥] ϵ [luA,luB,z⊥] q2 b [luB] / depiler luB ϵ[z⊥] / depiler z⊥ a [luA] / depiler luA ▶dans l’´ etat q1 ∈Q et avec a sous la tˆ ete de lecture ; ▶et quel que soit le sommet de pile. . . quel peut-il ˆ etre ? ▶si je viens de lire un a (resp. b) : luA (resp. luB) ; ▶si je n’ai encore rien lu : pile initiale (vide) Pas de transition sur pile vide : symbole initial de pile z⊥∈Z Mirabelle Nebut Automates ` a pile 16/64 Automates ` a pile g´ en´ eraux L’automate des items Les diﬀ´ erents types d’analyse syntaxique D´ eﬁnitions Les crit` eres d’acceptation Langages et automates d´ eterministes Exemple des palindromes - 3 q1 b [luA, luB, z⊥] / empiler luB a [luA, luB, z⊥] / empiler luA a,b[luA,luB,z⊥] ϵ [luA,luB,z⊥] q2 b [luB] / depiler luB ϵ[z⊥] / depiler z⊥ a [luA] / depiler luA ▶dans l’´ etat q1 ∈Q, avec a sous la tˆ ete de lecture ; ▶et avec luA, luB ou z⊥en sommet de pile ; ▶alors on reste dans q1 ∈Q ; ▶et on empile luA : on remplace le sommet x par x luA q1, a, luA →q1, luA luA q1, a, z⊥→q1, z⊥luA q1, a, luB →q1, luB luA (lecture bas uploads/Management/ aut-pile-transp.pdf