tabular317

Yacc et OcamlYacc

La construction des tables LALR(1) pour un vrai langage produit des automates avec plusieurs centaines d'états (ma grammaire pour le langage du projet en a 125), donc il faut utiliser des générateurs automatiques qui prennent une description de la grammaire et produisent un analyseur.

Tel est le but de Yacc (ou Bison) qui produisent un analyseur écrit en C, et de OcamlYacc, qui produit un analyseur écrit en Ocaml.
Ces générateurs d'analyseurs sont fait pour travailler en tandem avec Lex (ou Flex) pour C, et OcamlLex, respectivement.

La grammaire des sommes, en OcamlYacc

La grammaire suivante, vue dans la partie théorique

displaymath380

est décrite dans le fichier source OcamlYacc suivant 

%{
%}
/ ceci est un commentaire: comme en C, mais seulement pour OcamlYacc! /
%token EOF ID PLUS
%start s
%type  s
%%
s:  e EOF {}
;
e:     t PLUS e {}
     | t {}
;
t:     ID {}
;
%%

Structure de la source OcamlYacc

Comme pour OcamlLex, la source est divisée en plusieurs parties logiques: 

%{
  déclarations et code Ocaml
  utilisés dans les actions de l'analyseur
%}
  directives et déclarations pour OcamlYacc
%%
  description des règles de la grammaire
%%
  déclarations et code Ocaml qui utilisent
  les fonctions d'analyses produites par OcamlYacc

Directives et déclarations pour OcamlYacc

%token symbol...symbol
Déclaration des symboles terminaux.

%token < type > symbol...symbol
Déclaration de tokens ayant une valeur sémantique associée de type type.

%start symbol...symbol
Déclaration des points d'entrée.

%type < type > symbol...symbol
Déclaration du type renvoyé par la fonction analysant le non terminal donné. Nécessaire seulement sur le points d'entrée (à différence de Yacc!)

%left symbol...symbol
%right symbol...symbol
%nonassoc symbol...symbol
Déclaration de précédence et associativité (on les verra plus en bas).

Description des règles de la grammaire

Les lignes 

e:     t PLUS e {}
     | t {}
;
décrivent les deux productions

displaymath390

Entre accolades on peut mettre du code Ocaml, qui a accès à des valeurs $1...$n, sur lesquels on reviendra.

Appel de OcamlYacc

Si exmpl.mly contient le source OcamlYacc, alors la commande 

ocamlyacc exmpl.mly
produit les fichiers
exmpl.mli
la description de l'interface de l'analyseur.
Cela contient aussi la définition d'un type Ocaml token contenant tous les tokens déclarés avec la directive %token.
On peut ensuite utiliser ce fichier dans un fichier d'entrée pour OcamlLex, ce qui permet d'écrire la définition des tokens une seule fois à un seul endroit.
exmpl.ml
l'analyseur syntaxique produit par OcamlYacc. Cela définit une fonction 
fnt: (Lexing.lexbuf -> token) -> Lexing.lexbuf -> t
pour chaque symbole non terminal fnt déclaré dans une directive %start et dont le type t est donné dans une directive %type.

Appel de OcamlYacc (suite)

Si exmpl.mly contient le source OcamlYacc, alors la commande 

ocamlyacc -d exmpl.mly
produit en plus le fichier
exmpl.output
la description de l'automate LALR(1).

Utiliser des grammaires ambiguës

OcamlYacc (comme Yacc), permet (et encourage) l'utilisation de grammaires ambiguës, pour lesquelles on utilise les directives %left, %right et %nonassoc pour spécifier associativité et précédence: 

/ on veut lire -1+345=-4+3+4 comme ((-1)+((34)5))=(((-4)+3)+4)  /
%nonassoc EQUAL    / precédence faible, associtivité non spécifiée  /
%left MULT         / précédence moyenne, associativité à gauche     /
%left PLUS         / précédence plus élevée, associativité à gauche /
%nonassoc UMINUS   / précédence encore plus relevée, associativité non spécifiée /

Exemple

Donc pour la grammaire

displaymath394

plutôt que disambiguer en

displaymath380

on peut utiliser le source OcamlYacc suivant est équivalent, mais plus rapide 

%{
%}
%token EOF ID PLUS
%right PLUS
%start s
%type  s
%%
s:  e EOF {};
e:     e PLUS e {}
     | ID {};
%%

Précédences, directive %prec

On peut aussi introduire des terminaux fictifs, juste pour les précédences:

displaymath398 

%{
%}
%token EOF ID PLUS LET EQUALS IN
%nonassoc LETPREC
%right PLUS
%start s
%type  s
%%
s:  e EOF {};
e:     e PLUS e {}
     | ID {}
     | LET ID EQUALS e IN e   %prec LETPREC {};
