Précédent Index Suivant

Basic revisité

Nous voulons à présent utiliser le couple ocamllex et ocamlyacc afin de remplacer la fonction parse donnée page ?? pour Basic, par des fonctions engendrées à partir des fichiers de spécification du lexique et de la syntaxe du langage.

Pour y arriver, nous ne pourrons pas reprendre tels quels le type des unités lexicales que nous avions défini. Nous allons devoir définir un type plus précis permettant de distinguer les différents opérateurs, les commandes et les mots clés.

Nous aurons également besoin d'isoler les déclarations de type concernant la syntaxe abstraite dans un fichier basic_types.mli. Il contiendra les déclarations du type phrases et de tous les types nécessaires à celui-là.

Le fichier basic_parser.mly

L'en-tête
du fichier contient un appel aux déclarations de types pour la syntaxe abstraite ainsi que deux fonctions auxiliaires de conversion de chaînes de caractères vers leur équivalent en syntaxe abstraite. 

%{
open Basic_types ;;

let phrase_of_cmd c =
 match c with
   "RUN" -> Run
 | "LIST" -> List
 | "END" -> End
 | _ -> failwith "line : unexpected command"
;;

let op_bin_of_rel r =
 match r with
   "=" -> EGAL
 | "<" -> INF
 | "<=" -> INFEQ
 | ">" -> SUP
 | ">=" -> SUPEQ
 | "<>" -> DIFF
 | _ -> failwith "line : unexpected relation symbol"
;;

%}


Les déclarations
contiennent trois parties : la déclaration des lexèmes; la déclaration de leurs règles d'associativité et de priorité; la déclaration de la règle axiome line qui correspond à l'analyse d'une ligne de programme ou de commande.

Les unités lexicales sont les suivantes : 


 %token <int> Lint
 %token <string> Lident
 %token <string> Lstring
 %token <string> Lcmd
 %token Lplus Lmoins Lmult Ldiv Lmod
 %token <string> Lrel
 %token Land Lor Lneg
 %token Lpar Rpar
 %token <string> Lrem 
 %token Lrem Llet Lprint Linput Lif Lthen Lgoto
 %token Legal
 %token Leol
Leurs noms parlent d'eux-mêmes et ils sont décrits par le fichier basic_lexer.mll (voir page ??).

Les règles de priorité entre opérateurs reprennent les valeurs données par les fonctions priority_ob et priority_ou définies lorsque nous avions donnée la grammaire de notre Basic (voir page ??). 


 %right Lneg
 %left Land Lor
 %left Legal Lrel
 %left Lmod
 %left Lplus Lmoins
 %left Lmult Ldiv
 %nonassoc Lopp
Le symbole Lopp nous servira à traiter le moins unaire. Ce n'est pas un terminal de la grammaire, mais un << pseudo non terminal >> permettant de gérer la surcharge entre opérateurs lorsque deux utilisations d'un même symbole ne doivent pas avoir la même priorité selon le contexte. Et c'est le cas du symbole moins (-). Nous reviendrons sur ce point lorsque nous aurons énoncé les règles de la grammaire.

Le non terminal axiome est line. La fonction engendrée retournera l'arbre de syntaxe abstraite de la ligne analysée. 

 %start line
 %type <Basic_types.phrase> line
Les règles
de grammaire se décomposent en trois non terminaux : line pour une ligne; inst pour une instruction du langage; exp pour les expressions. L'action associée à chacune des règles se contente de construire le morceau de syntaxe abstraite correspondant. 

 %%
line : 
   Lint inst Leol               { Ligne {num=$1; inst=$2} }
 | Lcmd        Leol                    { phrase_of_cmd $1 }
 ;

inst :
   Lrem                         { Rem $1 }
 | Lgoto Lint                   { Goto $2 }
 | Lprint exp                   { Print $2 }
 | Linput Lident                { Input $2 }
 | Lif exp Lthen Lint           { If ($2, $4) }
 | Llet Lident Legal exp        { Let ($2, $4) }
 ;

exp :
   Lint                         { ExpInt $1 }
 | Lident                       { ExpVar $1 }
 | Lstring                      { ExpStr $1 }
 | Lneg exp                     { ExpUnr (NON, $2) }
 | exp Lplus exp                { ExpBin ($1, PLUS, $3) }
 | exp Lmoins exp               { ExpBin ($1, MOINS, $3) }
 | exp Lmult exp                { ExpBin ($1, MULT, $3) }
 | exp Ldiv exp                        { ExpBin ($1, DIV, $3) }
 | exp Lmod exp                        { ExpBin ($1, MOD, $3) }
 | exp Legal exp                { ExpBin ($1, EGAL, $3) }
 | exp Lrel exp                        { ExpBin ($1, (op_bin_of_rel $2), $3) }
 | exp Land exp                 { ExpBin ($1, ET, $3) }
 | exp Lor exp                  { ExpBin ($1, OU, $3) }
 | Lmoins exp %prec Lopp        { ExpUnr(OPPOSE, $2) }
 | Lpar exp Rpar                { $2 }
 ;
 %%
