4. Communication dans les Systèmes Multi-Agents
4.1 Interprétation du langage

4.1.3 L'analyse syntaxique

Les règles de grammaire

La syntaxe des phrases qui nous intéressent obéit à des règles de réécriture données sous la forme :
catégorie grammaticale suite non vide de catégories grammaticales et de mots de la langue.

Ce qui se trouve à gauche (resp. à droite) de la flèche s'appelle la partie gauche (resp. la partie droite) de la règle. Les lecteurs familiers avec la théorie des langages auront reconnu une grammaire algébrique sans production vide ou -free context-free grammar (les autres lecteurs n'ont pas besoin, pour le présent cours, de se soucier des propriétés formelles de ces grammaires).

Exemple:

  (i)   Phrase -> Nom-Propre Verbe-3ème-personne-singulier
  (ii)  Nom-Propre -> Théophraste
  (iii) Nom-Propre -> Célimène
  (iv) Verbe-3ème-personne-singulier -> dort
  (v)  Verbe-3ème-personne-singulier -> sourit

est une grammaire. Les catégories grammaticales y apparaissent en caractères droits, les mots de la langue, en caractères italiques.

Une suite de mots de la langue fait partie d'une catégorie grammaticale C s'il existe une séquence de règles de réécriture telle qu'en partant de C et en substituant la partie gauche d'une règle par sa partie droite, on arrive à .

Exemple : Théophraste sourit fait partie de la catégorie grammaticale Phrase car la séquence (i) (ii) (v) [ou la séquence (i) (v) (ii)] a les propriétés souhaitées. En effet, partant de Phrase, (i) lui substitue Nom-Propre Verbe-3ème-personne-singulier, dans laquelle (ii) substitue Nom-Propre par Théophraste, ce qui donne Théophraste Verbe-3ème-personne-singulier. Enfin, dans cette suite, (v) substitue Verbe-3ème-personne-singulier par sourit ce qui donne la suite annoncée : Théophraste sourit.

Question: Donner toutes les suites de mots de la langue qui font partie des catégories grammaticales Nom-Propre et Phrase, en appliquant la grammaire de l'exemple ci-dessus.

Cliquer ici pour voir la réponse.

Pour simplifier les notations, on se permettra de regrouper en une seule règle toutes les règles ayant la même partie gauche, les différentes parties droites étant séparées par une barre verticale. Dans cette notation simplifiée, la grammaire de l'exemple s'écrit :

Phrase -> Nom-Propre Verbe-3ème-personne-singulier
Nom-Propre -> Théophraste | Célimène
Verbe-3ème-personne-singulier -> dort | sourit

Question: Modifier la grammaire de l'exemple ci-dessus pour que les suites de mots de la langue le garçon dort, la fille sourit fassent également partie de la catégorie grammaticale phrase.

Cliquer ici pour voir la réponse.

Calcul des premiers

Le problème qui va nous concerner ici est, d'une certaine façon, l'opposé de celui que nous venons de voir : Il ne s'agit pas d'engendrer des suites de mots, mais une suite de mots étant donnée, de trouver la séquence de règles, si elle existe, qui permet de justifier que cette suite fait partie de la catégorie grammaticale Phrase.

De très nombreux algorithmes permettent de résoudre ce problème (voir ouvrages de théorie des langages et de compilation cités en fin de section) ; au paragraphe suivant, nous aurons besoin d'une analyse dite descendante, et nous nous bornons ici à décrire la méthode dont nous nous servirons. Elle a besoin de savoir par quels mots commence chaque catégorie grammaticale C, mots que l'on appelle les premiers de la catégorie C et qu'on regroupe dans un ensemble PREMIER(C).

Le calcul de ces ensembles PREMIER se fait par l'algorithme suivant :

        initialement, tous les ensembles PREMIER sont vides.
        pour tout mot de la langue m faire PREMIER(m) <- {m} fait
        tant que la valeur d'une fonction PREMIER est modifiée faire
           pour toute règle C -> A1…An faire
            ajouter PREMIER(Ai) à PREMIER(C)
           fait
         fait

