• Schéma de principe
• Retourner des valeurs sémantiques dans OcamlLex
• Traitement des valeurs sémantiques dans le cadre LR ambiguë
• Retourner des valeurs sémantiques dans OcamlYacc
• L'exemple classique: la calculette en OcamlYacc/OcamlLex.
• Bref aperçu des grammaires attribuées
• Traitement des valeurs sémantiques dans le cadre LL

Les exemples avec les sources sont disponibles comme fichiers Tar Gzip

Schéma de principe

On a vu construire un analyseur lexical (OcamlLex), des analyseurs LL (à la main) et LR (via OcamlYacc), mais ces constructions se limitent à répondre OUI ou NON à la question est-ce ce mot partie du langage r&#233;gulier ou alg&#233;brique suivant?'' <P> Nous devons maintenant enrichir cette r&#233;ponse avec de l'information s&#233;mantique (c'est &#224; dire avec des valeurs qui d&#233;crivent le mot qui a &#233;t&#233; reconnu, ou une autre information calcul&#233;e &#224; partir de ce mot). En g&#233;n&#233;ral, la premi&#232;re partie de notre compilateur (le front-end'') aura la structure du schéma suivant

où lexème et phrase peuvent contenir ou simplement être des informations sémantiques choisies par qui réalise le compilateur.

Valeurs sémantiques dans OcamlLex

Voyons d'abord le cas de l'analyseur lexical.
Dans la définition de l'analyseur pour OcamlLex, on a déjà vu qu'il y a une partie action qui est exécutée dés qu'un lexème est reconnu

{ prologue }
let ident = regexp ...
rule etatinitial =
  parse regexp { action }
      | ...
and ...
{ epilogue }

Un exemple: le lexeur pour une calculette

Dans cet exemple, on retournera des tokens pouvant contenir des valeurs sémantiques, comme le int dans INT of int:

( File CalcLex.mll )
{type token = INT of int | LPAREN | RPAREN | PLUS | MINUS | TIMES | DIV | EOL;;
 exception Eof;;
 let print_token = function  . . . }

rule token = parse
[' ' '']     { token lexbuf }     ( skip blanks )
| ['  n' ]        { EOL }
| ['0'-'9']+     { INT(int_of_string(Lexing.lexeme lexbuf)) }
| '+'            { PLUS }
| '-'            { MINUS }
| ''            { TIMES }
| '/'            { DIV }
| '('            { LPAREN }
| ')'            { RPAREN }
| eof            { raise Eof }

{ let _ = try
    let lexbuf = Lexing.from_channel stdin in
        while true do print_token (token lexbuf); done
  with Eof -> print_newline(); exit 0 }
  

%{
%}
%token INT
%token EOF PLUS
%start s
%type  s
%%
s:  e EOF       { $1 };
e:     e PLUS t { $1 + $3 }
     | t        { $1 };
t:  INT         { $1 };
%%

( 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 (attention aux tabulations!!!)

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 calc

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) $<

Grammaires attribuées

Le fichier d'entrée pour OcamlYacc que l'on vient de voir est un cas particulier de ce que l'on appelle une grammaire attribuée.

• arbre de syntaxe concrète
• attributs synthétisés et hérités
• ordre de calcul
• pourquoi synthèse et LR font bon ménage

Grammaires attribuées, exemple classique

La grammaire attribuée suivante montre des attributs hérités (typeh) et synthétisés (types, vallex)

Voyons l'exemple float a,b,c que OcamlLex transforme en

avec les bonnes valeurs synthétisées pour les terminaux ID.
N.B.: on peut toujours se passer d'attributs hérités... Comment fairiez-vous dans cet exemple?

Positions dans le flot d'entrée

Il est important, dans un compilateur réaliste, de pouvoir signaler des erreurs à l'utilisateur avec une certain degré de précision. Pour cela il est important dans les valeurs sémantiques de maintenir:

• la position initiale et finale dans le flot des caractères ayant donné origine à un terminal
  