Ces règles n'appellent pas de commentaire particulier sauf celle-ci : 
exp :
 ...
 | Lmoins exp %prec Lopp { ExpUnr(OPPOSE, $2) }
Elle concerne l'utilisation unaire du symbole -. Le mot clé %prec que l'on trouve dans cette règle indique que cette construction doit recevoir la priorité de Lopp (ici, la priorité maximale).

Le fichier basic_lexer.mll

L'analyse lexicale ne contient qu'un seul ensemble : lexer qui correspondra au type près à l'ancienne fonction lexer (voir page ??). L'action sémantique associée à la reconnaissance de chaque unité lexicale est simplement le renvoi du constructeur correspondant. Comme le type des unités lexicales est déclaré dans le fichier des règles de syntaxe, il faut inclure ce dernier. On rajoute une petite fonction auxiliaire chargée de supprimer les guillemets autour des chaînes de caractères. 

{
 open Basic_parser ;;

 let string_chars s = String.sub s 1 ((String.length s)-2) ;;
}

rule lexer = parse
   [' ' '\t']            { lexer lexbuf }

 | '\n'                  { Leol }

 | '!'                   { Lneg }
 | '&'                   { Land }
 | '|'                   { Lor }
 | '='                         { Legal }
 | '%'                         { Lmod }
 | '+'                         { Lplus }
 | '-'                         { Lmoins }
 | '*'                         { Lmult }
 | '/'                         { Ldiv }

 | ['<' '>']             { Lrel (Lexing.lexeme lexbuf) }
 | "<="                         { Lrel (Lexing.lexeme lexbuf) }
 | ">="                         { Lrel (Lexing.lexeme lexbuf) }

 | "REM" [^ '\n']*       { Lrem (Lexing.lexeme lexbuf) }
 | "LET"                 { Llet }
 | "PRINT"               { Lprint }
 | "INPUT"               { Linput }
 | "IF"                  { Lif }
 | "THEN"                { Lthen }
 | "GOTO"                { Lgoto }

 | "RUN"                { Lcmd (Lexing.lexeme lexbuf) }
 | "LIST"               { Lcmd (Lexing.lexeme lexbuf) }
 | "END"                { Lcmd (Lexing.lexeme lexbuf) }
 
 | ['0'-'9']+           { Lint (int_of_string (Lexing.lexeme lexbuf)) }
 | ['A'-'z']+           { Lident (Lexing.lexeme lexbuf) }
 | '"' [^ '"']* '"'     { Lstring (string_chars (Lexing.lexeme lexbuf)) }
Remarquons que nous avons dû isoler le symbole = qui sert à la fois dans les expressions et dans l'instruction d'affectation.

Seules deux de ces expressions rationnelles nécessitent des explications complémentaires. La première concerne les lignes de commentaires ("REM" [^ '\n']*). Elle reconnaît le mot clé REM suivi par un nombre quelconque de caractères différents du retour chariot. La seconde concerne les chaîne de caractères ('"' [^ '"']* '"') considérées comme une suite de caractères différents de " et encadrée par des ".

Compilation, intégration

La compilation du couple analyseur lexical, analyseur syntaxique doit être faite en suivant un certain ordre. Ceci est dû à la dépendance mutuelle dans la déclaration des lexèmes. Ainsi, dans notre exemple, il faudra taper la séquence de commandes : 
ocamlc -c basic_types.mli
ocamlyacc basic_parser.mly
ocamllex basic_lexer.mll
ocamlc -c basic_parser.mli
ocamlc -c basic_lexer.ml
ocamlc -c basic_parser.ml
Ce qui engendrera les fichiers basic_lexer.cmo et basic_parser.cmo qui pourrons être intégrés à l'application.

Nous disposons maintenant de tout le matériel nécessaire pour reformuler notre application.

Nous supprimons tous les types et toutes les fonctions des paragraphes << analyse lexicale >> (page ??) et << analyse syntaxique >> (page ??) de l'application Basic et, dans la fonction une_commande (page ??), nous remplaçons l'expression 

    match parse (input_line stdin) with
par 

    match line lexer (Lexing.from_string ((input_line stdin)^"\n")) with
Remarquons que nous devons remettre en fin de ligne le caractère '\n' que la fonction input_line avait supprimé. Ceci est nécessaire, car nous utilisons ce caractère pour marquer la fin d'une ligne de commande (Leol).





Précédent Index Suivant