Analyse syntaxique

Les solutions sont à la fin.

1  Langage de parenthèses

1.1  Un peu de théorie

La deuxième partie de l'examen de 1999 introduisait deux grammaires pour le langage des parenthèses :
Grammaire G1
S1 -> E1
E1 -> ( E1 )
E1 -> E1 E1
E1 ->
    
Grammaire G2
S2 -> E2
E2 -> ( E2 ) E2
E2 ->
L'examen consistait à démontrer que ces deux grammaires sont équivalentes.

1.2  Un peu de pratique

Un analyseur syntaxique de G1 est fourni, il s'agit des trois fichiers sources lexer1.mll (analyseur lexical), g1.mly (analyseur grammatical) et check1.ml. Récupérer tout, ainsi que le Makefile et le fichier de dépendances .depend, et compiler par « make check1 ». (En cas de pépin, essayez « make clean » (tout effacer), « make depend » (reconstruire les dépendances) et recommencez « make check1 », ça marchera sans doute).

On s'aperçoit que ocamlyacc détecte des ambiguïtés : 
# make check1
ocamlyacc g1.mly
8 shift/reduce conflicts, 2 reduce/reduce conflicts.
ocamlc -c g1.mli
ocamlc -c g1.ml
ocamllex lexer1.mll
5 states, 257 transitions, table size 1058 bytes
ocamlc -c lexer1.ml
ocamlc -c check1.ml
ocamlc -o check1 g1.cmo lexer1.cmo check1.cmo
On remarquera au passage l'intérêt de make et les dépendances un peu étranges. En effet le type des lexèmes doit être défini par le fichier .mly ce qui impose finalement que le lexer dépend du parseur.