%%

Précédences, if then else

Un autre cas typique est

displaymath400 

%{
%}
%token EOF IF THEN ELSE ID
%start s
%type  s
%%
s:  e EOF {};
e:     ID {}
     | IF e THEN e {}
     | IF e THEN e ELSE e  {};
%%

Précédences, if then else (suite)

displaymath400

L'ambiguïté produit le conflit: 

10: shift/reduce conflict (shift 11, reduce 3) on ELSE
state 10
    e : IF e THEN e .  (3)
    e : IF e THEN e . ELSE e  (4)


    ELSE  shift 11
    EOF  reduce 3
    THEN  reduce 3

OcamlYacc choisit toujours shift dans un conflit shift/reduce, ce qui est bien dans ce cas, donc on ne modifie pas la source.

Pièges à éviter

Ceci est attrayant, ... 

%{
%}
%token EOF ID PLUS MULT MINUS
%start s
%right PLUS MINUS
%left MULT
%type  s
%%
s:  e EOF {};
e:
       e op e {}
     | ID {};
op: 

       PLUS  {}
     | MULT  {}
     | MINUS {};
%%

Pièges à éviter

... mais mauvais (et les précédences ne règlent pas le problème) 

11: shift/reduce conflict (shift 7, reduce 2) on PLUS
11: shift/reduce conflict (shift 8, reduce 2) on MULT
11: shift/reduce conflict (shift 9, reduce 2) on MINUS
state 11
    e : e . op e  (2)
    e : e op e .  (2)


    PLUS  shift 7
    MULT  shift 8
    MINUS  shift 9
    EOF  reduce 2


    op  goto 10

Pièges à éviter

Il faut 

%{
%}
%token EOF ID PLUS MULT MINUS
%start s
%right PLUS MINUS
%left MULT
%type  s
%%
s:  e EOF {};
e:
       e PLUS e {}
     | e MULT e {}
     | e MINUS e {}
     | ID {};
%%

Un exemple complet: la calculette (I)

Le lexeur... 

( File lexer.mll )
{
open Parser        ( The type token is defined in parser.mli )
exception Eof
}
rule token = parse
[' ' '\t']     { token lexbuf }     ( skip blanks )
| ['\n' ]        { EOL }
| ['0'-'9']+     { INT(int_of_string(Lexing.lexeme lexbuf)) }
| '+'            { PLUS }
| '-'            { MINUS }
| ''            { TIMES }
| '/'            { DIV }
| '('            { LPAREN }
| ')'            { RPAREN }
| eof            { raise Eof }

Un exemple complet: la calculette (II)

Le parseur... 

 / File parser.mly /
%token <int> INT
%token PLUS MINUS TIMES DIV LPAREN RPAREN EOL
%left PLUS MINUS        / lowest precedence /
%left TIMES DIV         / medium precedence /
%nonassoc UMINUS        / highest precedence /
%start main             / the entry point /
%type <int> main
%%
main:  expr EOL                 { $1 };
expr: INT                       { $1 }
      | LPAREN expr RPAREN      { $2 }
      | expr PLUS expr          { $1 + $3 }
      | expr MINUS expr         { $1 - $3 }
      | expr TIMES expr         { $1 * $3 }
      | expr DIV expr           { $1 / $3 }
      | MINUS expr %prec UMINUS { - $2 };

Un exemple complet: la calculette (III)

La boucle principale... 

 ( File calc.ml *)
let _ =
try
let lexbuf = Lexing.from_channel stdin in
while true do
let result = Parser.main Lexer.token lexbuf in
print_int result; print_newline(); flush stdout
done
with Lexer.Eof ->
exit 0

Un exemple complet: la calculette (fin)

Le fichier Makefile 

CAMLC=ocamlc
CAMLLEX=ocamllex
CAMLYACC=ocamlyacc



all: parser.cmi parser.cmo lexer.cmo calc.cmo
            ocamlc -o calc lexer.cmo parser.cmo calc.cmo
clean:
    rm .cmo .cmi



generic rules :



#



.SUFFIXES: .mll .mly .mli .ml .cmi .cmo
.mll.mli:
    $(CAMLLEX) $<
.mll.ml:
    $(CAMLLEX) $<
.mly.mli:
    $(CAMLYACC) $<
.mly.ml:
    $(CAMLYACC) $<
.mli.cmi:
    $(CAMLC) -c $(FLAGS) $<
.ml.cmo:
    $(CAMLC) -c $(FLAGS) $<

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 q.tex.

The translation was initiated by Roberto Di Cosmo on Tue Nov 16 15:30:37 MET 1999

Roberto Di Cosmo
Tue Nov 16 15:30:37 MET 1999