Exemple : La grammaire envisagée ci-dessus est composée des règles :

Phrase -> Groupe-Nominal Verbe-3ème-personne-singulier
Groupe-Nominal -> Nom-Propre | le Nom-Commun-Masculin | la Nom-Commun-Féminin
Nom-Propre -> Théophraste | Célimène
Nom-Commun-Masculin -> garçon
Nom-Commun-Féminin -> fille
Verbe-3ème-personne-singulier -> dort | sourit

La première itération donne la valeur {le} à PREMIER(le), et en fait autant pour chaque mot, c'est-à-dire la, Théophraste, Célimène, garçon, fille, dort, sourit.

La règle Phrase -> Groupe-Nominal Verbe-3ème-personne-singulier ajoute l'ensemble PREMIER(Groupe-Nominal) à PREMIER(Phrase), mais cet ensemble étant inconnu, il ne se passe rien.

La règle Groupe-Nominal -> Nom-Propre n'a pas plus d'effet, puisque PREMIER(Nom Propre) est inconnu.

La règle Groupe-Nominal -> le Nom-Commun-Masculin ajoute PREMIER(le), c'est-à-dire {le} à PREMIER(Groupe-Nominal).

De même, Groupe-Nominal -> la Nom-Commun-Féminin ajoute PREMIER(la) = {la} à PREMIER(Groupe-Nominal) qui contient désormais {le, la}

Nom-Propre -> Théophraste ajoute {Théophraste} à PREMIER(Nom-Propre).

De même, Nom-Propre -> Célimène ajoute {Célimène} à PREMIER(Nom-Propre) qui vaut maintenant {Théophraste, Célimène}.

De la même façon, on voit que PREMIER(Nom-Commun-Masculin) = {garçon}, PREMIER(Nom-Commun-Féminin) = {fille}, PREMIER(Verbe-3ème-personne-singulier) = {dort, sourit}.

On recommence alors le parcours de toutes les règles : la règle Phrase -> Groupe-Nominal Verbe-3ème-personne-singulier ajoute l'ensemble PREMIER(Groupe-Nominal) à PREMIER(Phrase), donc PREMIER(Phrase) vaut désormais {le, la}.

La règle Groupe-Nominal -> Nom-Propre ajoute PREMIER(Nom Propre) à PREMIER(Groupe-Nominal) qui prend la valeur {le, la, Théophraste, Célimène}.

Les autres règles ne modifient pas les ensembles déjà construits.

On recommence une nouvelle fois le parcours de toutes les règles : la règle Phrase -> Groupe-Nominal Verbe-3ème-personne-singulier ajoute l'ensemble PREMIER(Groupe-Nominal) à PREMIER(Phrase), donc PREMIER(Phrase) = {le, la, Théophraste, Célimène}.

Les autres règles ne modifient pas les ensembles déjà construits.

Plus aucun ensemble n'évoluant, l'exécution de l'algorithme est terminée.

Question: On rajoute les règles :

Groupe Nominal -> Pronom-Personnel-3ème-personne-singulier
Pronom-Personnel-3ème-personne-singulier -> il | elle
Quelles sont les modifications des PREMIER ?

Cliquer ici pour voir la réponse.

Fabrication de la table d'analyse

La méthode d'analyse que nous présentons ici s'appuie sur une table, méthode assez proche de celle que nous avons vue pour la reconnaissance des mots : les lignes de la table sont les catégories grammaticales C, et les colonnes, les mots de la langue M. L'intersection de la ligne C et de la colonne M contient le numéro d'une règle de réécriture si le mot M fait partie de PREMIER(C) ; elle est vide sinon.

Commençons par l'exemple extrêmement simple de la grammaire envisagée ci-dessus, dont nous numérotons les règles (et pour cela, nous abandonnons momentanément le regroupement des règles ayant même partie gauche) :

