Damien Nouvel...Damien Nouvel (Inalco) Langages hors-contexte 3/30 Origines Historique des grammaires Hiérarchie de Chomsky (1956) Analyse du langage naturel (morphologie, syntaxe)

Langages hors-contexte

Damien Nouvel

Damien Nouvel (Inalco) Langages hors-contexte 1 / 30

Origines

Plan

1. Origines

2. Définitions

3. Dérivations

4. Simplification


Origines

Langages réguliers et grammaires

§ Les langages réguliers (ou rationnels) reconnaissent‚ Des mots issus de lexiques‚ Des formes normales (chiffres, dates, etc.)

ñ Ils sont insuffisants pour‚ Les formes récursives‚ Les structures de type tanbnu‚ La recherche de la syntaxe dans le langage naturel‚ L’analyse de programmes

ñ La machine de Turing peut faire mieux que ça !


Origines

Historique des grammaires

§ Hiérarchie de Chomsky (1956)‚ Analyse du langage naturel (morphologie, syntaxe)‚ Grammaire formelles

‚ Type 0 : grammaires générales (machine de Turing)‚ Type 1 : grammaires contextuelles (automates lin. bornés)‚ Type 2 : grammaires hors-contexte (automates à pile)‚ Type 3 : grammaires régulières (automates à états finis)

§ Langages de programmation artificiels (compilation)‚ Compilateurs mot-à-mot (assembleur)‚ Expressions mathématiques : arbres d’analyse‚ Compilateurs modernes

‚ Analyse lexicale (scanner)‚ Analyse syntaxique (parser)

ñ Utilisation des méthodes linguistiques pour la programmation


Définitions

Plan

1. Origines

2. Définitions

3. Dérivations

4. Simplification


Définitions

Arbre d’expression

§ Analyse de l’expression mathématique 12+ 3 ˚

?9

‚ Priorité des opérateurs : (12+ (3 ˚

?9))

‚ Arbre d’expression :

+

˜

1 2

˚

3?

9

ñ Chaque branche est aussi une expression valide : 12

, 3 ˚?9


Définitions

Backus-Naur Form

§ Langage de programmation Algol 1960 (J. Backus et P. Naur)§ Règles de description du langage

‚ Pour la programmation ::= "if" "(" ")" "{" "}" ::= "==" | "&&" | … ::= |

ñ Vérification de la syntaxe des programmesñ Récursivité dans les règles‚ Pour la linguistique

::= ::= | ::= "marche" | "dort" ::= "le" ::= "chien" | "chat" ::= "petit" | "gros"


Définitions

Définition des grammaires hors-contexte

ñ Reconnaissance / génération de langages§ Quadruplet G = (T,N,R, S)

‚ T : symboles terminauxñ Les mots possibles des énoncés‚ N : symboles non-terminaux

ñ Groupes de mots intéressants (GN, GV, etc.)‚ R Ă N ˆ (N Y T)˚ : règles

ñ Déterminent la composition des groupes de motsñ Notations

‚ Une règle s’écrit A Ñ α avec A P N et α P (N Y T)˚‚ Des règles A Ñ α et A Ñ β s’écrivent A Ñ α|β

‚ S P N : axiome (symbole de départ)ñ Représente l’énoncé


Définitions

Exemple

§ Expressions mathématiques‚ N = tS,Eu et T = t+, ˚,˜,?, (, ), 1, 2, 3...u‚ Règles :

S Ñ EE Ñ E + EE Ñ E ˚ EE Ñ E ˜ EE Ñ (E)E Ñ

?E

E Ñ 1|2|3 . . .§ Une dérivation possible :

S Ñ E Ñ E + E Ñ E ˜ E + E ¨ ¨ ¨ Ñ 1 ˜ 2 + 3 ˚?9


Définitions

Exercices

§ Définissez des grammaires qui reconnaissent‚ Un code postal‚ Le langage des dates au format jj/mm/aaaa‚ Une plaque d’immatriculation française‚ Un nombre entier naturel (positif)‚ Un nombre réel‚ Le langage régulier ab˚cd˚‚ Le langage tancn,n ą 0u‚ Les palindrômes‚ Une expression de parenthèses () et crochets []‚ Le langage tanbcmd,n ą 0,m ě nu


Dérivations

Plan

1. Origines

2. Définitions

3. Dérivations

4. Simplification


Dérivations

Dérivation

