Remerciez-le!

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

Th´ eorie des langages Grammaires Hors-Contexte Elise Bonzon http://web.mi.pari

Th´ eorie des langages Grammaires Hors-Contexte Elise Bonzon http://web.mi.parisdescartes.fr/∽bonzon/ elise.bonzon@parisdescartes.fr 1 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires Hors-Contexte D´ eﬁnitions Grammaires r´ eduites Grammaires propres Formes normales 2 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires Hors-Contexte D´ eﬁnitions Grammaires r´ eduites Grammaires propres Formes normales 3 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaire Hors-Contexte Grammaire Hors-Contexte ou alg´ ebrique Une grammaire G = ⟨V , Σ, P, S⟩est hors-contexte (ou alg´ ebrique) si V est un alphabet Σ ⊆V est l’ensemble des symboles terminaux V \ Σ est l’ensemble des symboles non terminaux S ∈V \ Σ est le symbole de d´ epart P ⊆((V \ Σ) × V ∗) est l’ensemble (ﬁni) de r` egles de production 4 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaire Hors-Contexte Grammaire Hors-Contexte ou alg´ ebrique Une grammaire G = ⟨V , Σ, P, S⟩est hors-contexte (ou alg´ ebrique) si V est un alphabet Σ ⊆V est l’ensemble des symboles terminaux V \ Σ est l’ensemble des symboles non terminaux S ∈V \ Σ est le symbole de d´ epart P ⊆((V \ Σ) × V ∗) est l’ensemble (ﬁni) de r` egles de production Langage alg´ ebrique Un langage L est alg´ ebrique s’il existe une grammaire alg´ ebrique telle que L(G) = L 4 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaire Hors-Contexte Cons´ equence : Tout langage rationnel est alg´ ebrique. ATTENTION: la r´ eciproque est fausse Un langage alg´ ebrique non rationnel n’est pas reconnu par un automate ﬁni n’est pas d´ ecrit par une expression r´ eguli` ere il n’existe pas de grammaire r´ eguli` ere pour l’engendrer. 5 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Rappel : hierarchie de Chomsky Type 0 Pas de restriction Type 1 Grammaires contextuelles (ou sensibles au contrˆ ole) (Context-sensitive) α →β, |α| ≤|β|, α ∈V + Type 2 Grammaires hors-contexte (Context-Free) A →β Type 3 Grammaires r´ eguli` eres (ou lin´ eaires ` a droite) A →wB A, B ∈V \ Σ non terminaux A →w w ∈Σ∗ terminaux 6 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Rappel : hierarchie de Chomsky T0 T1 Context sensitive Machine de Turing T2 Context Free Automate ` a pile T3 R´ eguliers Automate ﬁni 7 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaire hors contexte : exemple Soit G = ⟨V , Σ, P, S⟩avec Σ = {a, b} V \ Σ = {S} Axiome S 3 r` egles de production : S →aSb S →ϵ L(G) = {anbn|n ≥0} 8 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaire hors contexte : langage PASCAL instruction → ϵ |variable := expression |begin liste-instructions end |if expression then instruction |if expression then instruction else instruction |case expression of liste-case end |while expression do instruction |repeat instruction until expression |for varid := liste-pour do instruction |identiﬁcateur-procedure |identiﬁcateur-procedure(liste-expressions) |goto etiquette |with liste-variables-record do instruction |etiquette : instruction 9 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaire hors contexte : langage PASCAL instruction → ϵ |variable := expression |begin liste-instructions end |if expression then instruction |if expression then instruction else instruction |case expression of liste-case end |while expression do instruction |repeat instruction until expression |for varid := liste-pour do instruction |identiﬁcateur-procedure |identiﬁcateur-procedure(liste-expressions) |goto etiquette |with liste-variables-record do instruction |etiquette : instruction Symboles terminaux : begin, if, then, else, end, case, of, while... Les variables (ou symboles non terminaux) sont d´ eﬁnies dans d’autres r` egles ⇒Grammaire Pascal : plus de 300 r` egles 9 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Analyse syntaxique Les langages de programmation sont des langages alg´ ebriques. Ils sont sp´ eciﬁ´ es par des grammaires alg´ ebriques Dans sa phase d’analyse syntaxique, un compilateur teste si un programme est bien un ´ el´ ement du langage de programmation dans lequel il est ´ ecrit. Pour un programme donn´ e, le compilateur essaie de reconstituer l’arbre de d´ erivation (ou arbre syntaxique) de bas en haut en proc´ edant par r´ eductions successives : on parle alors d’analyse ascendante. A l’issue de cette phase, on sait si notre programme est syntaxiquement correct ou pas 10 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires Hors-Contexte D´ eﬁnitions Grammaires r´ eduites Grammaires propres Formes normales 11 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires r´ eduites Symbole non terminal utile Soit G = ⟨V , Σ, P, S⟩. Un symbole non terminal X ∈V \ Σ est Productif si LG(X) ̸= ∅ Accessible s’il existe des mots α, β tels que S ∗ − → G αXβ Utile s’il est productif, qu’il existe des mots α, β tels que S ∗ − → G αXβ et tels que α et β ne contiennent que des symboles non terminaux productifs. 12 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires r´ eduites Symbole non terminal utile Soit G = ⟨V , Σ, P, S⟩. Un symbole non terminal X ∈V \ Σ est Productif si LG(X) ̸= ∅ Accessible s’il existe des mots α, β tels que S ∗ − → G αXβ Utile s’il est productif, qu’il existe des mots α, β tels que S ∗ − → G αXβ et tels que α et β ne contiennent que des symboles non terminaux productifs. Grammaire r´ eduite Une grammaire est r´ eduite si tous ses symboles non terminaux sont utiles. 12 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires r´ eduites Symbole non terminal utile Soit G = ⟨V , Σ, P, S⟩. Un symbole non terminal X ∈V \ Σ est Productif si LG(X) ̸= ∅ Accessible s’il existe des mots α, β tels que S ∗ − → G αXβ Utile s’il est productif, qu’il existe des mots α, β tels que S ∗ − → G αXβ et tels que α et β ne contiennent que des symboles non terminaux productifs. Grammaire r´ eduite Une grammaire est r´ eduite si tous ses symboles non terminaux sont utiles. En supprimant les variables inutiles dans une grammaire, on ne change pas le langage engendr´ e – sauf si l’axiome lui-mˆ eme est inutile, c’est-` a-dire si la grammaire engendre le langage vide. 12 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Algorithme de calcul des symboles non terminaux productifs 1. Calculer l’ensemble V0 des symboles non terminaux X pour lesquels il existe une r` egle X →α, α ∈Σ∗ 2. Calculer l’ensemble Vi+1 form´ e de Vi et des symboles non terminaux X pour lesquels il existe une r` egle X →α, α ∈(Σ ∪Vi)∗ 3. Arrˆ eter lorsque Vi+1 = Vi. Cet ensemble est l’ensemble des symboles non terminaux productifs. 13 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Algorithme de calcul des symboles non terminaux accessibles 1. Poser W0 = {S} 2. Calculer l’ensemble Wi+1 form´ e de Wi et des symboles non terminaux X pour lesquels il existe une r` egle Y →αXβ, avec Y ∈Wi 3. Arrˆ eter lorsque Wi+1 = Wi. Cet ensemble est l’ensemble des symboles non terminaux accessibles. 14 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Algorithme de r´ eduction d’une gram- maire 1. D´ eterminer l’ensemble des symboles non terminaux productifs 2. Supprimer les symboles non terminaux non productifs, ainsi que les r` egles dans lesquels ils ﬁgurent 3. Si l’axiome S est improductif, la grammaire r´ eduite a pour seul symbole non terminal S, et un ensemble de r` egles vide 4. Si l’axiome S est productif, d´ eterminer tous les symboles non terminaux accessibles ` a partir de S. Ceci permet d’obtenir l’ensemble des symboles non terminaux utiles. 5. Supprimer tous les autres symboles non terminaux, ainsi que les r` egles dans lesquelles ils ﬁgurent. La grammaire ainsi obtenue est r´ eduite. 15 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Algorithme de r´ eduction d’une gram- maire : exemple On consid` ere la grammaire ayant les r` egles suivantes : S → a|X X → XY Y → b Symboles non terminaux productifs : {S, Y }. X est donc improductif, on peut le supprimer On obtient la grammaire S → a Y → b L’ensemble des symboles non terminaux accessibles est {S}. On supprime Y S → a La grammaire est r´ eduite. 16 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Algorithme de r´ eduction d’une gram- maire : exemple 2 On consid` ere la grammaire ayant les r` egles suivantes : S → XYZW X → cX Y → ab Z → cYa|WSW W → ϵ Symboles non terminaux productifs : {Y , Z, W }. S est donc improductif. La grammaire r´ eduite a donc pour seul symbole non terminal S, et un ensemble de r` egles vide 17 / 31 Th´ eorie des langages ▲ Grammaires Hors-Contexte Grammaires Hors-Contexte D´ eﬁnitions Grammaires r´ eduites Grammaires propres Formes normales 18 / 31 uploads/s3/ 05-grammaires-hors-contexte.pdf