• la position initiale et finale dans le flot des caractères ayant donné origine à un non terminal
  

Valeurs sémantiques en analyse LL

On a vu que l'analyse LL est plus simple à mettre en oeuvre, au point que l'on peut construire les analyseurs à la main. Mais cela vient à un coût: le traitement des valeurs sémantiques est moins naturel, parce que l'on travaille avec des grammaires fort peu naturelles.

Revoyons l'exemple simple de tout à l'heure, mais en version LL.
La grammaire (annotée avec les actions)

n'est pas LL, parce que ell'est recursive à gauche.

Valeurs sémantiques en analyse LL (suite)

Il faut derecursiviser (en passant, on élimine le symbole T qui est redondant)

Valeurs sémantiques en analyse LL (suite)

Voici l'analyseur LL que l'on avait construit pour cette grammaire, quand on ne s'intéressait pas aux valeurs sémantiques:

exception Parse_Error;;
type token = Int | PLUS | Eof;;
let descente gettoken = . . .
 let rec ntS () = (ntE(); check(Eof))
 and ntE () = match !tok with  Int -> (eat(Int); ntE'())
                         |  _   -> raise Parse_Error
 and ntE' () = match !tok with PLUS -> (eat(PLUS);eat(Int); ntE'())
                         |  _      -> () ( transition vide )
in ntS();;

( un lexeur bidon vite fait )
let gettoken_of l = let data = ref l in
    let f () = let t = List.hd !data in data:= List.tl !data; t in f;;

descente (gettoken_of [Int;PLUS;Int;PLUS;Int;Eof]);;

Valeurs sémantiques en analyse LL (suite)

Voyons les valeurs dans le cas simple:

exception Parse_Error;;
type token = Int of int| PLUS | Eof;;
let descente gettoken = . . .
 let rec ntS () = (let e = ntE() in (check(Eof);e))
 and ntE () = match !tok with  Int(n) -> (advance(); ntE'())
                         |  _   -> raise Parse_Error
 and ntE'(v) = match !tok with PLUS -> (eat(PLUS); ???)
                         |  _      -> (???) ( transition vide )
in ntS();;

( un lexeur bidon vite fait )
let gettoken_of l = let data = ref l in
    let f () = let t = List.hd !data in data:= List.tl !data; t in f;;

descente (gettoken_of [Int(3);PLUS;Int(2);PLUS;Int;Eof]);;

Valeurs sémantiques en analyse LL (suite)

Voyons les valeurs dans les cas complexes:

exception Parse_Error;;
type token = Int of int| PLUS | Eof;;
let descente gettoken = . . .
 let rec ntS () = (let e = ntE() in (check(Eof);e))
 and ntE () = match !tok with  Int(n) -> (advance(); ntE'(n))
                         |  _   -> raise Parse_Error
 and ntE'(v) = match !tok with PLUS -> (eat(PLUS);
                                        match !tok with
                                            Int(n) -> advance(); ntE'(v+n)
                                        |  _       -> raise Parse_Error
                                       )
                         |  _      -> (v) ( transition vide )
in ntS();;

( un lexeur bidon vite fait )
let gettoken_of l = let data = ref l in
    let f () = let t = List.hd !data in data:= List.tl !data; t in f;;

descente (gettoken_of [Int(3);PLUS;Int(2);PLUS;Int;Eof]);;

Valeurs sémantiques dans LL (fin)

La morale de cet exemple est que LL est très mal adapté à l'analyse avec valeurs sémantiques de grammaires qui sont naturellement recursives à gauche: on est obligé de transformer les actions pour les adapter aux grammaires derecursivés, ce qui fait perdre de naturalité à l'analyseur, contrairement à ce qui se passe dans le cas LR.

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 Cours07.tex.

The translation was initiated by Roberto Di Cosmo on Wed Nov 24 08:49:13 MET 1999

...grammaire

Ici on utilise les X pour indiquer des symboles terminaux ou non terminaux