Arbre de syntaxe abstraite, Tables des symboles

Arbre de syntaxe abstraite: definition et exemples
Syntaxe abstraite en Ocaml
Syntaxe abstraite pour CTigre
Ce qui nous reste à faire: aperçu et espace de conception

Syntaxe abstraite

Une fois reconnue une phrase (ou programme) du langage, il est nécéssaire de la transformer en une forme adapté aux phases successives du compilateur, qui vont explorer à plusieur reprises cette representation pour verifier le typage, construire les tables des symboles, calculer la duree de vie des variables, et bien d'autres attributs.

L'arbre de derivation syntaxique associé à la grammaire utilisée pour l'analyse n'est pas bien adapté, parce qu'il contient un grand nombre de noeuds internes (les non-terminaux de la grammaire), qui n'ont aucun intérêt lors de la visite de la structure.

Syntaxe abstraite

Exemple: la phrase (1+2)34, avec la grammaire (ambiguë)

<!-- MATH: \begin{displaymath} \begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c@{\quad}c@{\qquad\rightarrow\qquad}l} & S & E\; \$ & & E & E * E \ & E & E + E & & E & (E) \ & E & int \end{array}

\end{displaymath} -->

$\begin{displaymath}\begin{array}{c@{\quad}c@{\qquad\rightarrow\qquad}l@{\qquad}c... ...E * E \\ & E & E + E & & E & (E) \\ & E & int \end{array}\end{displaymath}$

a comme arbre syntaxique

$\begin{displaymath}\includegraphics[height=12em]{concrete.ps}\end{displaymath}$

Syntaxe abstraite

Définition: un arbre de syntaxe abstraite est un arbre dont les noeuds internes contiennent des opérateurs de construction du langage, et non pas des non-terminaux.

Notamment, dans un arbre de syntaxe abstraite, construit à parti d'un arbre syntaxique, on n'a pas besoin de faire un effort pour rendre clair le parenthesage, vu qu'on le connaît deéjà grâce à l'arbre syntaxique. De même, tous les terminaux de la syntaxe concrète (comme les virgules, les points virgules, les guillemets, les mots clefs etc.) qui ont pour but de signaler des constructions particulières, n'on plus besoin d'apparaître.

Syntaxe abstraite

La définition est un peu floue, mais on peut mieux comprendre en regardant un exemple pour la grammaire de tout à l'heure.
L'arbre syntaxique est très redondant: notamment la seule chose qui nous interesse dans un noeud E(E₁,+,E₂) est l'opérateur + et ses deux fils E₁ et E₂, donc on peut confondre les noeud E et +. De même, on peut oublier les parenthèses et le $.

$\begin{displaymath}\includegraphics[height=10em]{concreteabs0.ps}\end{displaymath}$

Syntaxe abstraite

Ce qui donne

$\begin{displaymath}\includegraphics[height=10em]{concreteabs1.ps}\end{displaymath}$

Mais ici, les symboles non terminaux E et S n'ont plus aucun intérêt, et on peut les faire disparaître...

Syntaxe abstraite

Pour arriver enfin à

$\begin{displaymath}\includegraphics[height=10em]{concreteabs2.ps}\end{displaymath}$

qui est un possible arbre de syntaxe abstraite pour l'expression originaire...

Syntaxe abstraite et Ocaml

Les constructeurs de types disponibles dans le langage Ocaml sont très adaptés à la réalisation et manipulation des arbres de syntaxe abstraite.
Voici une possible définition en Ocaml des arbres de syntaxe abstraite obtenus plus haut pour cette grammaire

type exp_ast = Int of int
             | Add of exp_ast * exp_ast
             | Mult of exp_ast * exp_ast ;;

Le fait que chaque constructeur de type somme est immediatement disponible au programmeur permet d'exprimer très simplement l'arbre de syntaxe abstraite pour la phrase (1+2)34:

let ast = Mult(Mult(Add(Int(1),Int(2)),Int(3)),Int(4))

Syntaxe abstraite: un exemple complet

Voyons maintenant comment la calculette d'exemple de la dernière fois peut être réalisée en deux phases distinctes, plus modulaires

construction de l'ast: on retourne comme valeur sémantique un objet exp_ast
evaluation de l'ast: on parcours l'arbre en procédant à l'évaluation (cela permet par exemple de calculer avec associativité droite des opérateurs définis par commodité comme associtifs à gauche dans la gramamire).

Syntaxe abstraite: un exemple complet (I)

Le lexeur ne change pas

( 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 }

Syntaxe abstraite: un exemple complet (II)
Mais il nous faut maintenant definir un type pour l'arbre de syntaxe abstraite...

( File ast.ml )
type exp_ast =
         Int of int
       | Add of exp_ast * exp_ast
       | Sub of exp_ast * exp_ast
       | Mult of exp_ast * exp_ast
       | Div of exp_ast * exp_ast
;;

Syntaxe abstraite: un exemple complet (III)

Le parseur construit l'arbre de syntaxe abstraite ...

%{ open Ast;; %} / 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 <Ast.exp_ast> main
%%
main:  expr EOL                 { $1 };
expr: INT                       { Int($1) }
      | LPAREN expr RPAREN      { $2 }
      | expr PLUS expr          { Add($1,$3) }
      | expr MINUS expr         { Sub($1,$3) }
      | expr TIMES expr         { Mult($1,$3) }
      | expr DIV expr           { Div($1,$3) }
      | MINUS expr %prec UMINUS { Sub(Int(0),$2) };

Remarques OcamlYacc

Remarque: on n'est pas obligé de donner le type de expr. En effet, grâce à l'inférence des types de Ocaml, une fois connus les types rendus par les non terminaux de départ, tous les autres types peuvent être déduits par le compilateur.
C'est un avantage significatif par rapport à ce que l'on doit faire en Yacc ou Bison.

Remarque: dans la directive %token, on doit indiquer le type avec le nom complet (ici Ast.exp_ast), et cela même sin on a mis la bonne directive open Ast dans l'en-tête OcamlYacc.

En effet, l'en tête n'est copié que dans le fichier parser.ml, alors que les déclarations produites à partir des directives %token sont copiés à la fois dans parser.ml et dans parser.mli.

Syntaxe abstraite: un exemple complet (IV)

Le fichier principal change: d'abord on calcule l'ast, ensuite on l'évalue

 ( File calc.ml )
let rec eval = function
    Int(n) -> n
      | Add(e1,e2) -> (eval e1)+(eval e2)
      | Sub(e1,e2) -> (eval e1)-(eval e2)
      | Mult(e1,e2) -> (eval e1)*(eval e2)
      | Div(e1,e2) -> (eval e1)/(eval e2);;

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

Syntaxe abstraite: un exemple complet (fin)

Le fichier Makefile (attention aux tabulations!!!)

CAMLC=ocamlc
CAMLLEX=ocamllex
CAMLYACC=ocamlyacc

calc: ast.cmo parser.cmi parser.cmo lexer.cmo calc.cmo
                ocamlc -o calc lexer.cmo ast.cmo parser.cmo calc.cmo
clean:
        rm *.cmo *.cmi calc
# generic rules :
#################
.SUFFIXES: .mll .mly .mli .ml .cmi .cmo .cmx
.mll.mli:
        $(CAMLLEX) $<
.mll.ml:
        $(CAMLLEX) $<
.mly.mli:
        $(CAMLYACC) $<
.mly.ml:
        $(CAMLYACC) $<
.mli.cmi:
        $(CAMLC) -c $(FLAGS) $<
.ml.cmo:
        $(CAMLC) -c $(FLAGS) $<

Detour: utilisation dans le toplevel Ocaml

Après la compilation, lancez Ocaml, puis tapez



load "ast.cmo";;

load "parser.cmo";;

load "lexer.cmo";;

open Ast;;

Cela a pour effet de charger dans l'interpreteur les modules compilés ast.cmo, parser.cmo et lexer.cmo (l'ordre est important: dans ce cas, c'est le seul ordre qui ne viole pas les dependences entre modules)

Detour: utilisation dans le toplevel Ocaml

Maintenant on peut écrire:

let rec eval = function
    Int(n) -> n
      | Add(e1,e2) -> (eval e1)+(eval e2)
      | Sub(e1,e2) -> (eval e1)-(eval e2)
      | Mult(e1,e2) -> (eval e1)*(eval e2)
      | Div(e1,e2) -> (eval e1)/(eval e2);;

let parse_line () =
 try
  let lexbuf = Lexing.from_channel stdin in
  let ast = Parser.main Lexer.token lexbuf
  in ast
 with Lexer.Eof -> failwith "Fin de fichier inattendue";;

Detour: utilisation dans le toplevel Ocaml

On peut obtenir le même résultat en créant un fichier chargetout.ml

( fichier chargetout.ml )

load "ast.cmo";;

load "parser.cmo";;

load "lexer.cmo";;

open Ast;;
let rec eval = function
    Int(n) -> n
      | Add(e1,e2) -> (eval e1)+(eval e2)
      | Sub(e1,e2) -> (eval e1)-(eval e2)
      | Mult(e1,e2) -> (eval e1)*(eval e2)
      | Div(e1,e2) -> (eval e1)/(eval e2);;
let parse_line () =
 try let lexbuf = Lexing.from_channel stdin in
     let ast = Parser.main Lexer.token lexbuf in ast
 with Lexer.Eof -> failwith "Fin de fichier inattendue";;

Detour: utilisation dans le toplevel Ocaml

Et ensuite, on lance le toplevel Ocaml et on charge le fichier chargetout.ml avec la directive #use :

[dicosmo@localhost]$ ocaml
        Objective Caml version 2.02

#use "chargetout.ml";;

val eval : Ast.exp_ast -> int = <fun>
val parse_line : unit -> Ast.exp_ast = <fun>

Detour: utilisation dans le toplevel Ocaml

Et là, on peut visualiser directement les arbres de syntaxe abstraite:



let a=parse_line();;

1+(2-3)*4/(5--6)
val a : Ast.exp_ast =
  Add
   (Int 1,
    Div (Mult (Sub (Int 2, Int 3), Int 4),
         Sub (Int 5, Sub (Int 0, Int 6))))

eval a;;


: int = 1
#

Detour: utilisation dans le toplevel Ocaml

Dans votre projet, vous aurez probablement besoin d'une variante comme la suivante:

let parse_file fn =
try
let ic = (open_in fn) in
let lexbuf = Lexing.from_channel ic in
let ast = Parser.programme Lexer.token lexbuf
in (close_in ic); ast
with Lexer.Eof -> failwith "Fin de fichier inattendue"
;;

La syntaxe abstraite de CTigre: I

Pour la réalisation du projet, il vous faut définir une syntaxe abstraite pour le langage CTigre. Comme on souhaite garder trace des positions dans le fichier source, on disposera d'un module adapté dont voici une esquisse...

module Location =
struct
type t = int * int
let pos() = (Parsing.symbol_start(),Parsing.symbol_end())
let npos n = (Parsing.rhs_start(n),Parsing.rhs_end(n))
let dummy = (-1,-1) ( par exemple pour le 0 dans )
                    ( la conversion -i vers 0-i  )
end

La syntaxe abstraite de CTigre: II

On aura aussi bésoin de gèrer des tables de symboles, ce qui sera fait dans un module que l'on étoffera et explorera plus en détail dans le prochain cours.

module Symbol =
  struct
    type symbol = string
    let symbol n = n
    let name s = s
  end

La syntaxe abstraite de CTigre: III

On trouvera dans la définition de la syntaxe abstraite les différentes composantes du langage:
1) types

