BASIC APASCALADO VII - A versatilidade dos autómatos.

Vamos   fazer  um  programa   para  analisar   uma sequência   de  caracteres  com   o  objectivo 
 de encontrar um numero real de virgula fixa.

Primeiro,  definimos  uma gramática que contenha a sintaxe do numero:
  Fracçäo -->  Sinal Corpo
  Sinal ---->  "+"  /  "-"  /  ""
  Corpo ---->  Inteiro  /  "." Inteiro  /  Inteiro "."  /  Inteiro "." Inteiro 
  Inteiro -->  digito  /  digito Inteiro
  digito --->  "0"  /  "1"  /  "2"  /  ...  /  "9"

  Em que o traço de "divisäo" ( / ) significa OU.

Simplificando, vem
  F	=  S  C
  S	=  "+"  +  "-"  +  ""
  C	=  I  +  I"."I  +  "."I  +  I"."
  I	=  d1

  Em  que  o  sinal  "mais"  ( + )  significa OU e, d1 significa um ou mais digitos.

Agora,  deduzimos  o  valor  da  expressäo  F  em funçäo dos  outros  simbolos.  Fazemos  isto  com
 substituiçöes sucessivas:
  C	=  d1 + d1"."d1 + "."d1 + d1"."

agrupando em duas partes, vem
  C	=  (d1 + d1".") + (d1"."d1 + "."d1)

colocando d1 em evidência na primeira parte e, "."d1 na segunda, vem
  C	=  (d1("" + ".")) + ((d1 + "")"."d1)
que se pode simplificar para
  C	=  (d1("" + ".")) + (d0"."d1)

  em que d0 significa zero ou mais digitos.

Ora, como o sinal é
  S	=  ("+" + "-" + "")