§ Opérations qui génèrent le langage pour une grammaire§ Un mot α P (N Y T)˚ se dérive en un mot β P (N Y T)˚ si

‚ α se décompose en α1Aα2 avec A P N‚ β se décompose en α1γα2 avec γ P (N Y T)˚‚ A Ñ γ P R (c’est une règle)

§ Exemple : E + E ˜ E Ñ E + E ˚ E ˜ E‚ α1 = E+‚ α2 = ˜E‚ A = E‚ γ = E ˚ E‚ E Ñ E ˚ E P R


Dérivations

Suite de dérivations

§ Par transitivité‚ Chaîne de dérivations α Ñ β ¨ ¨ ¨ Ñ γ = α ˚ÝÑ γ‚ Fermeture transitive, clôture (cf étoile de Kleene)‚ Si γ P (N Y T)˚ alors γ est une proto-phrase de G

§ Ordre des dérivations‚ Possibilité d’analyses pour 1 + 2 + 3

‚ Dérivation gauche : réécrit le non-terminal le plus à gaucheE Ñ E + E Ñ 1 + E Ñ 1 + E + E Ñ 1 + 2 + E Ñ 1 + 2 + 3

‚ Dérivation droite : réécrit le non-terminal le plus à droiteE Ñ E + E Ñ E + 3 Ñ E + E + 3 Ñ E + 2 + 3 Ñ 1 + 2 + 3

ñ Dérivations différentes …même résultat ?ñ Pas toujours (par ex. associativité, priorité des opérateurs)


Dérivations

Langage généré

§ Soit G une grammaire, alors le langage généré par G est

L(G) = tm P T˚|S ˚ÝÑ mu

ñ Sous-ensemble de T˚

ñ Pas nécessairement fini


Dérivations

Arbre de dérivation

§ Représentation graphique de la dérivation‚ Racine : symbole initial = S‚ Nœud : symbole non-terminal P N‚ Feuille : symbole terminal P T‚ Relation parent-enfants : dérivation (règle)

ñ Structure de l’analyse§ Dérivations (et analyses) de 1 + 2 ˚ 3

E

E

E

1

+ E

2

˚ E

3

dérivation gauche

E

E

1

+ E

E

2

˚ E

3

dérivation droiteDamien Nouvel (Inalco) Langages hors-contexte 15 / 30

Simplification

Plan

1. Origines

2. Définitions

3. Dérivations

4. Simplification


Simplification

Simplifier une grammaire

ñ Supprimer les éléments inutiles de la grammaire‚ Symboles improductifs

‚ A est improductif s’il n’y a pas de m P T˚ tel que A ˚ÝÑ m‚ Symboles inaccessibles

‚ A est inaccessible s’il n’y a pas de α et β tels que S ˚ÝÑ αAβ‚ ϵ-productions

‚ Une ϵ-production est une dérivation telle que A ˚ÝÑ ϵ‚ Production simple

‚ A Ñ B est une production simple si A P N et B P Nñ Pour toute grammaire, il existe une grammaire équivalente

sans symboles improductifs ni inaccessibles, sansϵ-productions ni productions simples


Simplification

Élimination des symboles improductifs

§ Calcul des symboles productifs‚ Soit P0 = H et i = 1‚ Soit P1 = tA P N, Dα P T˚,A Ñ α P Ru‚ Tant que Pi ‰ Pi´1

‚ Pi+1 = Pi Y tA P N, Dα P (T Y Pi)˚,A Ñ α P Ru‚ i Ð i + 1

ñ Les symboles de NzP sont improductifsñ Enlever ces symboles et les règles dans lesquels ils figurent


Simplification

Élimination des symboles inaccessibles

§ Calcul des symboles accessibles‚ Soit C0 = H, C1 = tSu et i = 1‚ Tant que Ci ‰ Ci´1

‚ Ci+1 = Ci Y tA P N, Dα, β P (N Y T)˚,X P Ci,X Ñ αAβ P Ruñ Les symboles de NzC sont inaccessiblesñ Enlever ces symboles et les règles dans lesquels ils figurent


Simplification

Élimination des ϵ-productions

§ Calcul des symboles annulables‚ Soit U0 = H et i = 1‚ Soit U1 = tA P N,A Ñ ϵ P Ru‚ Tant que Pi ‰ Pi´1

‚ Ui+1 = Ui Y tA P N, Dα P (Ui)˚,A Ñ α P Ru‚ i Ð i + 1

