TD-5, analyse syntaxique, vérification de tautologies

TD-5, analyse syntaxique, vérification de tautologies

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-5/

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

Le but avoué de cet exercice est la construction d'un vérificateur de tautologies, c'est à dire d'un programme qui nous dit si une proposition est toujours vraie ou pas. Le but caché est l'écriture d'un analyseur syntaxique simple (recursive descent) et de quelques parcours d'arbres.

1	Un langage des propositions

On se donne le langage des expression défini par les constantes true et false, des variables VAR et les connecteurs ``et'' (/\), ``ou'' (\/) et ``non'' (!), plus les habituelles parenthèses.

B = true | false | VAR | B \/ B | B /\ B | ! B | ( B )

Les ambiguïtés présentes étant résolues en donnant des priorités aux opérateurs, ! étant la plus prioritaire, puis /\, puis \/. Ainsi qu'en faisant pencher les arbres à gauche. (Voyez /\ comme la multiplication et \/ comme l'addition et vous comprenez.)

Ces règles permettent une transformation de la grammaire des expressions B en une forme plus pratique :

B	=	O `EOF`	Expressions
O	=	E `\/` O `\|` E	Disjonctions
E	=	F `/\` E `\|` F	Conjonctions
F	=	`true` `\|` `false` `\|` `VAR` `\|` `!` O `\|` `(` O `)`	Expressions de base

(Le lexème EOF sert juste à garantir que l'on identifiera la proposition la plus longue possible, c'est important en pratique).

2	Programmation de l'analyseur

2.1

Analyse lexicale

Sont données les classes Lexeme et Lexer qui constituent l'analyseur lexical, suivant les conventions du cours. À savoir :

Les lexèmes identifiés par leur champ nature sont les mots-clefs correspondant aux constantes et aux opérateurs. Ils sont reconnus par le lexer et identifiés par le champ nature égal à TRUE, FALSE, OR, AND, NOT, OPAR, CPAR. Le lexème VAR est le seul qui a un champ ``as_var'' valide qui contient le nom de la variable comme un String.
Le lexème EOF est simplement null.
On crée un lexer à l'aide du constructeur Lexer, qui prend un Reader en argument.
On obtient le lexème suivant par la méthode next() d'un lexer.

2.2

Analyse syntaxique

La classe Bool des arbres représentant les propositions est partiellement donnée. Cette classe encode des arbres comme dans le cours, un champ nature (avec cinq valeurs possibles FALSE, TRUE, OR, AND, NOT, VAR), plus d'autres champs à utiliser ou pas selon la nature des noeuds de l'arbre (as_var pour les variables, arg0 et arg1 pour les sous-expressions). La classe Bool comprend aussi une méthode display() sophistiquée, utile pour visualiser les arbres, mais pas de méthode toString().

Écrire une classe LL, qui définit au moins :

Une méthode parse :
```
static Bool parse (Reader in)
```
Telle que parse réalise l'analyse syntaxique du flot in. Il est fortement conseillé de considérer la section 1 de ce document et de s'inspirer des transparents (planches 9, puis 15 et 16). C'est à dire qu'il est conseillé de transformer les règles de la section 1 en un programme, comme les planches 15 et 16 sont le programme correspondant à la planche 9.

Cette méthode main de test :

  public static void main (String [] args) {
    Bool b = parse(new InputStreamReader (System.in)) ;
    System.err.println("Voici l'arbre :\n" + b.display ()) ;
    System.out.println(b) ;
    return ;
  }

Donc la méthode main, parse l'entrée standard, affiche la représentation arborescente du résultat sur la sortie d'erreur et la représentation linéaire sur la sortie standard.

Il est donc aussi demandé d'écrire une méthode toString pour les arbres Bool, qui en quelque sorte défait l'analyse syntaxique.

Ainsi, à partir des exemples ex1.b, ex2.b et ex3.b. On obtiendra :

maranget@manche ~/TD/TD-5 > cat ex1.b
A \/ B \/ C
maranget@manche ~/TD/TD-5 > java LL < ex1.b
java LL < ../ex1.b          
Voici l'arbre :
    ____OR_
  _OR_     C 
 A    B 

((A \/ B) \/ C)
maranget@manche ~/TD/TD-5 > cat ex2.b
A \/ !B /\ C
maranget@manche ~/TD/TD-5 > java LL < ex2.b
Voici l'arbre :
  _OR_____
 A     __AND_
      NOT    C 
       |
      B 

(A \/ (!B /\ C))

On remarquera que suivre directement la technique des transparents donnera des arbres qui penchent naturellement à droite en l'absence de parenthèses explicites Essayez de les faire pencher naturellement à gauche, (cf. le premier exemple). Bon, si on veut faire sérieux, on parlera de l'associativité gauche ou droite des opérateurs /\ et \/. Mais ça me semble un peu plus confus que la notion de pencher d'un côté ou de l'autre surtout si on considère que les opérateurs sous-jacents sont associatifs...Solution.

3	Un vérificateur de tautologies

Si on donne des valeurs, vrai ou faux, aux variables, il est facile d'évaluer la valeur dite de vérité d'une proposition quelconque, en se servant des règles usuelles.

Par définition, une tautologie est une proposition qui est vraie quelque soient les valeurs de ses variables. Par exemple A \/!A est une tautologie. Pour le vérifier, il suffit d'essayer pour A vrai et A faux.

Il vous est donc demandé d'écrire une classe-programme Toto qui lit une proposition sur l'entrée standard et dit s'il s'agit d'une tautologie ou pas. La démarche suivante, inspirée de la définition de la tautologie est suggérée :

Concevoir une classe des environnements (ou valuations) qui associe des chaînes à des booléens (une solution simple utilise les listes).
Écrire une méthode qui prend une proposition et une valuation de ses variables et évalue la proposition selon les règles classiques du calcul des propositions.
Collecter toutes les variables d'une proposition.
Énumérer les valuations possibles de ces variables et évaluer la proposition pour chacune des valuations trouvées. Dès qu'une évaluation rend faux on a montré que la proposition n'est pas une tautologie. Sinon (toutes les évaluations rendent vrai), la proposition est une tautologie.

Un plus, dans le cas où la proposition n'est pas une tautologie est d'afficher la valuation qui l'invalide. En plus des exemples précédent, vérifier que ex4.b est une tautologie. Solution.

4	Une histoire de pigeon

Soient n nids de pigeons et n+1 pigeons. Il semble assez clair (principe du nid de pigeon) que si chaque pigeon occupe un nid, alors au moins un nid sera occupé par au moins deux pigeons. Si on code ``le nid i est occupé par le pigeon j'' par la variable Hij, alors la proposition ex4.b exprime le principe du pigeon pour n=2. La première ligne exprime que chaque pigeon est logé, tandis que la dernière exprime qu'au moins un nid contient deux pigeons, les deux propositions étant combinées par le connecteur implication P => Q, codé comme ! P \/ Q. L'application de Toto à cette proposition est la preuve du principe du nid de pigeon pour n=2.

Écrire une classe Pigeon qui vérifie le principe du nid de pigeon pour un entier passé en argument sur la ligne de commande.

Sur le même principe on pourra peut-être (!) vérifier que l'on peut placer n reines sur un échiquier de taille n par n, de sorte qu'aucune reine ne puisse en prendre une autre. Voir la page 28 de ce document trouvé sur le web (un document intéressant par ailleurs, à visualiser avec gv ou ghostview).

Dernière modification : 2002-11-27

Ce document a été traduit de L^AT_EX par H^EV^EA.