TD 4 - Construção de autómatos deterministas a partir de expressões regulares, analisadores léxicos

A ideia de partida é a seguinte: se um autómato finito reconhece a expressão regular r, então para toda a letra de uma palavra reconhecida podemos lhe fazer corresponder uma letra contida em r. Para distinguir as diferentes occorências de uma mesma letra em r, vamos indexá-los com inteiros. consideremos por exemplo a expressão regular (a|b)* a (a|b), que define as palavras sobre o alfabeto {a,b} cuja penúltima letra é um a. Se indexamos os caracteres, obtemos

(a1|b1)* a2 (a3|b2)

a1a1b1a1a2b2

A ideia é, então, de construir um autómato cujos estados são conjuntos de letras indexadas, correspondendo às occorências que podem ser lidas num dado momento. Desta forma, o estado inicial contem as primeiras letras possíveis das palavras reconhecidas. No nosso exemplo, estas são a₁,b₁,a₂. Para construir as transições, basta calcular, para cada ocorrência de uma letra, o conjunto das ocorrências que podem estar em seguida. No nosso exemplo, se acabamos de ler a₁, então os caracteres possíveis seguintes são a₁,b₁,a₂ ; se acabamos de ler a₂, então estes são a₃,b₂.

Questão 1. Nulidade de uma expressão regular

type ichar = char * int

type regexp =
  | Epsilon
  | Character of ichar
  | Union of regexp * regexp
  | Concat of regexp * regexp
  | Star of regexp

val null : regexp -> bool

Questão 2. Os primeiros e o últimos

module Cset = Set.Make(struct type t = ichar let compare = compare end)

Definir uma função

val first : regexp -> Cset.t

De forma semelhante, definir uma função

val last : regexp -> Cset.t

Questão 3. Os seguintes

val follow : ichar -> regexp -> Cset.t

De notar que a letra d pertence ao conjunto follow c r se e só se

• ou existe uma sub-expressão de r da forma r₁r₂ com d elemento de first r₂ e c elemento de last r₁ ;
• ou existe uma sub-expressão de r da forma r₁* com d elemento de first r₁ e c elemento de last r₁.

Questão 4. Construção do autómato

1. junta-se um novo caracter # no fim de r ;
2. o estado de partida (inicial) é o conjunto first r ;
3. temos uma transição do estado q para o estado q' aquando da leitura do caracter c (trata-se aqui de uma letra não indexada) se q' é a união de todos os follow ci r para todos os elementos ci de q tais que fst ci = c ;
4. os estados de aceitação (finais) são os estados que contêm o caracter #.

Definir uma função

val next_state : regexp -> Cset.t -> char -> Cset.t

Para representar o autómato finito dá-mo-nos o tipo OCaml seguinte :

module Cmap = Map.Make(Char)
module Smap = Map.Make(Cset)

type state = Cset.t

type autom = {
  start : state;
  trans : state Cmap.t Smap.t
}

let eof = ('#', -1)

val make_dfa : regexp -> autom

let make_dfa r =
  let r = Concat (r, Character eof) in
  (* transições em curso de construção *)
  let trans = ref Smap.empty in
  let rec transitions q =
    (* a função transitions constrói todas as transições do estado q,
       se é a primeira vez que este é explorado  *)
    ...
  in
  let q0 = first r in
  transitions q0;
  { start = q0; trans = !trans }

Nota : é, claro, possível construir um autómato cujos estados não são conjuntos mas sim, por exemplo, inteiros, para mais eficiência na execução do autómato. Isto pode, alias, ser feito durante a própria construção, ou a posteriori. Mas isso não é o nosso propósito principal aqui.

Visualização com a ferramenta dot

let fprint_state fmt q =
  Cset.iter (fun (c,i) ->
    if c = '#' then Format.fprintf fmt "# " else Format.fprintf fmt "%c%i " c i) q

let fprint_transition fmt q c q' =
  Format.fprintf fmt "\"%a\" -> \"%a\" [label=\"%c\"];@\n"
    fprint_state q
    fprint_state q'
    c

let fprint_autom fmt a =
  Format.fprintf fmt "digraph A {@\n";
  Format.fprintf fmt "  @[\"%a\" [ shape = \"rect\"];@\n" fprint_state a.start;
  Smap.iter
    (fun q t -> Cmap.iter (fun c q' -> fprint_transition fmt q c q') t)
    a.trans;
  Format.fprintf fmt "@]@\n}@."

let save_autom file a =
  let ch = open_out file in
  Format.fprintf (Format.formatter_of_out_channel ch) "%a" fprint_autom a;
  close_out ch

