TD - Analyse descendante

Dans ce TD, on construit un analyseur LL(1). On se donne les types Caml suivants pour définir la notion de grammaire.

type terminal = string

type non_terminal = string

type symbol =
  | Terminal of terminal
  | NonTerminal of non_terminal

type production = symbol list

type rule = non_terminal * production

type grammar = {
  start : non_terminal;
  rules : rule list;
}

Par la suite, on suppose toujours que tous les non-terminaux sont accessibles et productifs. On suppose d'autre part qu'au symbole de départ S' est associé une unique règle de la forme S' -> S# où # est un symbole terminal n'apparaissant pas dans les autres règles de la grammaire. Ainsi, l'exemple donné en cours

     E  ->  T E'
     E' ->  + T E'
         |  epsilon
     T  ->  F T'
     T' ->  * F T'
         |  epsilon
     F  -> ( E )
         | int

sera représenté par la valeur OCaml :

let g_arith =
  { start = "S'";
    rules = [ "S'", [ NonTerminal "E"; Terminal "#" ];
              "E",  [ NonTerminal "T"; NonTerminal "E'"; ];
              "E'", [ Terminal "+"; NonTerminal "T"; NonTerminal "E'"; ];
              "E'", [ ];
              "T",  [ NonTerminal "F"; NonTerminal "T'"; ];
              "T'", [ Terminal "*"; NonTerminal "F"; NonTerminal "T'"; ];
              "T'", [ ];
              "F",  [ Terminal "("; NonTerminal "E"; Terminal ")"; ];
              "F",  [ Terminal "int" ]; ] }

Calcul de point fixe

Afin de faciliter les calculs de point fixes dans les questions suivantes, écrire une fonction

val fixpoint : ('a -> 'a * bool) -> 'a -> 'a

telle que fixpoint f x itère la fonction f à partir de la valeur x tant que le booléen renvoyé par f vaut true.

Calcul des nuls

On se donne le module Caml suivant pour représenter des ensembles de non-terminaux :

module Ntset = Set.Make(String)
type nulls = Ntset.t

Écrire une fonction is_null_production qui, étant donné l'ensemble des non-terminaux qui peuvent se dériver en le mot vide, détermine si un mot peut se dériver en le mot vide.

val is_null_production : nulls -> symbol list -> bool

(C'est la fonction NULL(α) du cours.) On pourra utiliser List.for_all.

En déduire une fonction null : grammar -> nulls qui calcule l'ensemble des non-terminaux nuls d'une grammaire donnée. On utilisera la fonction fixpoint de la manière suivante :

let null g =
  let step nulls =
    ...on calcule le nouvel ensemble nulls et
       on indique par un booléen s'il y a eu changement...
  in
  fixpoint step Ntset.empty

Note : il est bien entendu possible d'utiliser Ntset.equal pour déterminer si l'ensemble nulls a changé, mais il est également possible d'être plus fin en utilisant is_null_production uniquement sur les règles dont le membre gauche n'est pas encore dans nulls et en détectant dans ce cas si nulls doit être modifié.

Calcul des premiers

On se donne les modules Caml suivants pour représenter des ensembles de terminaux (Tset) et des dictionnaires indexés par des non-terminaux (Ntmap) :

module Ntmap = Map.Make(String)
module Tset = Set.Make(String)

Les ensembles de premiers que nous allons calculer dans cette question auront donc le type suivant :

type firsts = Tset.t Ntmap.t

c'est-à-dire un dictionnaire qui associe à chaque symbole non-terminal un ensemble de symboles terminaux.

Écrire une fonction val empty_map : grammar -> Tset.t Ntmap.t qui construit un dictionnaire associant à chaque non-terminal de la grammaire un ensemble vide de non-terminaux.

Écrire une fonction

val first_production_step : nulls -> firsts -> symbol list -> Tset.t

qui calcule l'ensemble des premiers d'une production, étant donnés l'ensemble des non-terminaux nuls et un dictionnaire pour les premiers de chaque non-terminal. (C'est la fonction FIRST(α) du cours.)

