Dans ce TP, on va analyser syntaxiquement des expressions arithmétiques
composées de variables, d'entiers, de parenthèses et d'un des opérateurs
+ - * /.
Analyse lexicale¶
On va commencer par écrire une fonction qui convertit une chaine de caractères en une liste de caractères pour pouvoir faire du filtrage dessus.
let string_to_charlist (s:string) : char list =
(* renvoie la liste des caractères d'une chaine *)
List.of_seq (String.to_seq s)
On définit maintenant un type pour les jetons :
type token =
Id of string
| Num of int
| Plus | Times | Minus | Div
| LPar | RPar
La fonction suivante décide si un caractère est une lettre
minuscule ou majuscule dans abc...z ou ABC...Z.
let is_alpha c =
match c with
|'a'..'z' | 'A'..'Z' -> true
| _ -> false
La fonction suivante décide si un caractère est un chiffre de 0 à 9.
let is_digit c =
match c with
| '0'..'9' -> true
| _ -> false
On considère maintenant une liste de caractères l et la fonction
suivante renvoie un couple (l1,l2) tel que :
l1est le plus grand préfixe delqui satisfait l'expression régulière0|[1-9][0-9]*, ce qui interdit les zéros non significatifs tout en acceptant la constante0.l1 @ l2 = l
S'il n'y a pas de préfixe numérique valide, on va donc renvoyer
([],l).
let extract_num s =
let rec aux s =
match s with
| ('0'..'9' as c)::q ->
let i, s' = aux q in
(c::i, s')
| _ -> [], s
in match s with
| '0'::q -> (['0'], q)
| ('1'..'9' as c)::q ->
let i, s' = aux q in
(c::i, s')
| _ -> [], s
Remarque
Sur 012, le plus grand préfixe valide est 0 : le lexer produit alors les
jetons Num 0 puis Num 12, et c'est l'analyse syntaxique qui rejettera
l'expression. Comme tout chiffre commence un préfixe valide, extract_num
ne renvoie jamais [] dans lexer ; le test x = [] y est conservé par
prudence.
La fonction suivante procède comme la précédente mais avec un
préfixe satisfaisant l'expression régulière [a-zA-Z][a-zA-Z0-9_]*.
let extract_ident s =
let rec extract_aux s =
match s with
| c::q when is_digit c || is_alpha c || c = '_' ->
let i, s' = extract_aux q in
(c::i, s')
| _ -> [], s
in
match s with
| c::_ when is_alpha c ->
extract_aux s
| _ -> [], s
La fonction lexer convertit une liste de caractères en une liste
de tokens. Si jamais on ne peut pas produire de tokens, on produit
l'exception LexingError.
Cette fonction est naturellement récursive, on va ignorer tous les
caractères ' '. Ici, il s'agit simplement d'avoir une règle
| ' '::q -> lexer q
exception LexingError
let rec lexer s =
match s with
| [] -> []
| ' '::q -> lexer q
| '('::q -> LPar :: lexer q
| ')'::q -> RPar :: lexer q
| '+'::q -> Plus :: lexer q
| '-'::q -> Minus :: lexer q
| '*'::q -> Times :: lexer q
| '/'::q -> Div :: lexer q
| x :: _ when is_digit x ->
let x, q = extract_num s in
if x = []
then raise LexingError
else Num (int_of_string
(String.concat "" (List.map (String.make 1) x)))
:: lexer q
| _ ->
let x, q = extract_ident s in
if x = []
then raise LexingError
else let x = String.concat "" (List.map (String.make 1) x) in
Id x :: lexer q
Premier analyseur syntaxique¶
On considère maintenant que l'entrée est une liste de tokens
obtenue par un appel valide à lexer.
On va considérer un premier langage d'expression qui correspond à la grammaire :
T = + num
NT = expr
s = expr
expr -> num | num + expr
Le langage contient donc des expressions comme 1 + 33 + 23 ou 12.
Une telle expression se représente naturellement par la liste des
entiers. Donc pour l'exemple [1;33;23] ou [12].
On va écrire une fonction qui produit cette liste :
exception ParsingError
let rec parser1 (tl:token list) : int list =
match tl with
| [Num n] -> [n]
| Num n :: Plus :: q -> n :: parser1 q
| _ -> raise ParsingError
Deuxième analyseur syntaxique¶
On considère maintenant un type arborescent expression complet :
type expression =
Variable of string
| Constant of int
| Add of expression * expression
| Substract of expression * expression
| Mult of expression * expression
| Divide of expression * expression
Les analyseurs syntaxiques vont ainsi essayer de reconstruire un arbre.
On commence avec une grammaire assez simple :
T = ( ) + / - * id num
NT = expr operand
s = expr
expr -> operand
| operand + operand
| operand - operand
| operand * operand
| operand / operand
operand -> id | num | ( expr )
Pour réaliser cet analyseur, on vous conseille d'avoir deux fonctions
auxiliaires récursives parse_operand et parse_expression
qui vont prendre une liste de token et renvoyer un couple (e, q)
où e est l'expression lue et q les tokens non utilisés.
Vu la dernière production, ces fonctions sont nécessairement mutuellement récursives.
À la fin, il faudra s'assurer qu'on a utilisé tous les tokens.
let parser2 (tl:token list) : expression =
let rec parse_operand tl =
match tl with
| Id x :: q -> (Variable x, q)
| Num n :: q -> (Constant n, q)
| LPar :: q ->
begin
match parse_expression q with
| e, RPar::q -> (e,q)
| _ -> raise ParsingError
end
| _ -> raise ParsingError
and parse_expression tl =
let op1, q = parse_operand tl in
match q with
| Plus::q -> let op2, q = parse_operand q in (Add(op1, op2), q)
| Times::q -> let op2, q = parse_operand q in (Mult(op1, op2), q)
| Minus::q -> let op2, q = parse_operand q in (Substract(op1, op2), q)
| Div::q -> let op2, q = parse_operand q in (Divide(op1, op2), q)
| _ -> (op1, q)
in
let e, q = parse_expression tl in
if q <> []
then raise ParsingError;
e
La grammaire complète¶
On rappelle la grammaire complète vue en cours qui gère la précédence entre opérateurs sans parenthèses :
T = ( ) + / - * id num
NT = expr term factor
s = expr
expr -> term + expr | term - expr | term
term -> factor * term | factor / term | factor
factor -> id | num | ( expr )
let parser tl =
let rec parse_factor tl =
match tl with
| Id x :: q -> (Variable x, q)
| Num n :: q -> (Constant n, q)
| LPar :: q ->
begin
match parse_expression q with
| e, RPar::q -> (e,q)
| _ -> raise ParsingError
end
| _ -> raise ParsingError
and parse_term tl =
match parse_factor tl with
| (f, Times :: q) ->
let t, q = parse_term q in
Mult(f, t), q
| (f, Div :: q) ->
let t, q = parse_term q in
Divide(f, t), q
| (f, q) -> (f, q)
and parse_expression tl =
match parse_term tl with
| (t, Plus :: q) ->
let e, q = parse_expression q in
Add(t, e), q
| (t, Minus :: q) ->
let e, q = parse_expression q in
Substract(t, e), q
| (t, q) -> (t, q)
in
let e, q = parse_expression tl in
if q <> []
then raise ParsingError;
e
Remarque
Avec cette grammaire, les opérateurs sont associatifs à droite :
8 - 2 - 1 est analysé comme 8 - (2 - 1), ce qui ne correspond pas à la
convention usuelle pour - et /. Pour obtenir l'associativité à gauche
sans grammaire récursive à gauche (qu'une descente récursive ne sait pas
traiter), on peut lire une suite term op term op ... term avec une boucle
(ou une fonction auxiliaire à accumulateur) qui construit l'arbre de gauche
à droite.
Et ensuite ?¶
Si vous êtes ici, vous n'avez pas vraiment besoin d'être guidé. Voici ce qu'on peut faire ensuite :
- rajouter des productions et modifier l'analyseur pour gérer le
-unaire comme dans-(1+3) - écrire une fonction d'évaluation d'expression prenant en entrée une
Hashtbldonnant la valeur numérique des variables (on parle d'environnement) - rajouter la définition de variables locales avec
let ... indans la syntaxe et dans l'évaluation d'expressions. - implémenter le successeur de
OCamlet écrire un compilateur vers l'assembleurx86_64.