entäo
  F =  ("+" + "-" + "")( (d1("" + ".") + (d0"."d1) )

Em vez  de  deduzir  matemáticamente  a gramática, tambem se pode deduzir gráficamente, com diagramas.

Por falar  em diagramas...  Esta  fórmula  pode se transcrever directamente para um esquema gráfico: 

                   +--------+     +---+
      +---+        V  +---+ ¦  +->¦ . +-+
   +->¦ + +->+   +--->¦ d +----¦  +---+ +------------+
   ¦  +---+  ¦   ¦    +---+    +---->---+            ¦
   ¦  +---+  ¦   ¦   +--------+                      ¦
-->+->¦ - +->+-->¦   V  +---+ ¦           +--------+ +--->
   ¦  +---+  ¦   ¦ +--->¦ d +---+  +---+  V  +---+ ¦ ¦
   +---->----+   +-¦    +---+   +->¦ . +---->¦ d +---+
                   +------------+  +---+     +---+

Perceberam  isto?   Muito  bem,  podem  esquecer; este esquema näo serve para nada!

Colocando isto  em funçäo  do estado da situaçäo, fica:

	                        "d"
	                    +--------+    "."
          "+"           "d" V  +---+ ¦   +-----+
      +---------+     +------->¦ 3 +---->¦ ""  +---+
    +---+ "-" +---+   ¦        +---+     +-----+   ¦  +---+
--->¦ 1 +-----¦ 2 +-->¦			           +->¦ 6 +--->
    +---+ ""  +---+   ¦	     "d"            "d"    ¦  +---+
      +---------+     ¦  +--------+     +--------+ ¦
                      ¦  V  +---+ ¦ "." V  +---+ ¦ ¦ "d"
                      +---->¦ 4 +--------->¦ 5 +---+ 
                            +---+          +---+

Vamos meter isto numa tabela.
Num eixo ficam os estados e, no outro, os simbolos terminais.

+---+---------------+
¦E\S¦ + ¦ - ¦ . ¦ d ¦ Esta  tabela  representa  um
+---+---+---+---+---+ autómato não determinístico; 
¦ 1 ¦ 24¦ 24¦ 5 ¦346¦ se colocar-mos um programa a 
+---+---+---+---+---¦ executar no estado 1,  e lhe 
¦ 2 ¦ - ¦ - ¦ 5 ¦346¦ fornecermos um "+",  ele não 
+---+---+---+---+---¦ sabe se vai para  o estado 2 
¦ 3 ¦ - ¦ - ¦  6¦3 6¦ ou para o estado 4. 
+---+---+---+---+---¦ Isto não é muito agradável. 
¦ 4 ¦ - ¦ - ¦ 5 ¦ 4 ¦ Vamos resolver isso... 
+---+---+---+---+---¦
¦ 5 ¦ - ¦ - ¦ - ¦ 56¦
+---+---+---+---+---¦ 
¦ 6 ¦ ok¦ ok¦ ok¦ ok¦ 
+---+---------------+

Devido  aos percursos "vazios",  o START  pode ser qualquer dos estados {1,2,4},  
por isso, este fica sendo o nosso primeiro estado: 

  +---+---------------+
  ¦E\S¦ + ¦ - ¦ . ¦ d ¦
--+---+---+---+---+---+
A ¦124¦ 24¦ 24¦ 5 ¦346¦ união dos estados {1,2,4}
--+---+---+---+---+---¦
B ¦ 24¦ - ¦ - ¦ 5 ¦346¦ união dos estados {2,4}
--+---+---+---+---+---¦
C ¦ 5 ¦ - ¦ - ¦ - ¦ 56¦
--+---+---+---+---+---¦
D ¦346¦ - ¦ - ¦ 56¦346¦ união dos estados {3,4,6}
--+---+---+---+---+---¦
E ¦ 56¦ - ¦ - ¦ - ¦ 56¦ união dos estados {5,6}
----------------------+

Começamos com o estado {1,2,4};
do estado A tiramos três novos estados: {2,4}, {5}, {3,4,6}; 
do estado C tiramos um novo estado: {5,6}. 

+---+-------------------+
¦E\S¦ + ¦ - ¦ . ¦ d ¦ $ ¦ Pronto! 
+---+---+---+---+---+---+ Agora temos  um autómato 
¦ A ¦ B ¦ B ¦ C ¦ D ¦ - ¦ muito  mais simples;  um 
+---+---+---+---+---+---¦ autómato deterministico. 
¦ B ¦ - ¦ - ¦ C ¦ D ¦ - ¦
+---+---+---+---+---+---¦ O estado final  era o 6, 
¦ C ¦ - ¦ - ¦ - ¦ E ¦ - ¦ e agora? 
+---+---+---+---+---+---¦ Agora são os estados que 
¦ D ¦ - ¦ - ¦ E ¦ D ¦ ok¦ contêm o estado 6,  isto 
+---+---+---+---+---+---¦ é, o estado D (346)  e o 
¦ E ¦ - ¦ - ¦ - ¦ E ¦ ok¦ estado E (56). 
+---+-------------------+

Para se verem melhor os estados finais,  introduzi 
uma coluna com "$" (para representar FIM DE TEXTO). 
Quando  a  intersecção  do  estado  actual  com  o 
caracter  é  uma  letra, entäo  mudamos  para esse 
estado.  Quando a intersecçäo é um traço, então há 
erro de sintaxe.  Quando a intersecçäo é OK, então 
acabou o reconhecimento com sucesso.

Se quisermos calcular  o numero ao mesmo tempo que 
verificamos a sua sintaxe,  arranjamos  uma tabela 
de acções a executar:

+---+-------------------+
¦E\S¦ + ¦ - ¦ . ¦ d ¦ $ ¦
+---+---+---+---+---+---+
¦ A ¦ 1 ¦ 2 ¦ 1 ¦ 3 ¦ -1¦ 
+---+---+---+---+---+---¦
¦ B ¦ -1¦ -1¦ 1 ¦ 3 ¦ -1¦-1: erro 
+---+---+---+---+---+---¦ 0: inicializar variáveis 
¦ C ¦ -1¦ -1¦ -1¦ 4 ¦ -1¦ 1: skip, näo fazer nada 
+---+---+---+---+---+---¦ 2: sinal negativo
¦ D ¦ -1¦ -1¦ 3 ¦ 3 ¦ 5 ¦ 3: adicionar a inteiro 
+---+---+---+---+---+---¦ 4: adicionar a decimal 
¦ E ¦ -1¦ -1¦ -1¦ 4 ¦ 5 ¦ 5: terminar cálculo 
+---+-------------------+

Vamos ao esquema final:

    +-----+   "."   +-----+
 +--+  B  +-------->+  C  +->+
 ¦  +-----+         +-----+  ¦
 ¦     A	       A     ¦
d¦  "+"¦"-" +=====+ "."¦     ¦ d
 ¦     +----+¦ A ¦+----+     ¦
 ¦	    +=====+          ¦
 ¦             |             ¦	
 ¦	    d  ¦             ¦
 ¦     +-------+	     ¦
 ¦     V                     ¦
 ¦  +-----+   "."   +-----+  ¦
 +--+  D  +---------+  E  +--+ 
    +     +---+ +---+     +
    +-+-+-+   | |   +-+-+-+
      ¦ A     ¦ ¦     ¦ A
      +-+     ¦$¦     +-+
       d      ¦ ¦      d
            +=====+
            ¦¦ ok¦¦
            +=====+ 

Estes autómatos  podem servir para controlar menus de programas,  
ou para  controlar a execução total de um programa (por exemplo 
um editor de texto). Se se sentirem muito inspirados até podem 
utilizar isto como  impulso  para  fazer compiladores!  
Na colecçäo SISTEMAS há um livro para isso, mas aviso que näo é 
para qualquer um ler.

Além disso o automato pode funcionar ao contrário; em vez de 
interpretar texto, pode gerar texto. Por exemplo,  dada   uma  
simplificaçäo  da  gramática portuguesa, gerar palavras pronunciáveis.

No próximo artigo veremos o programa.


-----------------------------
ZE OLIVEIRA zarsoft(a)clix.pt
-----------------------------