(*  (a|b)*a(a|b)  *)
let r = Concat (Star (Union (Character ('a', 1), Character ('b', 1))),
		Concat (Character ('a', 2),
			Union (Character ('a', 3), Character ('b', 2))))
let a = make_dfa r
let () = save_autom "autom.dot" a

A execução produz um ficheiro autom.dot que pode ser visualizado em Unix com o comando

  dotty autom.dot

  dot -Tps autom.dot | gv -

Questão 5. Reconhecimento de uma palavra

val recognize : autom -> string -> bool

Aqui encontram-se alguns testes positivos :

let () = assert (recognize a "aa")
let () = assert (recognize a "ab")
let () = assert (recognize a "abababaab")
let () = assert (recognize a "babababab")
let () = assert (recognize a (String.make 1000 'b' ^ "ab"))

let () = assert (not (recognize a ""))
let () = assert (not (recognize a "a"))
let () = assert (not (recognize a "b"))
let () = assert (not (recognize a "ba"))
let () = assert (not (recognize a "aba"))
let () = assert (not (recognize a "abababaaba"))

Apresentamos aqui outro teste com uma expressão regular que especifica as palavras com um número par de ocorrências da letra b :

let r = Star (Union (Star (Character ('a', 1)),
		     Concat (Character ('b', 1),
			     Concat (Star (Character ('a',2)),
				     Character ('b', 2)))))
let a = make_dfa r
let () = save_autom "autom2.dot" a

let () = assert (recognize a "")
let () = assert (recognize a "bb")
let () = assert (recognize a "aaa")
let () = assert (recognize a "aaabbaaababaaa")
let () = assert (recognize a "bbbbbbbbbbbbbb")
let () = assert (recognize a "bbbbabbbbabbbabbb")

let () = assert (not (recognize a "b"))
let () = assert (not (recognize a "ba"))
let () = assert (not (recognize a "ab"))
let () = assert (not (recognize a "aaabbaaaaabaaa"))
let () = assert (not (recognize a "bbbbbbbbbbbbb"))
let () = assert (not (recognize a "bbbbabbbbabbbabbbb"))

Questão 6. Geração de um analisador léxico

Mais precisamente, vamos produzir código da forma seguinte :

type buffer = { text: string; mutable current: int; mutable last: int }

let next_char b =
  if b.current = String.length b.text then raise End_of_file;
  let c = b.text.[b.current] in
  b.current <- b.current + 1;
  c

let rec state1 b =
  ...
and state2 b =
  ...
and state3 b =
  ...

A cada estado do autómato corresponde uma função statei com um argumento b de tipo buffer. Esta função executa a tarefa seguinte :

1. Se o estado é um estado final, então atribuimos a b.last o valor de b.current.
2. em seguida, invoca-se next_char b e examinamos o seu resultado. Se se trata de um caracter para o qual uma transição existe então invoca-se a função correspondente. Senão, levanta-se uma excepção (por exemplo, com recurso a failwith "lexical error").

Definir uma função

  val generate: string -> autom -> unit

• Pode-se começar por numerar todos os estados, por exemplo, construindo um dicionário de tipo int Smap.t que associa a cada estado um número único.
• No caso da função que trata do arquivo no ficheiro, esta poderá inspirar-se do código da função save_autom dada mais acima.

  let start = state42

Para testar, escrever (num outro ficheiro lexer.ml, desta vez escrito à mão) um programa que corta uma string em lexemas, usando o código produzido automaticamente (atribuindo de forma fixa o nome do ficheiro, por exemplo a.ml). O princípio por seguir descreve-se com base num ciclo que efectua as ações seguintes :

1. posicionar o campo last em -1 ;
2. invocar a função start e apanhar a excepção e que esta levantou ;
3. se o campo last continuar com o valor -1, então nenhum lexema foi reconhecido e assim terminar levantando novamente a excepção e ;
4. senão, mostrar o lexema qui foi reconhecido e atribuir ao campo current o valor do campo last.

O programa resultante poderá ser testar, por exemplo, com a expressão regular a*b, executando

let r3 = Concat (Star (Character ('a', 1)), Character ('b', 1))
let a = make_dfa r3
let () = generate "a.ml" a

  % ocamlopt a.ml lexer.ml

--> "ab"
--> "b"
--> "aaab"

--> "ab"
exception End_of_file

exception Failure("lexical error")

--> "ab"
--> "ba"
--> ""
would now loop

Questão 7. Uso do OCamllex