Upload
dangquynh
View
224
Download
0
Embed Size (px)
Citation preview
Grammaires formelles Grammaires formelles etet
programmation logiqueprogrammation logique
Motivation
Après avoir étudié Prolog nous l’avons appliqué à l’interprétation Après avoir étudié Prolog nous l’avons appliqué à l’interprétation de règles de sémantique sur des termes (Arbres de Syntaxe de règles de sémantique sur des termes (Arbres de Syntaxe Abstraite)Abstraite)
Nous allons ici nous intéresser à la façon de produire de tels arbres à Nous allons ici nous intéresser à la façon de produire de tels arbres à partir d’un ensemble de lexèmes extraits d’un texte (de programme partir d’un ensemble de lexèmes extraits d’un texte (de programme par exemple).par exemple).
L’analyseur se déduira simplement et automatiquement des règles L’analyseur se déduira simplement et automatiquement des règles de production établies pour définir sa grammairede production établies pour définir sa grammaire
Généralités
Phrase en françaisPhrase en françaisséquence finie de mots considérés comme séquence finie de mots considérés comme éléments insécables d'un ensemble finiéléments insécables d'un ensemble fini
toutes les séquences ne sont pas permisestoutes les séquences ne sont pas permisescorrectes (syntaxique)correctes (syntaxique)sensées (sémantique)sensées (sémantique)
Nous (individu) savons produire de nouvelles phrases Nous (individu) savons produire de nouvelles phrases mécanisme de génération !mécanisme de génération !
Nous savons également reconnaître de nouvelles phrases Nous savons également reconnaître de nouvelles phrases mécanisme de reconnaissance !mécanisme de reconnaissance !
Pour les langues naturelles, on n'a pas de formalisation complète de Pour les langues naturelles, on n'a pas de formalisation complète de ces mécanismes.ces mécanismes.Les "grammaires à structure de phrase" de Chomsky [Cho 59] en Les "grammaires à structure de phrase" de Chomsky [Cho 59] en sont une lointaine mais très utile approximation.sont une lointaine mais très utile approximation.
Parmi ces grammaires , nous regarderons dabord les Parmi ces grammaires , nous regarderons dabord les
grammaires hors-contexte ou grammaires non-contextuelles grammaires hors-contexte ou grammaires non-contextuelles
Règles ou productions
Ensemble de règles (productions) qui précise les suites de mots qui constituent Ensemble de règles (productions) qui précise les suites de mots qui constituent les phrases bien formées :les phrases bien formées :
L'ensemble des productions suivantesL'ensemble des productions suivantes
phrase -->phrase --> [effacer], groupe-nom.[effacer], groupe-nom.groupe_nom -->groupe_nom --> [le],[dernier],[mot], [de],groupe_nom.[le],[dernier],[mot], [de],groupe_nom.groupe_nom -->groupe_nom --> [la], [deuxième], [ligne].[la], [deuxième], [ligne].
permet de produirepermet de produire
effacereffacer le le dernier dernier mot mot de de lala deuxième deuxième ligneligne
verbeverbe articlearticle adjectifadjectif nomnom prepprep artart adjectifadjectif motmot------groupe_nominal----------------groupe_nominal----------
verbe verbe ------------------------groupe_nominal------------------------------------------------------------------groupe_nominal------------------------------------------
Grammaire
1) phrase 1) phrase -->--> verbe, groupe_nom.verbe, groupe_nom. 2) groupe_nom 2) groupe_nom -->--> article, adjectif, nom.article, adjectif, nom. 3) groupe_nom 3) groupe_nom -->--> article, adjectif, nom,article, adjectif, nom,
préposition, groupe_nom.préposition, groupe_nom. 4) verbe 4) verbe -->--> [imprimer].[imprimer]. 5) verbe 5) verbe -->--> [effacer].[effacer]. 6) article 6) article -->--> [le].[le]. 7) article 7) article -->--> [la].[la]. 8) adjectif 8) adjectif -->--> [deuxième].[deuxième]. 9) adjectif 9) adjectif -->--> [premier].[premier].10) adjectif10) adjectif -->--> [dernier].[dernier].11) nom11) nom -->--> [mot].[mot].12) nom 12) nom -->--> [ligne].[ligne].13) préposition-->13) préposition--> [de].[de].
effacer le dernier mot de la deuxième ligneeffacer le dernier mot de la deuxième ligne
Extensibilité
On peut ajouter des productionsOn peut ajouter des productions
14) article14) article -->--> [un].[un].15) article 15) article -->--> [du].[du].16) adjectif 16) adjectif -->--> [troisième].[troisième].17) nom 17) nom -->--> [caractère].[caractère].18) nom 18) nom -->--> [page].[page].
exemples de nouvelles phrases produitesexemples de nouvelles phrases produites
effacer un premier caractèreeffacer un premier caractère
effacer le premier caractère du troisième moteffacer le premier caractère du troisième mot
Monoïde libre
un ensemble (alphabet ou vocabulaire) un ensemble (alphabet ou vocabulaire)* l'ensemble des séquences finies d'éléments* l'ensemble des séquences finies d'éléments
de de plus la séquence vide plus la séquence vide
* est appelée fermeture de * est appelée fermeture de Les éléments de Les éléments de * seront appelés phrases* seront appelés phrases
++ fermeture positive fermeture positive ne contient pas la séquence videne contient pas la séquence vide
* est muni de la structure algébrique* est muni de la structure algébrique< < *, {concaténation, *, {concaténation, } U { } U {
monoïde libre engendré par monoïde libre engendré par ΣΣ**
la concaténation définie au sens habituel est associativela concaténation définie au sens habituel est associativeλλ est l'élément neutre de la concaténation est l'élément neutre de la concaténationΣΣ donne l'ensemble des constantes (générateurs) donne l'ensemble des constantes (générateurs)
Définition des grammaires Hors-contexte(non-contextuelles)
Une GNC Une GNC G est un quadruplet (V, T, P, S)G est un quadruplet (V, T, P, S)oùoù
VV est un ensemble fini de "symboles non terminaux"est un ensemble fini de "symboles non terminaux"
ou "catégories syntaxiques"ou "catégories syntaxiques"
TT est un ensemble fini (disjoint de V) de est un ensemble fini (disjoint de V) de "symboles terminaux" ou "mots""symboles terminaux" ou "mots"
PP un ensemble fini de "règles" ou "productions"un ensemble fini de "règles" ou "productions"de la forme A --> de la forme A --> avec A avec A V et V et (V (V T) T)++
S S un "symbole initial" un "symbole initial" V V
Retour sur l’exemple
dans notre exempledans notre exemple
V = {phrase, groupe_nom, verbe, article, adjectif, nom,V = {phrase, groupe_nom, verbe, article, adjectif, nom, préposition, phrase} préposition, phrase}
T = {imprimer, effacer, le, la, un, premier, deuxième,T = {imprimer, effacer, le, la, un, premier, deuxième, troisième, dernier, caractère, not, ligne, page, troisième, dernier, caractère, not, ligne, page,
de, du} de, du}
S = phraseS = phrase
Productions et Dérivations
On définit deux relations ==> et =*=> sur (V On définit deux relations ==> et =*=> sur (V T)* T)*SiSi
A --> A --> est une production de Pest une production de Petet et et des phrases de (V des phrases de (V T)* T)*
alors alors AA ==> ==>
On dit que On dit que A -->A --> ββ est appliquée à est appliquée à αΑγ αΑγ pour engendrer pour engendrer αβγαβγ
Deux phrases sont liées par la relation ==> quand la seconde Deux phrases sont liées par la relation ==> quand la seconde est obtenue à partir de la première par l'application d'une est obtenue à partir de la première par l'application d'une production production
..., ..., mm des mots de (V des mots de (V T)* tels que T)* tels que
1 1 ==>==> 22,, 2 2 ==>==> 33...... ,, m-1 m-1 ==>==> mm
on écrira alorson écrira alors 1 1 =*=>=*=> mm
=*=> est la fermeture réflexive et transitive de ==>=*=> est la fermeture réflexive et transitive de ==>
Langage non-contextuelengendré par une GNC
L = { L = { | | T* et S =*=> T* et S =*=> }}
ex : ex :
effacer le deuxième moteffacer le deuxième mot
imprimer la deuxième ligneimprimer la deuxième ligne
effacer la deuxième ligne de la troisième ligneeffacer la deuxième ligne de la troisième ligne
Arbres d ’analyse(arbres de dérivation)
verbeverbe groupe-nomgroupe-nom
artart adjadj nomnom prepprep groupe-nomgroupe-nom
effacereffacer lele dernierdernier motmot dede artart adjadj nomnom
lala deuxièmedeuxième ligneligne
Le sommet s'appelle "racine"Le sommet s'appelle "racine"il est marqué par le symbole initial de Gil est marqué par le symbole initial de GLes feuilles sont marquées par les symboles terminaux Les feuilles sont marquées par les symboles terminaux les noeuds intermédiaires correspondent aux productions.les noeuds intermédiaires correspondent aux productions.
phrasephrase
Arbre de dérivation
L'arbre de dérivation représente donc la trace de la L'arbre de dérivation représente donc la trace de la construction d'une expression bien forméeconstruction d'une expression bien formée
sisi AA est dans l'arbreest dans l'arbre
XX11 XpXp|| ||
A --> XA --> X11,..., Xp,..., Xp est une production utilisée dans la est une production utilisée dans la construction de la phraseconstruction de la phrase
Une phrase est dite «ambiguë» si on peut lui associer Une phrase est dite «ambiguë» si on peut lui associer plusieurs arbres syntaxiques.plusieurs arbres syntaxiques.(par extension, on dit dans ce cas que la grammaire est ambigüe) (par extension, on dit dans ce cas que la grammaire est ambigüe)
Expression parenthèsée (Terme)
Un arbre peut s'écrire sous forme d'une expressionUn arbre peut s'écrire sous forme d'une expressionparenthèséeparenthèsée
ex :ex :ph( v(effacer), gn(art(le), adj(dernier), n(mot),ph( v(effacer), gn(art(le), adj(dernier), n(mot),
prep(de), gn( art(la), adj(deuxième), n(ligne)))).prep(de), gn( art(la), adj(deuxième), n(ligne)))).
avec ici ph pour phrase, gn pour groupe-nom,n pour nom,...avec ici ph pour phrase, gn pour groupe-nom,n pour nom,...
analogieanalogiess p, q, rp, q, r
s est bien formée si p, q et r sont bien forméess est bien formée si p, q et r sont bien forméesgram-gram-mairemaire
s :- p, q, rs :- p, q, r s est vrai si p, q, et r sont vrais s est vrai si p, q, et r sont vrais
attention comme dans Prolog mais à laattention comme dans Prolog mais à lades clauses de Horn : l'ordre des symbolesdes clauses de Horn : l'ordre des symbolesdu corps comptedu corps compte
GNC et clauses de Horn
clausesclauses
Exemple Prolog
Une phrase étant une suite de "mots", on va utiliserUne phrase étant une suite de "mots", on va utiliserdes listes de "mots" pour la représenterdes listes de "mots" pour la représenter
1) phrase ([V|GN]) :- 1) phrase ([V|GN]) :- verbe([V]), groupe_nom(GN).verbe([V]), groupe_nom(GN).
2) groupe_nom([Art, Adj, N]) :- 2) groupe_nom([Art, Adj, N]) :- article ([Art]), adjectif ([Adj]), nom([N]).article ([Art]), adjectif ([Adj]), nom([N]).
3) groupe_nom ([Art, Adj, N, Pr|GN]):-3) groupe_nom ([Art, Adj, N, Pr|GN]):-article([Art]), adjectif([Adj]), nom([N]),article([Art]), adjectif([Adj]), nom([N]),preposition([Pr]), groupe_nom(GN).preposition([Pr]), groupe_nom(GN).
Déclaration des terminaux
4) verbe([imprimer]).4) verbe([imprimer]).5) verbe([effacer]).5) verbe([effacer]).6) article([le]).6) article([le]).7) article([la]).7) article([la]).8) adjectif([deuxieme]).8) adjectif([deuxieme]).9) adjectif([premier]).9) adjectif([premier]).10) adjectif([dernier]).10) adjectif([dernier]).11) nom([mot]).11) nom([mot]).12) nom([ligne]).12) nom([ligne]).13 preposition([de]).13 preposition([de]).
Construction de l ’Arbre de Syntaxe Abstraite
Objectif:
utiliser cette notation pour spécifier puis générer les termes dont nous avons besoin ensuite pour l ’interprétation prolog des règles de sémantique structurelle vues dans le cours précédent.
DCG et Construction de l'arbre syntaxique
On réécrit la grammaire DCG avec un argumentOn réécrit la grammaire DCG avec un argument
phrase(ph(V,Gn))phrase(ph(V,Gn)) --> verbe(V), groupe_nom(Gn). --> verbe(V), groupe_nom(Gn).groupe_nom(gn(Art, Adj,N))--> groupe_nom(gn(Art, Adj,N))-->
article(Art),adjectif(Adj)),nom(N).article(Art),adjectif(Adj)),nom(N).groupe_nom(gn(Art, Adj, N, Pr, gn(Gn)))-->groupe_nom(gn(Art, Adj, N, Pr, gn(Gn)))-->
article(Art),adjectif(Adj),nom(N), article(Art),adjectif(Adj),nom(N), preposition(P), groupe_nom(Gn).preposition(P), groupe_nom(Gn).
verbe(v(effacer))verbe(v(effacer)) -->--> [effacer].[effacer].verbe(v(imprimer))verbe(v(imprimer)) -->--> [imprimer].[imprimer].article(art(le)) article(art(le)) --> --> [le].[le].adjectif(adj(dernier))adjectif(adj(dernier)) -->--> [dernier].[dernier].......nom(n(mot))nom(n(mot)) -->--> [mot].[mot].preposition(prep(de)) preposition(prep(de)) --> --> [de].[de].
exemplela phrasela phrase
[effacer, le, dernier, mot][effacer, le, dernier, mot]peut se construire par les productionspeut se construire par les productionsphrase(ph(v(effacer), Gn))phrase(ph(v(effacer), Gn)) --> --> verbe(V),verbe(V),
groupe_nom(Gn)groupe_nom(Gn)
puis enpuis enphrase(ph(v(effacer), gn(Art, Adj, N))phrase(ph(v(effacer), gn(Art, Adj, N)) -->-->
verbe(v(effacer)),verbe(v(effacer)),article(Art),article(Art),adjectif(Adj),adjectif(Adj),
nom(N).nom(N).etetphrase(ph(v(effacer), gn(art(le),adj(dernier),n(mot)))phrase(ph(v(effacer), gn(art(le),adj(dernier),n(mot))) -->-->
verbe(v(effacer)),verbe(v(effacer)),
article(art(le)),article(art(le)),adjectif(adj(dernier)),adjectif(adj(dernier)),nom(n(mot)).nom(n(mot)).
ainsi jusqu'à produire l'arbre syntaxique (le terme)ainsi jusqu'à produire l'arbre syntaxique (le terme)ph(v(effacer), gn(art(le), adj(dernier), n(mot))))ph(v(effacer), gn(art(le), adj(dernier), n(mot))))
Limites des GNC
ne permettent pas de tenir compte du contextene permettent pas de tenir compte du contexte
1) effacer la dernier ligne1) effacer la dernier ligne2) effacer la deuxième ligne de la deuxième ligne2) effacer la deuxième ligne de la deuxième ligne syntaxiquement incorrecte (1), et/ou syntaxiquement incorrecte (1), et/ou sémantiquement absurde (2) sémantiquement absurde (2)
la solution de certains de ces problèmes dans le cadre la solution de certains de ces problèmes dans le cadre GNC demanderait de nombreuses autres productions. GNC demanderait de nombreuses autres productions.
Grammaires DCG
Definite Clause GrammarsDefinite Clause Grammars
afin de régler le problème de l'accord des genres (féminin ouafin de régler le problème de l'accord des genres (féminin oumasculin) (contexte syntaxique) on propose de remplacer parmasculin) (contexte syntaxique) on propose de remplacer parexempleexemple
groupe_nom --> article, adjectif, nom, groupe_nom --> article, adjectif, nom, preposition, groupe_nom. preposition, groupe_nom.
parpargroupe_nom --> article(C), adjectif(C), nom(C), groupe_nom --> article(C), adjectif(C), nom(C),
preposition, groupe_nom. preposition, groupe_nom.
dans laquelle un "argument contextuel" C a été introduitdans laquelle un "argument contextuel" C a été introduit
Exemple DCG : suite
Ici cet argument pourra prendre les valeurs "masculin"Ici cet argument pourra prendre les valeurs "masculin"ou "féminin"ou "féminin"
Les autres règles s'écrivantLes autres règles s'écrivant
verbeverbe -->--> [imprimer][imprimer]verbeverbe --> --> [effacer][effacer]article(masculin)article(masculin) --> --> [le][le]article(féminin) article(féminin) --> --> [la][la]adjectif(masculin)adjectif(masculin) --> --> [dernier][dernier]nom(féminin) nom(féminin) --> --> [ligne][ligne]
effacer la dernière ligne ne peut être produite !effacer la dernière ligne ne peut être produite !
Représentation en Clauses de Horn
groupe_nom ([Art, Adj, N]) :- article(C, [Art]),groupe_nom ([Art, Adj, N]) :- article(C, [Art]), adjectif(C, [Adj]), adjectif(C, [Adj]),
nom(C, [Nom]). nom(C, [Nom]).
......article(masculin, [le]).article(masculin, [le]).article(feminin, [la]).article(feminin, [la]).......
production des grammaires DCGproduction des grammaires DCG
clauses de Horn avec prédicats d'arité quelconqueclauses de Horn avec prédicats d'arité quelconque
Contextes sémantiques et DCG
On veut éliminer les phrases du genreOn veut éliminer les phrases du genreeffacer la dernière ligne de la dernière ligneeffacer la dernière ligne de la dernière ligne
Le corps des règles pourra contenir des prédicats ou procédures(entre accolades) Le corps des règles pourra contenir des prédicats ou procédures(entre accolades) représentant des conditions d'emploi des productionsreprésentant des conditions d'emploi des productionsex :ex :1" 1" phrasephrase --> verbe, groupe_nom(O).--> verbe, groupe_nom(O).2"2" groupe_nom(Ygroupe_nom(Y11)) -->--> article(C), adjectif(C),article(C), adjectif(C),
nom(C, Znom(C, Z11), {Y), {Y11 < Z < Z11}.}.3"3" groupe_nom(Ygroupe_nom(Y22)) -->--> article(C), adjectif(C)article(C), adjectif(C)
nom(C, Znom(C, Z22), {Y), {Y22 < Z < Z22},},preposition, groupe_nom(Zpreposition, groupe_nom(Z22).).
......12"12" nom(masc, 1)nom(masc, 1) -->--> [caractère][caractère]13"13" nom(masc, 2) nom(masc, 2) -->--> [mot][mot]14"14" nom(fem, 3)nom(fem, 3) -->--> [ligne][ligne]15"15" nom(fem, 4)nom(fem, 4) -->--> [page][page]
Trace de dérivation
12",..., 15" introduisent une hiérarchie sémantique12",..., 15" introduisent une hiérarchie sémantiquecaractèrecaractère notnot ligne ligne page page
(l'idée vient de ce que la préposition ...de... implique l'inclusion)(l'idée vient de ce que la préposition ...de... implique l'inclusion)
{Y{Y11 < Z < Z11} dans 2" et 3" élimine les phrases absurdes} dans 2" et 3" élimine les phrases absurdesex : ex : on suppose que l'on en est àon suppose que l'on en est à groupe_nom(Y groupe_nom(Y22)--> )--> [la, dernière], nom(fem, Z[la, dernière], nom(fem, Z22), {Y), {Y22 < Z < Z22},},
[de], groupe_nom(Z[de], groupe_nom(Z22).).
avecavecnom(fem, 3)nom(fem, 3)--> [ligne] --> [ligne] on passe àon passe àgroupe_nom(Ygroupe_nom(Y22)) --> --> [la, dernière, ligne], {Y[la, dernière, ligne], {Y22 < 3}, < 3},
[de], groupe_nom(3)[de], groupe_nom(3)
puis avec la règle 2" correctement instanciéepuis avec la règle 2" correctement instanciéegroupe_nom(Ygroupe_nom(Y22) ) --> --> [la, dernière, ligne], {Y[la, dernière, ligne], {Y22 < 3}, < 3},
[de, la, dernière], nom(fem, Z[de, la, dernière], nom(fem, Z11), {3 < Z), {3 < Z11}}
seuleseule
nom(fem, 4)nom(fem, 4) --> --> [page] [page] permet depermet de satisfaire 3 < Zsatisfaire 3 < Z11
groupe_nom(Ygroupe_nom(Y22)) --> --> [la, dernière, ligne], {Y[la, dernière, ligne], {Y2 2 < 3},< 3},[de, la, dernière, page].[de, la, dernière, page].
Grammaire DCGet programmation logique
groupe_nom(Ygroupe_nom(Y22) -->) --> article(C), adjectif(C),article(C), adjectif(C), nom(C, Z nom(C, Z22), {Y), {Y2 2 < Z< Z22},}, preposition, groupe_nom(Z preposition, groupe_nom(Z22))
est traduit enest traduit en
groupe_nom(Ygroupe_nom(Y22, [art, Adj, N, Pr|GN]) :-, [art, Adj, N, Pr|GN]) :- article(C, [Art]), adjectif(C, [Ad]), article(C, [Art]), adjectif(C, [Ad]), nom(C, Z nom(C, Z22, [N]), Y, [N]), Y22 < Z < Z22,, preposition(Pr), groupe_nom(Z preposition(Pr), groupe_nom(Z22, GN)., GN).
dans laquelle les catégories syntaxiques (comme dans laquelle les catégories syntaxiques (comme nom(C, Znom(C, Z22, [N]), [N])))ou les procédures ou les procédures {Y{Y22 < Z < Z22}} sont interprétées comme des prédicats sont interprétées comme des prédicats
logiqueslogiques..
Construction de l'arbre de syntaxe abstraiteOn réécrit la grammaire DCG avec les argumentsOn réécrit la grammaire DCG avec les arguments
phrase(ph(V, Gn))phrase(ph(V, Gn)) --> verbe(V), groupe-nom(O,Gn) --> verbe(V), groupe-nom(O,Gn)
groupe_nom(Ygroupe_nom(Y11, gn(Art, Adj,N))--> , gn(Art, Adj,N))--> article (C, Art),article (C, Art),adjectif (C, Adj)),adjectif (C, Adj)),
nom(C, Znom(C, Z11, N), {Y, N), {Y11<Z<Z11}.}.
groupe_nom(Ygroupe_nom(Y22, gn (Art, Adj, N, Pr, gn, (Gn)))-->, gn (Art, Adj, N, Pr, gn, (Gn)))--> article(C, Art),article(C, Art),
adjectif(C, Adj),adjectif(C, Adj),nom(C, Znom(C, Z22, N), {Y, N), {Y22<Z<Z22}}
preposition(P),preposition(P),groupe_nom(Zgroupe_nom(Z22, Gn)., Gn).
verbe (v(effacer))verbe (v(effacer)) -->--> [effacer].[effacer].
verbe (v(imprimer))verbe (v(imprimer)) -->--> [imprimer].[imprimer].article(masc, art(le))article(masc, art(le)) -->--> [le].[le].......nom(fem, 4, n(page))nom(fem, 4, n(page)) -->--> [page].[page].
preposition(prep(de))preposition(prep(de)) -->--> [de].[de].
Eléments de transformations automatique en Prolog
En partant deEn partant dephrase --> verbe, groupe nomphrase --> verbe, groupe nom
nous avions écrit nous avions écrit phrase([V|GN]) :- verbe([V]), groupe_nom(GN).phrase([V|GN]) :- verbe([V]), groupe_nom(GN).
Cela suppose la reconnaissance du fait que 'verbe' Cela suppose la reconnaissance du fait que 'verbe' consomme un mot de la phrase.consomme un mot de la phrase.
Représentation en D_liste
Un traitement automatique pourrait plus simplementUn traitement automatique pourrait plus simplementproduireproduire
Phrase(Ph) :- Phrase(Ph) :- conc(Début, Reste, Ph),conc(Début, Reste, Ph),
verbe(Début),verbe(Début),groupe_nom(Reste).groupe_nom(Reste).
Ou plus efficacementOu plus efficacementPhrase(Ph, Fin) :- Phrase(Ph, Fin) :- verbe(Ph, Suite),verbe(Ph, Suite),
groupe_nom(suite, Fin)groupe_nom(suite, Fin)
avec par exempleavec par exempleet et verbe --> [effacer] verbe --> [effacer] transformé en transformé en
verbe([effacer|S], S).verbe([effacer|S], S).
et le butet le but ?- phrase([effacer, le, dernier, mot], [ ]).?- phrase([effacer, le, dernier, mot], [ ]).