Exemple :
  (1)   Phrase -> Groupe-Nominal Verbe-3ème-personne-singulier
  (2)   Groupe-Nominal -> Nom-Propre
  (3)   Groupe-Nominal -> le Nom-Commun-Masculin
  (4)   Groupe-Nominal -> la Nom-Commun-Féminin
  (5)   Nom-Propre -> Théophraste
  (6)   Nom-Propre -> Célimène
  (7)   Nom-Commun-Masculin -> garçon
  (8)   Nom-Commun-Féminin -> fille
  (9)   Verbe-3ème-personne-singulier -> dort
  (10) Verbe-3ème-personne-singulier -> sourit

Les ensembles PREMIER construits dans l'exemple précédent permettent d'obtenir la table :

Les choses ne se passent pas toujours aussi facilement : connaissant la catégorie et le mot de la langue, il n'est pas toujours possible de déterminer de façon unique la règle à appliquer ; nous verrons dans un moment un remède possible dans ce cas, mais il ne réussit pas toujours, et il faut parfois recourir à des méthodes d'analyse moins rapides (voir cours de théorie des langages et de compilation).

De plus, les règles de grammaire portent généralement sur la nature des mots, et non sur les mots eux-mêmes ; le niveau précédent (section 4.1.2), en reconnaissant les mots, nous a fourni leur nature grammaticale ; on construira des analyseurs beaucoup plus puissants en portant en colonne les natures de mots au lieu des mots eux-mêmes.

Supposons par exemple qu'aient été reconnues 11 natures grammaticales : les noms propres (notés np), les noms communs masculins et féminins (notés ncm et ncf), les articles indéfinis et définis masculins et féminins (notés aim, adm, aif, et adf), les adjectifs antéposés masculins et féminins (notés aam et aaf), les verbes intransitifs et transitifs conjugués à la troisième personne du singulier (notés vi3 et vt3).

Considérons la grammaire formée des règles :
  (1)   Phrase -> Groupe-Nominal Groupe-Verbal
  (2)   Groupe-Nominal -> np
  (3)   Groupe-Nominal -> Déterminant-Masculin Groupe-Masculin
  (4)   Groupe-Nominal -> Déterminant-Féminin Groupe-Féminin
  (5)   Déterminant-Masculin -> aim
  (6)   Déterminant-Masculin -> adm
  (7)   Déterminant-Féminin -> aif
  (8)   Déterminant-Féminin -> adf
  (9)   Groupe-Masculin -> aam Groupe-Masculin
  (10) Groupe-Masculin -> ncm
  (11) Groupe-Féminin -> aaf Groupe-Féminin
  (12) Groupe-Féminin -> ncf
  (13) Groupe Verbal -> vi3
  (14) Groupe Verbal -> vt3 Groupe-Nominal

Le calcul des PREMIER permet de construire la table suivante :

Analyse proprement dite

Une fois la table construite, l'analyse syntaxique consiste à appliquer l'algorithme suivant :

initialement, 
        PRÉDICTION contient Phrase,
        RESTE contient l'énoncé à analyser,
        POSSIBLE est à vrai ;

        tant que PRÉDICTION et RESTE ne sont pas vides et POSSIBLE 
                est vrai faire
                M <- le premier symbole de RESTE
                P <- le premier symbole de PRÉDICTION

        si P est une catégorie C,
                si l'intersection de la ligne C et de la colonne M de la table 
                        contient un numéro i, et si C -> A1…An est la règle n°i, 
                        remplacer C par A1…An en tête de
                        PRÉDICTION
                sinon {la case ligne C colonne M est vide} mettre POSSIBLE à faux
                finsi

        sinon {P est un mot ou une nature de mot}
                si P = M, on ôte M de RESTE, et P de PRÉDICTION
                sinon {P <> M} mettre POSSIBLE à faux
                finsi
        finsi
        fait

        si POSSIBLE est vrai et PRÉDICTION et RESTE sont tous deux vides, 
        analyse réussie
        sinon échec de l'analyse
        finsi

Exemple:
appliquons cet algorithme à la table ci-dessus pour analyser : la jolie petite fille lit un gros livre ; on suppose que le niveau de reconnaissance des mots a reconnu la nature de chacun d'eux, et a fourni la séquence : adf aaf aaf ncf vt3 aim aam ncm.

