Chapitre 6

type arbre =
| Feuille of char 
| Noeud of char * arbre * arbre;;

let f = " (a + a * a ) ";;
let i = ref 0;;

let rec expression () =
  let a = terme () in
  if f.[!i] = `+` then begin
   incr i;
   Noeud (`+`, a, expression ()) end
  else a

and terme () =
  let a = facteur () in
  if f.[!i] = `*` then begin
   incr i;
   Noeud (`*`, a, terme ()) end
  else a

and facteur () =
  if f.[!i] = `(` then begin
   incr i;
   let a = expression () in
   if f.[!i] = `)` then begin
    incr i;
    a end
   else erreur (i) end
  else
  if f.[!i] = `à
  then begin
   incr i;
   Feuille `à end 
  else erreur (i);;

(* Prédicat définissant les non-terminaux *)
let auxiliaire y = ... ;;

(* règle.(s).(i) est la ième règle
   dont le membre gauche est s *)
let règle =
  [|  [| s00; s01; ... |];
      [| s10; s11; ... |];
      [| si0; si1; ... |];
  ... |];;

(* nbrègle.(s) est le nombre de règles
   dont le membre gauche est s *)
let nbrègle = [| s0; ...; sn |];;

(* Fonction auxiliaire sur les chaînes
   de caractères: remplacer s pos char
   renvoit une copie de la chaîne s
   avec char en position pos *)
let remplacer s pos char =
 let s1 = make_string (string_length s) ` ` in
 blit_string s 0 s1 0 (string_length s);
 s1.[pos] <- char;
 s1;;

let analyse_récursive f u =
 let b = ref false in
 let pos = ref 0 in
 while f.[!pos] = u.[!pos] do incr pos done;
 if f[!pos] = `$` && u.[!pos] = `#`
 then begin
  print_string "analyse réussie \n";
  true end
 else
   let y = u.[!pos] in
   if auxiliaire y
   then begin
    let i = ref 0 in
    let ynum = int_of_char y - int_of_char `À in
    while not !b && !i <= nbrègle.(ynum) do
     b := analyse_récursive
           (remplacer (u, !pos, règle.(ynum).(!i)), f);
     if !b
     then printf "règle %d du non-terminal %c \n" !i y
     else incr i
    done;
    !b end
   else false;;

(* {\em Analyse LL(1), voir page \pageref{prog:ll1}} *)
let rec arbre_synt_pref () =
  if f.[!pos] = `à
  then begin
    incr pos;
    Feuille `à end
  else
  if f.[!pos] = `(`
  && f.[!pos + 1] = `+`
  || f.[!pos + 1] = `*`
  then begin
    let x = f.[!pos + 1] in
    pos := !pos + 2;
    let a = arbre_synt_pref () in
    let b = arbre_synt_pref () in
    if f.[!pos] = `)`
    then Noeud (x, a, b)
    else erreur (!pos) end
  else erreur(!pos);;

(* {\em Évaluation, voir page \pageref{prog:evaluation}} *)
type expression =
| Constante of int
| Opération of char * expression * expression;;

let rec évaluer = function
| Constante i -> i
| Opération ('+', e1, e2) -> évaluer e1 + évaluer e2
| Opération ('*', e1, e2) -> évaluer e1 * évaluer e2;;