ñ Les symboles de U sont annulables§ Modification de la grammaire

‚ Remplacer les règles A Ñ αXβ où X P U par A Ñ αXβ|αβ(avec combinaisons possibles de X dans les règles)

‚ Supprimer toutes les règles A Ñ ϵ (sauf pour S)‚ Supprimer toutes les règles A Ñ A

ñ Grammaire équivalente à ϵ près


Simplification

Équivalences et productions simples

§ Productions simples, dérivations et classes d’équivalences‚ Production simple : toute règle A Ñ B avec B P N‚ Soit la relation ě telle que A ě B si A ˚ÝÑ B‚ Soit la relation « telle que A « B si A ě B et B ě A‚ Classes d’équivalences

‚ Si A « B, tout ce qui est dérivé de A peut l’être de B‚ Relation réflexive, symétrique et transitive‚ L’ensemble des classes est une partition de N

§ Modification de la grammaire‚ On conserve les productions non-simples‚ Pour chaque classe d’équivalence

ñ Choisir un symbole qui remplace tous les autresñ Pour chaque dérivation A ˚ÝÑ B

‚ Pour chaque B Ñ β, ajouter A Ñ β


Simplification

Exemple : simplification de grammaire

§ Grammaire1. S Ñ T|U2. U Ñ aYb|V3. V Ñ W4. X Ñ W|a5. Y Ñ Z6. Z Ñ c|ϵ

§ Étapes‚ Symboles productifs :‚ Symboles accessibles :‚ ϵ-productions :‚ Productions simples :


Simplification


§ Grammaire1. S Ñ T|U2. U Ñ aYb|V3. V Ñ W4. X Ñ W|a5. Y Ñ Z6. Z Ñ c|ϵ

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles :‚ ϵ-productions :‚ Productions simples :


Simplification


§ Grammaire1. S Ñ U2. U Ñ aYb3.4. X Ñ a5. Y Ñ Z6. Z Ñ c|ϵ

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles :‚ ϵ-productions :‚ Productions simples :


Simplification


§ Grammaire1. S Ñ U2. U Ñ aYb3.4. X Ñ a5. Y Ñ Z6. Z Ñ c|ϵ

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles : tS,U,Y,Zu ñ retirer X‚ ϵ-productions :‚ Productions simples :


Simplification


§ Grammaire1. S Ñ U2. U Ñ aYb3.4.5. Y Ñ Z6. Z Ñ c|ϵ

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles : tS,U,Y,Zu ñ retirer X‚ ϵ-productions :‚ Productions simples :


Simplification


§ Grammaire1. S Ñ U2. U Ñ aYb3.4.5. Y Ñ Z6. Z Ñ c|ϵ

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles : tS,U,Y,Zu ñ retirer X‚ ϵ-productions : tZ,Yu ñ modifier 6, 2‚ Productions simples :


Simplification


§ Grammaire1. S Ñ U2. U Ñ aYb|ab3.4.5. Y Ñ Z6. Z Ñ c

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles : tS,U,Y,Zu ñ retirer X‚ ϵ-productions : tZ,Yu ñ modifier 6, 2‚ Productions simples :


Simplification


§ Grammaire1. S Ñ U2. U Ñ aYb|ab3.4.5. Y Ñ Z6. Z Ñ c

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles : tS,U,Y,Zu ñ retirer X‚ ϵ-productions : tZ,Yu ñ modifier 6, 2‚ Productions simples : S Ñ U et Y Ñ Z ñ modifier 1, 2, 5, 6


Simplification


§ Grammaire1. S Ñ aYb|ab2.3.4.5. Y Ñ c6.

§ Étapes‚ Symboles productifs : tX,Z,Y,U,Su ñ retirer T, V et W‚ Symboles accessibles : tS,U,Y,Zu ñ retirer X‚ ϵ-productions : tZ,Yu ñ modifier 6, 2‚ Productions simples : S Ñ U et Y Ñ Z ñ modifier 1, 2, 5, 6


Simplification

Formes normales

§ Forme normale de Chomsky : toutes règles de la forme‚ A Ñ BC avec A,B,C P N‚ A Ñ a avec a P T

§ Forme normale de Greibach : toutes règles de la forme‚ A Ñ aα avec a P T, α P N˚

ñ Pour tout langage hors-contexte il existe une grammaire enforme normale de Chomsky et une grammaire en formenormale de Greibach qui le génèrent