En déduire une fonction val first : grammar -> nulls -> firsts qui calcule l'ensemble des premiers des non-terminaux d'une grammaire, étant donné l'ensemble des non-terminaux nuls de cette grammaire (ce dernier étant passé en argument pour éviter d'être recalculé plusieurs fois). On utilisera la fonction fixpoint et on déterminera si l'ensemble des premiers est modifié en utilisant la fonction Tset.subset qui détermine l'inclusion ensembliste.

Calcul des suivants

Enfin, on va calculer les suivants de la grammaire. L'ensemble des suivants est représenté par le même type Caml que celui des premiers :

type follows = Tset.t Ntmap.t

Écrire une fonction

val follow : grammar -> nulls -> firsts -> follows

qui calcule les suivants d'une grammaire, étant donnés ses non-terminaux nuls et ses premiers. On pourra adopter le schéma suivant :

let follow g nulls firsts =
  let update (follows,b) nt follow_nt =
     ...
     ... met à jour la table follows avec nt -> follow_nt
     ... et remplace b par true si la table a été modifiée
     ...
  in
  let rec update_prod ((follows,b) as acc) nt p =
     ...
     ... examine la production nt -> p de la grammaire
     ... et met à jour le couple (follows,b) pour tout non-terminal X de p
     ...
  in
  let step follows =
    List.fold_left
      (fun acc (nt,p) -> update_prod acc nt p)
      (follows,false) g.rules
  in
  fixpoint step (empty_map g)

Construction de la table d'analyse LL(1)

On se donne les types Caml suivants pour représenter les dictionnaires indexés par des terminaux et les ensembles de productions :

module Tmap = Map.Make(String)
module Pset = Set.Make(struct type t = production let compare = compare end)

On définit alors le type suivant pour les tables d'analyse descendante :

type expansion_table = Pset.t Tmap.t Ntmap.t

Une telle table est donc un dictionnaire associant à chaque non-terminal puis à chaque terminal un ensemble de productions. Les deux dictionnaires sont creux : lorsqu'une ligne ou une colonne de la table est vide, il n'y a pas d'entrée correspondante dans la table.

Écrire une fonction

val add_entry : expansion_table -> non_terminal -> terminal -> production -> expansion_table

qui ajoute une entrée dans la table. On prendra soin de correctement traiter le cas d'une première occurrence d'une ligne ou d'une colonne.

Écrire une fonction

val expansions : grammar -> expansion_table

qui calcule la table d'analyse descendante d'une grammaire donnée.

On pourra tester avec la grammaire suivante (qui caractérise les mots contenant autant de a que de b) :

let g1 = {
  start = "S'";
  rules = ["S'", [NonTerminal "S"; Terminal "#"];
	   "S", [];
	   "S", [Terminal "a"; NonTerminal "A"; NonTerminal "S"];
	   "S", [Terminal "b"; NonTerminal "B"; NonTerminal "S"];
	   "A", [Terminal "a"; NonTerminal "A"; NonTerminal "A"];
	   "A", [Terminal "b"];
	   "B", [Terminal "b"; NonTerminal "B"; NonTerminal "B"];
	   "B", [Terminal "a"];
	  ] }

let table1 = expansions g1

Pour visualiser le résultat, on pourra utiliser le code suivant qui définit un pretty-printer pp_table pour les tables d'expansion :

let pp_symbol fmt = function
  | Terminal s -> Format.fprintf fmt "\"%s\"" s
  | NonTerminal s -> Format.fprintf fmt "%s" s

let rec pp_production fmt = function
  | [] -> ()
  | [x] -> pp_symbol fmt x
  | x :: l -> Format.fprintf fmt "%a %a" pp_symbol x pp_production l

let pp_table fmt t =
  let print_entry c p =
    Format.fprintf fmt "  %s: @[%a@]@\n" c pp_production p in
  let print_row nt m =
       Format.fprintf fmt "@[Expansions for %s:@\n" nt;
       Tmap.iter (fun c rs -> Pset.iter (print_entry c) rs) m;
       Format.fprintf fmt "@]" in
  Ntmap.iter print_row t