Au départ, PRÉDICTION = Phrase, RESTE = adf aaf aaf ncf vt3 aim aam ncm, POSSIBLE = vrai ;

M = adf, P = Phrase, qui est une catégorie ; l'intersection de la ligne Phrase et de la colonne adf donne 1 ; la règle n°1 Phrase -> Groupe-Nominal Groupe-Verbal remplace Phrase dans PRÉDICTION par Groupe-Nominal Groupe-Verbal, RESTE et POSSIBLE ne sont pas modifiés ;

M = adf, P = Groupe-Nominal, une catégorie ; l'intersection de la ligne Groupe-Nominal et de la colonne adf donne 4 ; la règle n°4 modifie PRÉDICTION qui devient Déterminant-Féminin Groupe-Féminin Groupe-Verbal, RESTE et POSSIBLE ne sont pas modifiés ;

M = adf, P = Déterminant-Féminin, catégorie ; l'intersection de la ligne Déterminant-Féminin et de la colonne adf donne 8 ; la règle n°8 modifie PRÉDICTION qui devient adf Groupe-Féminin Groupe-Verbal, RESTE et POSSIBLE ne sont pas modifiés ;

M = adf, P = adf ; ce n'est pas une catégorie ; on a P = M ; on les supprime de ces deux listes : PRÉDICTION devient Groupe-Féminin Groupe-Verbal, RESTE = aaf aaf ncf vt3 aim aam ncm et POSSIBLE n'est pas modifié ;

M = aaf, P = Groupe-Féminin, catégorie ; l'intersection de la ligne Groupe-Féminin et de la colonne aaf donne 11 ; la règle n°11 modifie PRÉDICTION qui devient aaf Groupe-Féminin Groupe-Verbal, RESTE et POSSIBLE ne sont pas modifiés ;

M = aaf, P = aaf ; P = M ; on les supprime : PRÉDICTION devient Groupe-Féminin Groupe-Verbal, RESTE= aaf ncf vt3 aim aam ncm et POSSIBLE n'est pas modifié ;

La suite de l'analyse se déroule ainsi : de nouveau règle 11, PRÉDICTION redevient aaf Groupe-Féminin Groupe-Verbal, puis Groupe-Féminin Groupe-Verbal, après effacement de aaf ; RESTE = ncf vt3 aim aam ncm. Puis règle 12, PRÉDICTION devient ncf Groupe-Verbal, puis Groupe-Verbal, après effacement de ncf ; RESTE = vt3 aim aam ncm.

Ensuite, règle 14, PRÉDICTION devient vt3 Groupe-Nominal, puis Groupe-Nominal, après effacement de vt3 ; RESTE = aim aam ncm. Règle 3, PRÉDICTION devient Déterminant-Masculin Groupe-Masculin, puis règle 5, PRÉDICTION devient aim Groupe-Masculin, puis Groupe-Masculin après effacement de aim ; RESTE = aam ncm. Règle 9, PRÉDICTION devient aam Groupe-Masculin, puis Groupe-Masculin après effacement de aam ; RESTE = ncm. Enfin, règle 10, PRÉDICTION devient ncm, puis vide après effacement de ncm, qui vide également RESTE. L'analyse se termine donc avec succès.

