Remerciez-le!

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

14/12/2021 1 2021-2022 Chapitre 3: Langages hors-contexte et automates à piles

14/12/2021 1 2021-2022 Chapitre 3: Langages hors-contexte et automates à piles Enseignant: Manel Ben Salem 1 Niveau: 2ième Licence SI Plan du cour 2 Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 1. Grammaires hors-contexte 2. Arbres syntaxiques 3. Automates à piles 4. Automates à piles déterministes 14/12/2021 2 Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 3 1. Grammaire hors-contexte • Certains langages ne peuvent pas être décrits par une grammaire régulière, et ne peuvent donc pas être reconnus par un automate fini (par exemple le langage {anbn/n > 0}), →Appartiennent à une classe de langages plus générale que celle des langages réguliers : la classe des langages hors-contexte, décrits par des grammaires hors-contextes et reconnus par des automates à pile. • Définition (Grammaire hors-contexte) : G = (T, N, S, R) est une grammaire hors-contexte si toutes les règles de R sont de la forme: A →w avec A ∈N et w ∈(N ∪T)∗. • Définition (Langage hors-contexte) : On appelle langage hors-contexte un langage généré par une grammaire hors contexte. • On rappelle qu’un ensemble est fermé relativement à une opération à n opérandes si tout résultat de cette opération appliquée à n éléments de l’ensemble appartient encore à l’ensemble. Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 4 1. Grammaire hors-contexte • Théorème : −l’union de deux langages hors-contexte est un langage hors-contexte, −le produit de deux langages hors-contexte est un langage hors-contexte, −l’itéré d’un langage hors contexte est un langage hors contexte. En effet, soient deux langages : L1 généré par la grammaire G1 = (T1, N1, S1, R1) et L2 généré par la grammaire G2 = (T2, N2, S2, R2), tels que N1 ∩N2 = ∅(si tel n’est pas le cas, on renomme certains éléments non-terminaux) alors : −Le langage L1 ∪L2 est généré par la grammaire hors contexte G = (T, N, S, R) telle que : →T = T1 ∪T2, →S est un nouveau symbole non terminal (S ∈N1 ∪N2), →N = N1 ∪N2 ∪{S}, →R = R1 ∪R2 ∪{S →S1, S →S2}. 14/12/2021 3 Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 5 1. Grammaire hors-contexte −Le langage L1.L2 est généré par la grammaire hors contexte G = (T, N, S, R) telle que: →T = T1 ∪T2, →S est un nouveau symbole non terminal (S ∈N1 ∪N2), →N = N1 ∪N2 ∪{S}, →R = R1 ∪R2 ∪{S →S1S2}. −Le langage L1∗est généré par la grammaire hors contexte G = (T1, N, S, R) telle que: →S est un nouveau symbole non terminal (S ∈N1 ∪N2), →N = N1 ∪{S}, →R = R1 ∪{S →S1S, S →ε}. En revanche, l’intersection de deux langages hors-contexte et le complémentaire d’un langage hors-contexte ne sont pas nécessairement des langages hors-contexte. Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 6 2. Arbre syntaxique • Dans le cas d’une grammaire hors-contexte G, on peut représenter la dérivation d’une phrase de L(G) à partir de l’axiome à l’aide d’un arbre syntaxique (ou arbre d’analyse ou arbre de dérivation). • Cette représentation fait abstraction de l’ordre d’application des règles de la grammaire et aide à la compréhension de la syntaxe de la phrase considérée. • Définition (Arbre syntaxique) : L’arbre syntaxique d’une phrase de la grammaire hors-contexte G = (T, N, S, R) est un arbre tel que: − la racine est étiquetée par le symbole de départ S, −chaque nœud interne est étiqueté par un symbole non terminal de N, −chaque feuille est étiquetée par un symbole terminal de T, −pour tout nœud interne, si son étiquette est le symbole non terminal A, et si ses n fils ont respectivement pour étiquettes X1, X2, ..., Xn, alors A →X1X2...Xn doit être une règle de R. 14/12/2021 4 Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 7 2. Arbre syntaxique • Remarques : −La lecture de gauche à droite des feuilles de l’arbre reconstitue la phrase que l’arbre représente. −Etant donnée une grammaire hors-contexte G, une phrase w est générée par G si et seulement si il existe un arbre syntaxique pour G qui génère w. • Exemple: −Considérons la grammaire G dont les règles sont : PH →GN V GN; GN →D N; N →fille; N → jouet; D →le; D →la; V →regarde. −L’arbre syntaxique associé au mot « la fille regarde le jouet » est : D GN V GN PH N D N la fille le jouet regarde Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 8 2. Arbre syntaxique • Définition (Phrase ambigüe) : Une phrase, générée par une grammaire, est ambigüe si elle admet plus d’un arbre syntaxique pour cette grammaire. • Définition (Grammaire ambigüe) : Une grammaire est ambigüe si elle génère au moins une phrase ambigüe. • Exemple: Considérons par exemple la grammaire G = (T, N, E, R) avec : T = { Id, +, -, *, /, (, ) } (où Id signifie identificateur); N = { E, Op }; R = { E →Id | ( E ) | E Op E ; Op →+ | - | * | / } et considérons les deux arbres suivants : E E E Op E Op Id Id Id * E + Op E E Id + E E Op Id Id E * 14/12/2021 5 Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 9 2. Arbre syntaxique • Dans les deux cas, la phrase associée est « Id + Id * Id ». • On a donc deux arbres de dérivation pour une même phrase, et la grammaire G est ambigüe. • En l’occurrence, on ne peut pas savoir si l’on commence par l’addition ((Id+Id)*Id) ou la multiplication (Id+(Id*Id)). • Remarques : −Le terme "ambigu" est appliqué à la grammaire et non au langage : il est souvent possible de transformer une grammaire ambigüe en une grammaire non ambigüe générant le même langage. Cependant, il existe des langages pour lesquels il n’existe pas de grammaire non ambigüe ; de tels langages sont dits intrinsèquement ambigus. −La propriété d’ambigüité est indécidable : cela signifie qu’il n’existe pas – et ne peut pas exister – d’algorithme général qui, étant donnée une grammaire hors-contexte, puisse déterminer en un temps fini si la grammaire est ambigüe ou non. Seules peuvent être déterminées des conditions suffisantes assurant la non-ambigüité. Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 10 3. Automates à pile • Les langages hors-contexte mais non régulier ne sont pas reconnaissables par un automate à états finis, • Par exemple, il n’existe pas d’automate à états finis ni d’expression régulière reconnaissant le langage{anbn, n>=0} →pour les reconnaitre on a besoin d’un outils plus puissant: les automates à piles. • Définition (Automate à pile) : Un automate à pile est un quintuplet A = (T, P, Q, M, S0) tel que : −T est le vocabulaire terminal, −P est le vocabulaire de pile (contenant en particulier un symbole initial de pile vide, noté ⊥), −Q est un ensemble fini d’états, −M est un ensemble de transitions, −S0 ∈Q est l’état initial. 14/12/2021 6 Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 11 3. Automates à pile • Le vocabulaire de pile contient l’ensemble des symboles qui pourront apparaître sur la pile, et n’est pas nécessairement distinct du vocabulaire terminal (on peut avoir T ∩P ≠∅). • Une transition de l’automate à pile est semblable à celle d’un automate fini, à part qu’elle spécifie en plus la manipulation de la pile. • Une transition de M est de la forme (état, symbole_lu, sommet_pile) →(nouvel_état, action_sur_pile) tel que: −Etat et nouvel_état sont des états de Q, −symbole_lu est soit un symbole terminal de T, soit , signifiant que l’automate ne regarde pas le mot, −sommet_pile est soit un symbole de P, soit , signifiant que l’automate ne regarde pas le sommet de la pile, −action_sur_pile est soit : “dépiler le symbole au sommet de la pile”, ou “dépiler le symbole au sommet de la pile puis empiler une suite de symboles” ou “empiler une suite de symboles”, ou “ne rien faire”. • De façon informelle, la transition (Si , u, v) →(Sk, action_sur_pile) signifie que l’automate peut passer de l’état Si à l’état Sk, pour autant que le mot à analyser commence par le symbole u et que la pile ait en sommet le symbole v. Théorie des langages et des automates Chapitre 3: Langages hors-contexte et automates à piles 12 3. Automates à pile • Après la transition, l’automate a consommé le symbole u du mot à analyser et a effectué l’action spécifiée dans action_sur_pile. • Un triplet (Si , u, v) est appelé une situation. • Les automates à pile que uploads/Philosophie/ chapitre-3-automates-a-piles.pdf