Cours.article

Description

Modèles de Langage et Analyse SyntaxiqueCours 2 - SyntaxeAntoine [e-mail]7 octobre 201016Plan1 Introduction 12 Grammaires formelles 12.1 Définitions : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Hiérarchie des grammaires formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.1 type 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.2 type 3 : grammaires régulières = grammaires rationnelles . . . . . . . . . . . . . . 22.2.3 type 2 : grammaires hors-contexte = grammaires algébriques . . . . . . . . . . . . 32.2.4 type 1 : grammaires contextuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2.5 type 0 : grammaire non-contrainte . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Forme Normale de Chomsky 51 IntroductionDans les exemples vus jusqu’ici on s’est limité à des règles de réécritures qui avaient toutes la forme :X !Y ... Y1 noù X est un symbole non-terminal de la grammaire, et Y ... Y sont soit des symboles non-terminaux,1 nsoit des symboles terminaux.Il s’agit en fait d’un type bien particulier de grammaires de réécriture, appelées grammaires hors-contexte, pour lequel on maîtrise des algorithmes d’analyse efficaces, comme on va le voir (plus tard!). Ilen existe d’autres types.Le pionnier en matière de grammaire de réécritures est Noam Chomsky. Dans la suite, on va voir :– ...

Informations

• Publié par: Bavem
• Nombre de lectures: 37
• Langue: Français

Extrait

Modèles de Langage et Analyse Syntaxique Cours 2  Syntaxe

Antoine Rozenknop [e-mail]paris13.fr 7 octobre 2010

1

Plan

1 Introduction1 2 Grammairesformelles 1 2.1 Définitions: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 2.2 Hiérarchiedes grammaires formelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 2.2.1 type4 .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 2.2.2 type3 : grammaires régulières = grammaires rationnelles. . . . . . . . . . . . . .2 2.2.3 type2 : grammaires horscontexte = grammaires algébriques. . . . . . . . . . . .3 2.2.4 type1 : grammaires contextuelles .. . . . . . . . . . . . . . . . . . . . . . . . . . .4 2.2.5 type0 : grammaire noncontrainte. . . . . . . . . . . . . . . . . . . . . . . . . . .5 3 FormeNormale de Chomsky5

1 Introduction