Remarquons que si le niveau de reconnaissance des mots a fourni plusieurs solutions (dans l'exemple précédent, lit peut être un nom commun masculin), chacune d'elles devrait être essayée (donc si n mots de la phrase sont de nature ambiguë, il faudrait faire jusqu'à 2n essais) ; des améliorations faciles permettent de diminuer ce nombre.

Question: Analyser Célimène sourit avec la table donnée plus haut, puis avec la présente table en supposant qu'on a reconnu qu'il s'agissait d'un nom propre suivi d'un verbe intransitif conjugué à la troisième personne.

Lorsque la construction de la table n'aboutit pas

La méthode ci-dessus suppose que pour chaque catégorie grammaticale, la donnée d'un seul élément à analyser suffit pour orienter vers la "bonne" règle, celle qui permettra de poursuivre l'analyse. De nombreuses raisons font que ce n'est pas toujours possible ; il suffit parfois de modifier légèrement la grammaire, sans altérer le fragment du langage analysé, car une infinité de grammaires permettent d'engendrer un même langage. Parfois, ceci n'est pas possible, ou l'est au prix d'autres inconvénients. Nous illustrons ici un autre procédé.

Dans la section suivante, nous aurons besoin d'une grammaire qui utilise les règles :

Groupe-nom-masculin -> ncm | Groupe-post-masculin
Groupe-post-masculin -> ncm Qualificatif-post-masculin

Manifestement, la présence d'un nom commun masculin (ncm) ne permet pas d'orienter l'analyse de Groupe-nom-masculin, puisque les deux possibilités de l'alternative commencent par le même symbole. La solution sera ici de considérer non seulement le mot suivant, mais les deux mots suivants : on dit que l'analyse est LL(2) au lieu d'être LL(1).

Si cela ne suffit pas, on peut augmenter la dose, et appliquer la méthode LL(k) qui consiste à examiner les k caractères suivants pour déterminer la règle à appliquer. Certains langages n'ont la propriété LL(k) pour aucune valeur de k, et il faut alors recourir à des méthodes de nature différente (cf. Biblio. pour des ouvrages de théorie des langages).

Lorsqu'il existe un k fini permettant l'utilisation de la méthode présentée ici, il faut en théorie avoir autant de colonnes que de combinaisons de k mots ; on peut facilement l'éviter en utilisant un symbole "joker" (noté ?), chaque fois que le choix de la règle ne dépend que des autres symboles. D'autre part, il faut initialiser RESTE par l'énoncé à analyser suivi de (k-1) symboles #, afin que la séquence des k symboles suivants soit toujours définie.

Exemple : La grammaire que nous utiliserons à la section suivante est :
  (1)   Phrase -> Groupe-nominal Groupe-verbal
  (2)   Groupe-nominal ® np
  (3)   Groupe-nominal -> Groupe-nominal-indéfini
  (4)   Groupe-nominal -> Groupe-nominal-défini
  (5)   Groupe-nominal-indéfini -> un Groupe-masculin
  (6)   Groupe-nominal-indéfini -> une Groupe-féminin
  (7)   Groupe-masculin -> Groupe-anté-masculin
  (8)   Groupe-masculin -> Groupe-nom-masculin
  (9)   Groupe-anté-masculin -> aam Groupe-masculin
  (10) Groupe-nom-masculin -> ncm
  (11) Groupe-nom-masculin -> Groupe-post-masculin
  (12) Groupe-post-masculin -> ncm Qualificatif-post-masculin
  (13) Qualificatif-post-masculin -> apm
  (14) Qualificatif-post-masculin -> Complément-post-masculin
  (15) Qualificatif-post-masculin -> Complément-d'attribut
  (16) Complément-post-masculin -> ppm prep Groupe-nominal
  (17) Complément-d'attribut -> de nda val
  (18) Groupe-féminin -> Groupe-anté-féminin
  (19) Groupe-féminin -> Groupe-nom-féminin
  (20) Groupe-anté-féminin -> aaf Groupe-féminin
  (21) Groupe-nom-féminin -> ncf
  (22) Groupe-nom-féminin -> Groupe-post-féminin
  (23) Groupe-post-féminin -> ncf Qualificatif-post-féminin
  (24) Qualificatif-post-féminin -> apf
  (25) Qualificatif-post-féminin -> Complément-post-féminin
  (26) Qualificatif-post-féminin -> Complément-d'attribut
  (27) Complément-post-féminin -> ppf prep Groupe-nominal
  (28) Groupe-nominal-défini -> le Groupe-masculin
  (29) Groupe-nominal-défini -> la Groupe-féminin
  (30) Groupe-verbal -> vic
  (31) Groupe-verbal -> Verbe-avec-complément
  (32) Verbe-avec-complément -> vtc Groupe-nominal

La table LL(2) est :

Question: Analyser Berthe étudie un fichier transmis par Chantal avec la table ci-dessus (le niveau de reconnaissance des mots indique que l'énoncé est formé de np vtc un ncm ppm prep np).

Cliquer ici pour voir la réponse.