Le vérificateur check1 lit l'entrée standard : 
# ./check1 
()(())
C'est bon
# ./check1
(
C'est pas bon
L'exercice consiste à écrire l'analyseur syntaxique check2 qui reconnaît la grammaire G2. Que veut dire en pratique l'équivalence de G1 et G2 ? L'ambiguïté de G1 est elle gênante pour cette application de vérification.

2  Arbres martiens

2.1  Le problème des Martiens

Les martiens se donnent cette définition des arbres binaires à feuilles entières :
type t = Leaf of int | Node of t * t

Ils souhaitent fabriquer ces arbres à partir de l'entrée standard (oui, les martiens on une entrée standard et programment en OCaml).

Là où ça se corse un peu, c'est que les chercheurs martiens, indépendamment des programmeurs se sont donné cette grammaire M1 des arbres.
Grammaire M1
S1 -> T1    symbole de départ
T1 -> ( T1 )    parenthésage
T1 -> T1 T1    noeud de l'arbre
T1 -> INT    feuille terrienne
T1 ->    zéro martien
Où INT est un entier terrien, et rien «» vaut zéro selon l'archaïque convention martienne.

Les programmeurs martiens ont déjà produit les sources tree.mli (arbres), lexmars.mll (lexer de technologie terrienne qui ne reconnaît pas le zéro martien) et mars.ml (fichier qui mélange le tout et contient un imprimeur des arbres). Ils ont commencé le parseur parsemars.mly, mais ils coincent. Aidez les !.

Une fois écrit parsemars.mly, vous compilerez par « make mars ».

2.2  Un peu d'aide

La grammaire M1 est ambigüe, car l'entrée standard « 1 2 3 », ne manque pas d'interprétations en termes d'arbres, puisque tous les arbres suivants sont des interprétations valides : 
   /\             /\              /\
  1  \           /  3            /  \
     /\         /\              /    \
    2  3       1  2            /\   / \
                              1  0 2   3
Pourtant l'analyseur mars obtenu en recopiant la grammaire des mathématiciens martiens fait un choix. Lequel ?

Peut être aurez-vous besoin d'écrire la grammaire ambigüe des arbres martiens d'abord et de lire les diagnostics de ocamlyacc, voir le poly pour comprendre comment lire ces fichiers parsemars.output.

Pour que le choix ne dépende plus de ocamlyacc mais du programmeur, il faut concevoir une grammaire non-ambigüe des arbres martiens. En pratique, on s'attachera à reconnaître le même langage que mars (sans produire forcément les mêmes arbres) et à ne plus avoir de conflit lors de la compilation de la grammaire. Vous pouvez vous faire une idée des conflits en compilant votre analyseur par ``ocamlyacc -v'' et en allant regarder le fichier d'extension .output

3  Un parseur pour Pseudo-Pascal

Il s'agit d'écrire un analyseur grammatical pour pseudo-pascal. La description de la grammaire pseudo-pascal est ici.

Pour vous permettre de vous concentrer sur le développement de votre parseur, l'analyseur lexical lexer.mll, un début de parseur parser.mly, qui contient notamment toutes les définitions de lexèmes et la première règle, et le source checkpp.ml qui appelle le parseur, sont donnés.

Écrire d'abord un programme qui reconnaît si l'entrée est du pseudo-pascal valide ou pas. Ou peut alors se contenter de mettre unit ``()'' dans toutes les actions du parseur. La compilation s'effectue encore une fois à l'aide du Makefile que vous avez déjà. 
% make checkpp
ocamlyacc -v parser.mly
ocamlc -c parser.mli
ocamlc -c parser.ml
ocamllex lexer.mll
125 states, 8114 transitions, table size 33206 bytes
ocamlc -c lexer.ml
ocamlc -c checkpp.ml
ocamlc -o checkpp parser.cmo lexer.cmo checkpp.cmo
Pour tester un peu checkpp, voici un programme pseudo-pascal, fact.p.

Dans un deuxième temps écrire un parseur qui construit l'arbre de syntaxe abstraite du programme reconnu. Cette syntaxe abstraite est définie dans l'interface pp.mli. Il faudra alors : Il va de soi qu'il ne fait pas attendre d'avoir tout écrit pour tenter de compiler...

On compilera alors par ``make ppp'', et on devrait obtenir : 
% ./ppp < fact.p
program
  var x : integer;
function fact (n : integer) : integer;
begin
   if n <= 1 then fact := 1 else fact := n * fact (n - 1)
end ;

begin
   read (x);
   writeln (fact (x))
end.



Solutions

Grammaires équivalentes

Il y a peu à dire sur le premier exercice, les grammaires sont équivalentes, donc par définition, les vérificateurs check1 et check2 reconnaissent le même langage. Les fichiers solution sont lexer2.mll, g2.mly et check2.ml.

Tout de même, rien ne nous dit que le vérificateur check1 suffit pour vérifier tous les mots de G1. Les choix par défaut de ocamlyacc pourraient le conduire à rater des mots de G1.

Voyage sur Mars

Pour les arbres martiens, il suffit de recopier la grammaire M1 dans un fichier parsemars.mly. La compilation révèle une grammaire extrêmement ambigüe : 
ocamlyacc -v parsemars.mly
14 shift/reduce conflicts, 2 reduce/reduce conflicts.
Il s'agit ensuite d'écrire une grammaire M2 équivalente à M1 mais non-ambigüe. Revoyons donc M1 :
Grammaire M1
S -> T    symbole de départ
T -> ( T )    parenthésage
T -> T T    noeud de l'arbre
T -> INT    feuille terrienne
T ->    zéro martien
Il y a deux sources d'ambiguité : le zéro martien et la définition des noeuds, qui fait fi de ce qui appartient aux sous-arbres gauches et droits.

Par example la chaîne vide peut être engendrée de bien des façons :
T ->     ou     T -> T T -> T ->
Ce qui veut dire que la chaîne «» vide peut être interprétée comme les arbres : 
0       ou,      /\
                0  0
De même on peut générer « 1 2 3 » au moins de deux manières :
T -> T T-> T 3 -> T T 3 -> T 2 3 -> 1 2 3
ou,
T -> T T-> 1 T -> 1 T T -> 1 2 T ->
Ce qui, lu à l'envers, nous donne les arbres : 
      /\                /\
     /  3    ou,       1  \
    /\                    /\
   1  2                  2  3
Une technique possible est de transformer la grammaire de départ. On part de M1 et on commence par supprimer la production T -> , en ajoutant une production avec T à droite remplacé par «» (rien), partout où c'est possible :
⎛
⎜
⎜
⎜
⎝
S -> T
  
T -> T T
T -> (T)
T -> INT
T ->
⎞
⎟
⎟
⎟
⎠		   =>   ⎛
⎜
⎜
⎜
⎝
S -> T
S ->
  
T -> T T
T -> (T)
T -> ()
T -> INT
⎞
⎟
⎟
⎟
⎠
Les productions genre T -> T sont tout de suite supprimées quand elles n'ajoutent évidemment rien au langage reconnu.

Ensuite on élimine la récursion gauche dans T -> T T et on introduit un non-terminal U pour regrouper les cas dits de base :
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
S -> T
S ->
  
T -> (T) T0
T -> () T0
T -> INT T0
 
T0 -> T T0
T0 ->
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠		   =>   ⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
S -> T
S ->
  
T -> U T0
 
U -> ( T )
U -> ( )
U -> INT
 
T0 -> T T0
T0 ->
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
Une remontée de T0 -> , révèle s'il en était besoin que T et T0 sont la même chose :
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
S -> T
S ->
 
T -> U T0
T -> U
  
U -> ( T )
U -> ( )
U -> INT
 
T0 -> T T0
T0 -> T
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠		   =>   ⎛
⎜
⎜
⎜
⎜
⎝
S -> T
S ->
 
T -> U T
T -> U
  
U -> ( T )
U -> ( )
U -> INT
 
T -> T T
⎞
⎟
⎟
⎟
⎟
⎠

On peut maintenant, sans diminuer le langage reconnu, supprimer la règle T -> T T. En effet, les règles T -> U T et T -> T T génèrent le même langage : une suite de U (argument un peu raide mais point scandaleux).
⎛
⎜
⎜
⎜
⎜
⎝
S -> T
S ->
 
T -> U T
T -> U
  
U -> ( T )
U -> ( )
U -> INT
⎞
⎟
⎟
⎟
⎟
⎠

On vérifie en compilant parsemars2.mly que cette grammaire est bien non ambigüe. (pour fabriquer mars2, on a encore besoin de lexmars2.mll et de mars2.ml).

Pour les curieux

On peut pouver que l'on a bien le droit de supprimer la production T -> T T en s'inspirant du contrôle. Soit un arbre de dérivation qui reconnaît un mot m.
type deriv_t =
| U  of deriv_u
| UT of deriv_u * deriv_t
| TT of deriv_t * deriv_t
and deriv_u =
| Rec of deriv_t
| ParPar
| Int of string

Le mot reconnu est facilement retrouvée par la fonction suivante :
let rec vu_t = function
| U u -> vu_u u
| UT (u,t) -> vu_u u @ vu_t t
| TT (t1,t2) -> vu_t t1 @ vu_t t2
and vu_u = function
| Rec t -> ["("] @ vu_t t @ [")"]
| ParPar ->   ["(" ; ")"]
| Int s  ->   [s]

On enlève les règles TT ainsi.
let rec enleve_t = function
| U u       -> U (enleve_u u)
| UT (u, t) -> UT (enleve_u u, enleve_t t)
| TT (t1, t2) -> begin match enleve_t t1 with
  | UT (u1,t1) -> UT (u1, enleve_t (TT (t1,t2)))
  | U u1       -> UT (u1, enleve_t t2)
  | _          -> assert false
  end
and enleve_u = function
| Rec t -> Rec (enleve_t t)
| u     -> u
Il est évident que la fonction enleve_t, si elle termine sans échouer produit des arbres sans TT, car ce constructeur n'apparaît pas dans les actions des match, ceci entraîne l'absence d'échec ``assert false''. La terminaison provient de ce que les arbres argument des appels récursifs sont plus petits (en nonbre de noeuds) que l'arbre passé en argument (modulo le lemme que les deux fonctions enleve_t et enleve_u rendent un résultat de taille plus petite que leur argument). Bref, on a montré que l'on peut faire pencher à droite un arbre arbitraire...

Il reste a montrer que l'arbre transformé E(t) = enleve_t(t) reconnaît le même mot que l'arbre de départ t. C'est pas dur, notons M(t) mot reconnu et voyons par example le cas, t = TT(t1, t2). il y a deux sous cas :

Un analyseur syntaxique complet pour Pseudo-Pascal

Le voilà : lexer.mll et parser.mly (et l'affichage des arbres print.ml et print.mli, et le driver ppp.ml).

L'analyseur lexical utilise le truc classique de ne pas reconnaître les mots-clefs directement dans le lexer, mais à posteriori parmi les séquences de lettres et à l'aide d'une table de hachage. Ce truc donne des tables de lexer bien moins grosses. L'afficheur utilise le module Format de la bibliothèque standard, bien pratique mais un peu compliqué à maîtriser.

Ce document a été traduit de LATEX par HEVEA.