Une centaine de lignes de Caml

Pour montrer l'idée de l'analyse syntaxique fonctionnelle avec flux paresseux, j'écris un analyseur syntaxique pour le type des expressions.

Avec des flux paresseux, l'analyse syntaxique se décompose en deux étapes: d'abord la construction d'un flux de lexèmes à partir d'un flux de caractères, puis l'obtention de la syntaxe abstraite à partir du flux de lexèmes.
Je définis d'abord l'analyseur lexical, en utilisant le module "genlex" de la bibliothèque standard de Caml Light. C'est très simple puisqu'il suffit de déclarer la liste des mots-clefs à la fonction make_lexer pour obtenir l'analyseur lexical.

#open "genlex";;
#let lexer = make_lexer ["let"; "="; "in"; "("; ")"; "+"; "-"; "*"; "/"];;
lexer : char stream -> token stream = <fun>

Par exemple, je crée un flux de caractères à partir d'une chaîne, puis lui applique l'analyseur lexical. Le résultat est le flux (paresseux) des lexèmes. Pour obtenir les lexèmes il faut accéder à la tête du flux des lexèmes. Dès qu'un token est obtenu, le flux est mis à jour automatiquement, c'est-à-dire que le lexème est ôté du flux. Quand le flux est vide l'exception Parse_failure se déclenche.

#let flux = lexer (stream_of_string "1x  + ");;
flux : token stream = <abstr>
#match flux with
  [< 'Int i >] -> i;;
- : int = 1
#match flux with
  [< '(Ident s as lexem); reste >] -> lexem;;
- : token = Ident "x"
#match flux with
  [< '(Kwd c as lexem); reste >] -> lexem;;
- : token = Kwd "+"
#match flux with
  [< '(Ident s as lexem); reste >] -> lexem;;
Exception non rattrapée: Parse_failure

L'analyseur syntaxique gère les précédences entre les opérateurs. Je définis donc un ``lecteur d'opérations binaires'', qui lit une suite d'opérations formée avec les opérateurs d'une liste d'opérateurs donnée en argument. (Remarquez que lire_binop utilise un argument fonctionnel lire_base pour lire les arguments de l'opération.)

#let lire_opérateur opérateurs = function
  | [< (stream_check
         (function Kwd op -> mem op opérateurs | _ -> false)) lexem >] ->
      match lexem with Kwd op -> op | _ -> failwith "lire_opérateur";;
lire_opérateur : string list -> token stream -> string = <fun>
#let lire_binop lire_base opérateurs =
 let rec lire_reste e1 = function
 | [< (lire_opérateur opérateurs) op; lire_base e2;
      (lire_reste (Binop (op, e1, e2))) e >] -> e
 | [< >] -> e1 in
 function [< lire_base e1; (lire_reste e1) e >] -> e;;
lire_binop :
 (token stream -> expression) -> string list -> token stream -> expression =
 <fun>

L'analyseur syntaxique est une collection de fonctions qui font une analyse similaire à la descente récursive: les précédences sont prises en compte par la stratification des fonctions d'analyse.

#let rec basique = function
  | [< 'Ident s >] -> Var s
  | [< 'Int i >] -> Num i
  | [< 'Kwd "("; expr e; 'Kwd ")" >] -> e

and minus = function
  | [< 'Kwd "-"; basique e >] ->
      begin match e with
      | Num i -> Num (-i)
      | _ -> failwith "unary minus"
      end
  | [< basique e >] -> e

and multiplicative flux = lire_binop minus ["*"; "/"] flux
and additive flux = lire_binop multiplicative ["+"; "-"] flux

and expr = function
  | [< 'Kwd "let"; 'Ident x; 'Kwd "="; expr e1; 'Kwd "in"; expr e2 >] ->
       Let (x, e1, e2)
  | [< additive e >] -> e;;
basique : token stream -> expression = <fun>
minus : token stream -> expression = <fun>
multiplicative : token stream -> expression = <fun>
additive : token stream -> expression = <fun>
expr : token stream -> expression = <fun>

#let parse_expr s = expr (lexer (stream_of_string s));;
parse_expr : string -> expression = <fun>

Avec l'analyseur syntaxique, on entre facilement des expressions complexes:

#eval [] (parse_expr "let x = 2 in x * x + 3");;
- : int = 7