Dans les exemples vus jusqu’ici on s’est limité à des règles de réécritures qui avaient toutes la forme : X→Y 1 . . .Y n où X est un symbolenonterminalde la grammaire, et Y 1 . . .Y n sont soit des symboles nonterminaux, soit des symboles terminaux. Il s’agit en fait d’un type bien particulier de grammaires de réécriture, appeléesgrammaires hors contexte!). Il, pour lequel on maîtrise des algorithmes d’analyse efficaces, comme on va le voir (plus tard en existe d’autres types. Le pionnier en matière de grammaire de réécritures est Noam Chomsky. Dans la suite, on va voir : – laclassification des grammaires formelles issue de ses travaux; – cequ’est laforme normale de Chomsky; – commenton peut transformer une grammaire horscontexte quelconque pour obtenir une grammaire équivalente sous forme normale de Chomsky. L’intérêt de cette transformation, qui n’est pas évident au premier abord, apparaîtra clairement lors qu’on s’intéressera aux algorithmes d’analyse syntaxique des grammaires horscontexte. Mais chaque chose en son temps!

2 Grammairesformelles 2.1 Définitions: Grammaire formelle –V: Vocabulaire –V T : Vocabulaire terminal (ensemble de symboles terminaux) –V N : Vocabulaire nonterminlal (ensemble de symboles nonterminaux) –P: Axiome (élément de V N ) (un symbole nonterminal) –R: ensemble de règles de récritures de la forme :α→βavec ∗ –α,β∈V –α6=∅

Définition 1.Une grammaire formelleGest un quadruplet (V N , V T , R, P).

Dérivation Définition 2.Une chaîneu 1 se réécriten une chaîneu 2 (u 1 ⇒u 2 ) si et seulement si il existe des chaînes de symbolesv 1 ,v 2 ,α,βtels que : 1.u 1 =v 1 α v 2 u 2 =v 1 β v 2 2.α=βou(α→β)∈R ∗ Définition 3.Une chaîneu 1 se dériveen une chaîneu 2 (u 1 ⇒u 2 ) si unesuccessionde réécritures permet d’obteniru 2 à partir deu 1 . Définition 4.Une dérivation est une succession de réécritures.

Langage Définition 5.On appellelangage engendré par Gl’ensemble de toutes les suites de symboles qui dérivent de l’axiome de G : ∗ ∗ L(G)={x/x∈PV et⇒x} Définition 6.On appellelangage sur V T l’ensemble (potentiellement infini) des chaînes delongueurs finiesformées avec des éléments du vocabulaire terminal V T .

Décidabilité Définition 7.Un langage estdécidablesi pour toute phrase on peut savoir au bout d’untemps finisi elle appartient ou nom au langage.

2.2 Hiérarchiedes grammaires formelles La hiérarchie des grammaires formelles décrite par N. Chomsky classe les grammaires de réécriture selon la forme que peut prendre leurs règles. On les donne en ordre inverse, c’estàdire de la forme la plus restrictive à la moins restrictive.

2.2.1 type4 Dans une grammaire de type 4,les parties droites de toutes les règles sont des terminaux. Les éléments de R ont donc la forme :

X→αavec X∈V N α∈V T *

Une telle grammaire ne fait qu’énumérerles phrases de son langage sur V T .

2.2.2 type3 : grammaires régulières = grammaires rationnelles Définition 8.Dans une grammairerégulière à gauche, les règles ont l’une des formes suivantes :   X→X, YY a∈V N avec X→a a∈V T Définition 9.Dans une grammairerégulière à droite, les règles ont l’une des formes suivantes :   X→a YX, Y∈V N avec X→a a∈V T

Exemple de grammaire régulière à droite P→Pa P→B B→b B→b B

n m Cette grammaire engendre les chaînesa b. ab aab abb aaabbbbbb ...

Utilité en TAL Les grammaires régulières sont utilisées dans : – lareprésentation compacte deslexiques – laconstruction decorrecteurs orthographiquesou de lexiquesrobustesaux erreurs – desgrammaires locales: motscomposés, séquences acceptables de chiffres (nombres,dates) – desgrammaires pour desdomaines très restreints(annonces de vols dans les aéroports)

Limitations Les grammaires de type 3 ne peuvent traiter : n n – leschaînesa bde typea 1 . . . a n b 1 . . . b n (“respectivement”) n n – leschaînesa bde typea 1 . . . a n b n . . . b 1 (expressionsparenthésées, structures enchâssées) : En anglais : The dog the stick the fire burned beat bit the cat En français : Le chat que le voisin que le maire que le préfet qui a été condamné a félicité a attrapé est blanc. – leschaînesabac soit. . .soit. . .ni. . .ni. . . – lerejeten fin de phrase des prépositions (en anglais) ou des particules séparables (en allemand) : The girl that I do not want to be caught with. – Lesdépendances à longue distance(interrogatives, clivées.. .) Jean veut savoir quelle fille Marie croit que Paul a vue.

2.2.3 type2 : grammaires horscontexte = grammaires algébriques Définition 10.Une grammaire de type 2, ditehorscontexteoualgébrique, est une grammaire de réécriture dont les parties gauches des règles contiennent un unique nonterminal :  X∈V N X→αavec ∗ α∈V

Exemple de grammaire horscontexte P→a Pb P→a b P→

n n Cette grammaire engendre les chaînesa b. “” “ab” “aabb” “aaabbb” ...

Utilité en TAL Les grammaires horscontexte sont adaptées pour : n n – leschaînesa bde typea 1 . . . a n b n . . . b 1 (expressions parenthésées, structures enchâssées) P→SN SV peut analyser : SN→SN ( P ) The dog the stick the fire burned beat bit the cat P SN SV SN P SN SV SN P SN VN ( () ) The dogthe stickthe fireburned beatbit the cat – leschaînesabac soit. . .soit. . .(X→soit Y soit Y) ni. . .ni. . .(X→ni Y ni Y)

Limitations – Lesgrammaires horscontexte traitent avec difficulté lerejeten fin de phrase des prépositions (en anglais) ou des particules séparables (en allemand).

Solution : dupliquer les règles pour chaque préposition ou particule – Ellesne peuvent traiter lesdépendances à longue distance, le pro. .)(interrogatives, clivées. blème étant par exemple de contraindre un accord selon un syntagme qui sort du contexte de cet accord : Jean veut savoir quelle fille Marie croit que Paul a vue. n m n m – Niles rares langues qui ont des structures de typea bc d n n – Niles chaînesa bde typea 1 . . . a n b 1 . . . b n (“respectivement”) Henri et Sophie sont repectivement indifférent et séduite par le film. Ces arguments ne sont pas vraiment décisifs pour mettre de côté ces grammaires pour le TAL, car en n m pratique, leset nesont jamais grands.

2.2.4 type1 : grammaires contextuelles Définition 11.Les grammaires de type 1, ditesgrammaires contextuellesse définissent par des règles du type :  +  α∈V ∗ α→βavec β∈V  |β| ≥ |α| (La partie gauche est non vide, et la partie droite doit contenir plus de symboles que la partie gauche)

Exemple : n n n La grammaire suivante engendre le langagea b c P→C Ba B C→B C P→a P B C

a B→a b b B→b b b C→b c c C→c c

Remarques – Cesgrammaires sontdécidables

le nombre de symboles ne peut que croître dans une dérivation.

Pour déterminer si une phrase de longueurnappartient au langage, il suffit de produire toutes les dérivations en s’arrêtant dès que le nombre de symboles produits dépassen, ce qui se fait en un temps fini. Cependant, un temps fini ne veut pas dire qu’il soit court! En pratique, cette génération exhaustive a une complexité exponentielle enn(le temps d’analyse est proportionnel à l’exponentielle du nombre de mots de la phrase à analyser). – Lesgrammaires sur lesquelles portent la majorité des recherches en TAL se situent entre le type 1 et le type 2.

2.2.5 type0 : grammaire noncontrainte Définition 12.Les grammaires de type 0 se définissent par des règles du type :  ∗ α∈V α→βavec ∗ β∈V

Remarque :Ces grammaires ne sont pas décidables.

On a pu remarquer que toutes les grammaires qui ont été écrites pour des langues naturelles pouvaient être récrites en utilisant le formalisme des règles contextuelles.

3 FormeNormale de Chomsky

Noam Chomsky a défini un type particulier de grammaires horscontexte (type 2) : les grammaires horscontexte sousforme normale. En TAL, ces grammaires sont très pratiques pour faire de l’analyse 3 syntaxique : elles permettent l’utilisation d’algorithmes efficaces pour cette tâche, de complexité O(n).

Forme Normale de Chomsky (CNF) Définition 13.Une grammaire horscontexte est sousForme Normale de Chomskysi ses règles ont l’une des deux formes :  X∈V N    X→Y ZY∈V N avec X→a Z∈V N   a∈V T Définition 14.Une grammaire horscontexte est sousCNF étenduesi ses règles peuvent également prendre les formes :   X∈V N  X→Y Z   Y∈V N X→Y avec  Z∈V N  X→a  a∈V T

Mise sous forme normale La plupart des grammaires horscontexte ne sont pas sous forme normale de Chomsky, que ce soient des grammaires du langage naturel ou de langages artificiels (langages de programmation par exemple), ce qui pourrait limiter l’intérêt des algorithmes efficaces que nous verrons plus loin. Heureusement, les grammaires de type 2 ont la propriété intéressante de pouvoir être mises sous forme normale, c’estàdire qu’il existe toujours une grammaire CNF équivalente. Définition 15.Deux grammaire sont diteséquivalentessi elles peuvent produire les mêmes chaînes de symboles terminaux. Dans le cas des grammaires horscontexte, on peut de plus facilement trouver un arbre d’analyse à partir d’un arbre créé avec la grammaire CNF équivalente. La mise sous forme normale se fait en 3 temps : 1. Suppressiondes règles de type :X→α t i β(oùt i est un terminal etαet/ouβsont non vides) (a) Créerun nonterminalT i (b) Ajouterla règleT i →t i (c) Remplacerla règleX→α t i βparX→α T i β 2. Suppressiondes règles de type :X→Y (a) Pourchaque règleZ→α X β, ajouter une règleZ→βα Y. (b) SupprimerX→Y. 3. Suppressiondes règles de type :X→αY Z (a) Créerun nouveau nonterminalX i (b) Ajouterla règleX i →Z α (c) Remplacerla règleX→αY ZparX→Y X i

La mise sous forme normale d’une grammaire augmenteconsidérablement le nombre de nonterminaux et de règles.

Exemple :

Forme initiale R 1 : P→SN SV R 2 : SN→Det N R 3 : SN→Det N SP R 4 : SP→Prep SN R 5 : SV→V R 6 : SV→V SN R 7 : SV→V SN SP L 5 : V→mange

Forme normale de Chomsky R 1 : P→SN SV R 2 : SN→Det N R 3.1 : X 1 →N SP R 3.2 : SN→Det X 1 R 4 : SP→Prep SN R 1.2 : P→SN V R 6 : SV→V SN R 7.2 : X 2 →SN SP R 7.1 : SV→V X 2 L 5 : V→mange