Simplification

Mise sous forme normale de Chomsky

§ Étapes‚ Pour chaque terminal a, crééer

‚ Un symbole Za‚ Une règle Za Ñ a

‚ Pour chaque règle A Ñ α où |α| ą 1‚ Tout terminal a de α est remplacé par Za

‚ Pour chaque règle A Ñ α où |α| ą 2‚ On décompose : α = A1,A2 . . .An‚ On crée les non-terminaux Y1,Y2 . . .Yn´2‚ On remplace A Ñ α par

A Ñ A1Y1Y1 Ñ A2Y2. . .Yn´2 Ñ An´1An

‚ Suppression des ϵ-productions et productions simplesñ Forme normale de ChomskyDamien Nouvel (Inalco) Langages hors-contexte 25 / 30

Simplification

Récursivité

§ Symbole récursif : A ˚ÝÑ αAβ‚ Si α = ϵ, A est récursif à gauche‚ Si β = ϵ, A est récursif à droite‚ Si ˚ÝÑ ne comporte qu’une dérivation : récursivité directe‚ Si ˚ÝÑ comporte plusieurs dérivations : récursivité indirecte

ñ Une grammaire récursive comporte un symbole récursif§ Exemple : grammaire indirectement récursive à gauche

‚ A Ñ B‚ B Ñ CD‚ C Ñ AE

§ Suppression de la récursivité directe à gauche‚ Remplacer toute règle A Ñ Aa|b

‚ A Ñ bA1‚ A1 Ñ aA1|ϵ


Simplification

Ambiguïté et équivalence

§ Ambiguïté de grammaires‚ Grammaire : un mot est généré par deux arbres de dérivation

ñ Exemple : rattachement prépositionnel‚ S Ñ GN V GN PRP GN‚ S Ñ GN V GN‚ GN Ñ GN PRP GN

ñ Il voit le chat de sa voisine (le chat de qui ?)ñ Il voit le chat de sa fenêtre (d’où voit-il ?)

‚ Ambiguïté sémantique (plutôt que morpho-syntaxique)§ Équivalence de grammaires

‚ Génèrent le même langage‚ Donnent les même arbres d’analyse (équivalence forte)


Simplification

Autre formalismes de grammaires

§ Insuffisances des grammaires hors-contexte‚ Accords (flexions / morphologie)‚ Anaphores‚ Portée de la coordination‚ Méthodes statistiques

ñ Non traitées par les grammaires hors-contexte§ Autres formalismes

‚ PCFG (Probabilistic context-free grammar)‚ LFG (Lexical Functional Grammar)‚ HPSG (Head-driven Phrase Structure Grammar)‚ TAG (Tree Adjoining Grammar)‚ CCG (Combinatory Categorial Grammar)‚ Transition-based Parsing‚ …


Simplification

Exercices

§ Mettre sous forme normale de Chomsky‚ S Ñ AbA‚ A Ñ AaA|ca

§ Soit l’ensemble de symboles non-terminaux :N = tGN,GV,DET,PREP,NOM,ADJ,ADVu

‚ Définissez les règles d’une grammaire qui génère des phrases‚ Ajoutez des éléments terminaux et leurs règles‚ Donnez les arbres de dérivation pour les phrases suivantes

‚ le chat mange‚ le chat mange la souris‚ le chat regarde le bout de fromage

‚ Donnez quelques phrases générées par la grammaire‚ Quel problème rencontre-t-on pour les genres (m/f) ?‚ Modifiez la grammaire pour les phrases interrogatives


Simplification

TP : SWI-Prolog:- use_rendering(svgtree, [list(false)]).

% Règles non terminaless(s(X,Y)) --> gn(X), gv(Y).gn(X) --> np(X).gn(gn(X,Y)) --> det(X), nc(Y).gv(gv(X,Y)) --> v(X), gn(Y).

% Règles terminalesnp(np(jean)) --> [jean].det(det(de)) --> [de].nc(nc(philosophie)) --> [philosophie].nc(nc(politique)) --> [politique].v(v(discute)) --> [discute].

% Requêtephrase(s(Tree), [jean, discute, de, politique]).


OriginesDéfinitionsDérivationsSimplification

Documents

Damien Nouvel...Damien Nouvel (Inalco) Langages hors-contexte 3/30 Origines Historique des grammaires Hiérarchie de Chomsky (1956) Analyse du langage naturel (morphologie, syntaxe)