Sur l'exemple ci-dessus, le résultat de

  let () = Format.printf "%a@." pp_table table1

doit être le suivant :

Expansions for A:
  a: "a" A A
  b: "b"
Expansions for B:
  a: "a"
  b: "b" B B
Expansions for S:
  #:
  a: "a" A S
  b: "b" B S
Expansions for S':
  #: S "#"
  a: S "#"
  b: S "#"

Tester également avec la grammaire g_arith donnée tout au début de ce sujet.

let table_arith = expansions g_arith
let () = Format.printf "%a@." pp_table table_arith

Caractérisation LL(1)

Écrire une fonction is_ll1 : expansion_table -> bool qui détermine si la table d'expansion ne contient qu'au plus une règle par case (ce qui, par définition, caractérise alors la grammaire comme appartenant à la classe LL(1)).

Tester avec

let () = assert (is_ll1 table1)
let () = assert (is_ll1 table_arith)

Tester également avec une grammaire de votre choix qui n'est pas LL(1).

Reconnaissance d'un mot

Écrire une fonction

val analyze : non_terminal -> expansion_table -> string list -> bool

qui détermine si un mot est reconnu par une grammaire, étant donnés son non-terminal de départ et sa table d'expansion. (On ne se souciera pas de savoir si la table correspond à une grammaire LL(1) et, en cas d'ambiguïté, on choisira une production au hasard avec Pset.choose.) On n'oubliera pas d'ajouter le symbole "#" à la fin du mot. Note : il y a succès de l'analyse si et seulement si on parvient à une pile et à une entrée toutes deux égales à la liste vide [], vu que l'on a ajouté une règle S' -> S#.

On pourra tester avec la grammaire g1 en utilisant le code suivant

let explode s =
  let n = String.length s in
  let rec make i = if i = n then [] else String.make 1 s.[i] :: make (i+1) in
  make 0

let test1 s = analyze g1.start (expansions g1) (explode s)

let () = assert (test1 "")
let () = assert (test1 "ab")
let () = assert (test1 "ba")
let () = assert (test1 "abab")
let () = assert (test1 "aaabbb")
let () = assert (test1 "aaabababbbababab")

let () = assert (not (test1 "a"))
let () = assert (not (test1 "b"))
let () = assert (not (test1 "aab"))
let () = assert (not (test1 "aaabbba"))
let () = assert (not (test1 "aaabbbaabab"))
let () = assert (not (test1 "aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb"))

Bootstrap : la grammaire des grammaires

On se donne la grammaire suivante :

let g_gram =
  { start = "S'";
    rules = [ "S'", [ NonTerminal "S"; Terminal "#" ];
              "S",  [ NonTerminal "R" ];
              "S",  [ NonTerminal "R"; Terminal ";"; NonTerminal "S" ];
              "R",  [ Terminal "ident"; Terminal "::="; NonTerminal "P"];
              "P",  [ NonTerminal "W" ];
              "P",  [ NonTerminal "W"; Terminal "|"; NonTerminal "P" ];
              "W",  [ ];
              "W",  [ NonTerminal "C"; NonTerminal "W";];
              "C",  [ Terminal "ident"];
              "C",  [ Terminal "string"];
            ] }

C'est la grammaire des grammaires, avec la signification suivante pour les différentes non-terminaux :

S = suite de règles séparées par des point-virgules ;
R = règles pour un non-terminal ;
P = productions séparées par des barres verticales ;
W = membre droit de production ;
C = symbole terminal ou non-terminal.

Vérifier qu'elle n'est pas LL(1) :

let table_gram = expansions g_gram
let () = Format.printf "%a@." pp_table table_gram
let () = assert (not (is_ll1 table_gram))

Proposer une grammaire LL(1) reconnaissant le même langage.

solution

retour à la page du cours