Analyses lexicales

Exercices 1 et 2 : expressions régulières - des outils

• Str en O'Caml,
• regexp en Java
• regex en C

# let french_date_of d =
  match d with
   [mm; jj; yy] -> jj^"/"^mm^"/"^yy
  | _ -> failwith "Bad date format" ;;
val french_date_of : string list -> string = <fun>

# let english_date_format = Str.regexp "[0-9]+\.[0-9]+\.[0-9]+" ;;
val english_date_format : Str.regexp = <abstr>

# let trans_date l = 
  try
   let i=Str.search_forward english_date_format l 0 in
   let d1 = Str.matched_string l in
   let d2 = french_date_of (Str.split (Str.regexp "\.") d1) in
     Str.global_replace english_date_format d2 l
  with Not_found -> l ;;
val trans_date : string -> string = <fun>

# trans_date "..............06.13.99............" ;;
- : string = "..............13/06/99............"

Exercice 3 : outils(ocamllex/lex/flex)

 {
   entête  -  expression caml  -  même chose qu'en ocamlyacc
 }

 rule    point-d'entrée   =
   parse  expression-régulière  {  action  }
    | ...
    | expression-régulière  {  action  }
 and    point-d'entrée   =
   parse ...
 and ...
 ;;

Exercice 4 : outils (Genlex)

type token =
    Kwd of string
  | Ident of string
  | Int of int
  | Float of float
  | String of string
  | Char of char ;;

Genlex.make_lexer ;;
- : string list -> char Stream.t -> Genlex.token Stream.t = <fun>

let keywords =
  [ "REM"; "GOTO"; "LET"; "PRINT"; "INPUT"; "IF"; "THEN";
    "-"; "!"; "+"; "-"; "*"; "/"; "%"; 
    "="; "<"; ">"; "<="; ">="; "<>";
    "&"; "|" ] ;;

# let line_lexer l = Genlex.make_lexer keywords (Stream.of_string l) ;;
val line_lexer : string -> Genlex.token Stream.t = <fun>
# line_lexer "LET x = x + y * 3" ;;
- : Genlex.token Stream.t = <abstr>

# let rec spaces s =
   match s with parser
     [<'' '  ; rest  >] -> spaces rest
   | [<''\t' ; rest  >] -> spaces rest
   | [<''\n' ; rest  >] -> spaces rest
   | [<>] -> ();;
val spaces : char Stream.t -> unit = <fun>
# let rec lexer s =
   spaces s;
   match s with parser
     [< ''('  >] -> [< 'Lsymbol "(" ; lexer s >]
   | [< '')'  >] -> [< 'Lsymbol ")" ; lexer s >]
   | [< ''+'  >] -> [< 'Lsymbol "+" ; lexer s >]
   | [< ''-'  >] -> [< 'Lsymbol "-" ; lexer s >]
   | [< ''*'  >] -> [< 'Lsymbol "*" ; lexer s >]
   | [< ''/'  >] -> [< 'Lsymbol "/" ; lexer s >]
   | [< ''0'..'9' as c; 
        i,v = lexint (Char.code c - Char.code('0')) >] 
       -> [<'Lint i ; lexer v>]
 and lexint r s =
   match s with parser  
     [< ''0'..'9' as c >] 
     -> let u = (Char.code c) - (Char.code '0') in  lexint (10*r + u) s
   | [<>] -> r,s
 ;;
val lexer : char Stream.t -> lexeme Stream.t = <fun>
val lexint : int -> char Stream.t -> int * char Stream.t = <fun>

Exercice 5 : suppression de commentaires

(* début du commentaire
      sur plusieurs 
         lignes *)

 let succ x = (* fonction successeur *)
   x + 1;;

(* niveau 1  texte commenté 
  let old_succ y = (* niveau 2 fonction successeur niveau 2 *)
    y +1;;
    niveau 1 *)
  succ 2;;

Analyse syntaxique descendante

Exercice 6 : mini-Basic

Spécifications BASIC_L2 niveau 1

• commandes
  

  commande	action
  QUIT	sortie du BASIC
  LOAD nom	charge un programme à partir du fichier nom
  SAVE nom	sauve un programme dans le fichier nom
  LIST	affiche le programme courant
  RUN	exécute le programme courant

  
  Un programme BASIC_L2 niveau 1 contiendra une suite de lignes numérotées et rangées en ordre croissant. Une ligne est définie par un label (son numéro) et une des instructions suivantes :
  
  
• instructions
  

  instruction	action
  REM texte	commentaire
  LET var = expr	affectation de la variable var par la valeur de expr
  PRINT e_1; e_2; ...; e_n;	affiche les valeurs des expressions e_1, ...,e_n à la suite
  PRINT	effectue un saut de ligne si la dernière expression n'est pas suivie d'un point-virgule
  INPUT var	lit au clavier une valeur qui sera affectée à var
  GOTO label	aller à l'instruction numérotée label
  IF expr GOTO label	Si l'expr est vraie aller à l'instruction numérotée label
  GOSUB label	appel de la sous-routine numérotée label
  RETURN	retourne à l'instruction suivante du dernier GOSUB rencontré
  END	fin du programme

  
  Les expressions sont arithmétiques, relationnelles et logiques.
  
  
• expressions
  

  expression
  e_1 op_arith e_2	expression arithmétique
  	*,+,/,-
  op_arith_1 e_1	-
  ( e_1 )	expression parenthésée
  e_1 op_rel e_2	expression relationnelle
  	<, =, >
  e_1 op_bool_2 _2	expression logique
  	AND, OR
  op_bool_1 e_1	NOT

  
  
  
• variables : les variables peuvent contenir des nombres (entiers ou flottants) ou bien des chaînes de caractères. On les distingue par leur nom. Une variable se terminant par un caractère $ (dollar) contiendra des chaînes de caractères.

Réécriture de la grammaire des expressions

• factorisation à gauche
• enlever la récursivité gauche

Implantation

Analyses syntaxiques ascendantes

Exercice 7 : outils (camlyacc/yacc/bison)

 %{
   (1) entête  -  expression caml
 %}

   (2) déclaration

 %%
   (3) règlei  actioni
 %%

   (4) queue  -  expression caml

e : O e e  {printf "%s " $1};

e : Constante  {printf "%u " $1}
  | Identificateur {printf "%s " $1};

%start e
%type <unit> e

        /* File parser.mly */
        %token <int> INT
        %token PLUS MINUS TIMES DIV
        %token LPAREN RPAREN
        %token 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 }
        ;

        (* 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']+ as lxm { INT(int_of_string lxm) }
          | '+'            { PLUS }
          | '-'            { MINUS }
          | '*'            { TIMES }
          | '/'            { DIV }
          | '('            { LPAREN }
          | ')'            { RPAREN }
          | eof            { raise Eof }

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

        ocamllex lexer.mll       # generates lexer.ml
        ocamlyacc parser.mly     # generates parser.ml and parser.mli
        ocamlc -c parser.mli
        ocamlc -c lexer.ml
        ocamlc -c parser.ml
        ocamlc -c calc.ml
        ocamlc -o calc lexer.cmo parser.cmo calc.cmo

Exercice 9 : instructions imbriquées (IF THEN ELSE)

• comme test le caractère T
• et comme autres instructions les caractères A.

XMLeries

Exercice 10 : étude de l'analyseur XML-light

Ce document a été traduit de L^AT_EX par H^EV^EA