module Absyn =
  struct
    type symbol = Symbol.symbol
    type core_type =
        { typ_desc: core_type_desc;
          typ_loc: Location.t}
    and  core_type_desc =
         Typ_name of symbol
      |  Typ_arrow of core_type * core_type
      |  Typ_array of core_type
      |  Typ_record of field list
    and  type_dec = (symbol * core_type)

La syntaxe abstraite de CTigre: IV

On trouvera dans la définition de la syntaxe abstraite les différentes composantes du langage:
2) expressions

    and exp = { exp_desc: exp_desc; exp_loc: Location.t}
    and forexp = {var: symbol; lo: exp; hi: exp; dir: direction_flag; for_body: exp}
    and direction_flag = Up | Down
    and arrayexp = {a_typ: symbol; size: exp; a_init: exp}
    and var = SimpleVar of symbol | FieldVar of var * symbol
            | SubscriptVar of var * exp
    and  exp_desc = VarExp of var | NilExp | IntExp of int | StringExp of string
      | Apply of symbol * exp list | RecordExp of (symbol * exp) list * symbol
      | SeqExp of exp * exp | IfExp of exp * exp * exp option
      | WhileExp of exp * exp | ForExp of forexp
      | LetExp of dec list * exp | TypeExp of type_dec list * exp
      | ArrayExp of arrayexp | Opexp of oper * exp * exp
      | AssignExp of var * exp
    and oper = PlusOp | MinusOp | TimesOp | DivideOp
         | EqOp | NeqOp | LtOp | LeOp | GtOp | GeOp

La syntaxe abstraite de CTigre: V

3) déclarations

    and dec =
        FunDec of fundec list
      | VarDec of vardec list
      | TypeDec of type_dec list
    and field = {f_name: symbol;
             typ: core_type;
             f_loc: Location.t}
    and   fundec = {fun_name: symbol;
                params: field list;
                result: core_type option;
                body: exp;
                fun_loc: Location.t}
    and vardec = {v_name: symbol;
                  var_typ: core_type option;
                  init: exp; var_pos: Location.t}
end

Où on en est

$\begin{displaymath}\spreaddiagramcolumns{4em} \spreaddiagramrows{4em} \objectmar... ...ackrel{Actions}{\mbox{s\'emantiques}}}\rto^{AST} & \enddiagram \end{displaymath}$

Où on va

$\begin{displaymath}\spreaddiagramcolumns{2em} \spreaddiagramrows{4em} \objectmar... ...{}}\rto & \framed<5pt>{Traduction}\rto<sup>.7</sup>{IR} & \enddiagram \end{displaymath}$

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

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

The translation was initiated by Roberto Di Cosmo on 2001-01-07

Roberto Di Cosmo
2001-01-07