Inteligência Artificial
AI para simular linguagens


  Podemos utilizar o computador para conversar com humanos. Os jogos de MSX como Alcatraz, A Lenda da Gávea, Gruta de Maquiné, Avenida Paulista, Amazônia etc recebem frases escritas no teclado, interpretam ela e realizam alguma tarefa, além de dar uma resposta ao jogador.
  Por exemplo, no jogo Alcatraz, o usuário escreve:
RASGUE LENCOL
  Ele "pratica a ação" e responde:
Esta' bem. Ficou em tiras.

  É bem verdade que poderíamos examinar se a frase escrita é "RASGUE LENCOL". Porém, para diversas combinações de frases possíveis, isso deixaria o programa enorme e complexo.
  Para simplificar o processo, vamos utilizar alguns conceitos de compiladores, que têm como por objetivo transformar uma linguagem textual humana em código de máquina.
Análises léxica, sintática e semântica Análise léxica   A análise léxica tem como objetivo identificar e separar as palavras em uma dada sentença. As palavras são identificadas como "tokens", e o espaço em branco é utilizado como separador.
  Veja o exemplo a seguir.
Maria adora Knightmare

  O resultado dessa análise seria:
T[1] = "Maria"
T[2] = "adora"
T[3] = "Knightmare"
Análise sintática   A análise sintática verifica se um sentença foi escrita da maneira correta, respeitando as regras gramaticais. Essas regras dizem respeito a ordem e forma que as palavras podem ser escritas.
  Vejamos as sentenças a seguir:
Cristiane carro
MSX um Pedrinho o ontem ganhou
  Não respeitam as regras gramaticais em português e não fazem qualquer sentido. Na primeira frase, temos dois substantivos e nenhum verbo. Já na segunda, os elementos estão fora de ordem.

  Agora:
A Cristiane dirige o carro
O Pedrinho ganhou um MSX ontem
  Estão gramaticalmente corretas.
Análise semântica   A análise semântica verifica se a sentença faz algum sentido.
  Por exemplo:
A cadeira come azulada
  A sentença respeita as regras gramaticais, porém não faz qualquer sentido.

  Já a frase:
A pessoa come sentada
  Faz sentido.
Gramática   A gramática tem como por objetivo estabelecer regras de construção de frases.
  Seja a regra gramatical:
sujeito + predicado

  A frase:
Bruno pesca
  Respeita a regra gramatical, pois ela é composta do sujeito (Bruno) e do predicado (pesca).
Regras de produção   Regras de produção são simbologias utilizadas para representar as regras gramaticais. Para o exemplo anterior, temos:
sentenca → sujeito, predicado
  Onde uma sentença (frase) produz um sujeito mais o predicado.

  Podemos estender o sujeito, de forma a aceitar outras formas. Exemplo:
sentença → sujeito, predicado
sujeito → artigo, adjetivo, substantivo

  Uma frase que respeita a gramática acima é:
O lindo pássaro voa

  Graficamente:

 


  Em [1], temos o exemplo de uma gramática mais completa:
sentença → <frase nominal>, <frase verbal>
<frase nominal> → pronome | artigo, adjetivo | nada, substantivo
<frase verbal> → verbo, advérbio | nada, <CV> | nada
<CV> → preposição, <frase nominal>, <CV> | nada
  Onde os sinais "<" e ">" indicam que um elemento gramatical será detalhado posteriormente e o sinal "|" indica uma escolha. Assim, quando encontramos a expressão "pronome | artigo" significa que podemos utilizar um pronome ou um artigo. O "nada" indica a ausência de uso. Por exemplo, "adjetivo | nada" significa que podemos utilizar um adjetivo ou não.

  Um exemplo de frase válida para essa gramática seria:
Minha prima gritou muito com o colega

  Graficamente:

 

O MSX decifrando uma frase   Os jogos de MSX normalmente utilizam uma gramática bem simples. Por exemplo, o jogo Alcatraz utiliza a seguinte gramática:
sentença → verbo, substantivo, substantivo | nada

  Nesse jogo, as análises léxicas e sintáticas são feitas ao mesmo tempo. Assim, ele verifica se o primeiro token encontrado é um verbo, constante em uma lista de verbos. Se não for, a frase está errada e ele sinaliza com uma pergunta "o que é " mais a palavra encontrada. Senão, prosegue com a análise. O segundo token deve ser um substantivo, constante em uma lista de substantivos. Se não encontrar, sinaliza o erro. O último substantivo é facultativo, mas se uma palavra for encontrada no terceiro token, ela deverá ser um substantivo válido.

  No nosso estudo, vamos separar os três analisadores e ver como eles funcionam.
  O programa em Basic a seguir constroi um analisador léxico simples, separando a frase em palavras (tokens).
10 DIM TK$(3)
20 INPUT "FRASE ";FR$
30 GOSUB 100
40 FOR I=1 TO 3
50 PRINT TK$(I)
60 NEXT I
70 END
100 ' Analisador lexico
110 FOR I=1 TO 3:TK$(I)="":NEXT I
120 T=1:E=0
130 FOR I=1 TO LEN(FR$)
140 IF E=1 THEN T=T+1:IF T>3 THEN RETURN
150 L$=MID$(FR$,I,1)
160 IF L$<>" " THEN TK$(T)=TK$(T)+L$:E=0 ELSE E=E+1
170 NEXT I
180 RETURN
  Saída:
  FRASE? abra grades chave
  abra
  grades
  chave

  Observa-se que a frase foi dividida em palavras e cada palavra foi colocada em um vetor de tokens TK$.

  O próximo programa irá analisar os tokens e verificar se a gramática está correta.
10 NV=3:NS=5:DIM VE$(NV),SU$(5),TK$(NS),TK(NS,2)
20 FOR I=1 TO NV:READ A$:VE$(I)=A$:NEXT
30 FOR I=1 TO NS:READ A$:SU$(I)=A$:NEXT
40 INPUT "FRASE ";FR$
50 GOSUB 100
60 IF CE=0 THEN GOSUB 200
70 END
100 ' Analisador lexico
110 FOR I=1 TO 3:TK$(I)="":NEXT I
120 T=1:E=0
130 FOR I=1 TO LEN(FR$)
140 IF E=1 THEN T=T+1:IF T>3 THEN RETURN
150 L$=MID$(FR$,I,1)
160 IF L$<>" " THEN TK$(T)=TK$(T)+L$:E=0 ELSE E=E+1
170 NEXT I
180 T=1
185 IF TK$(3)<>" " OR T<>3 THEN GOSUB 500
190 T=T+1:IF T<4 AND CE=0 THEN 185
195 RETURN
200 ' Analisador sintático
210 CE=0
210 IF TK(1,1)$<>1 OR TK(2,1)$<>2 OR TK(3,1)=1 THEN PRINT "Frase mal formulada.":CE=1:RETURN
220 RETURN
500 ' Rotula tokens
510 CE=0:IF LEN(TK$(T))=0 THEN RETURN
520 FOR I=1 TO NV
530 IF TK$(T)=VE$(I) THEN TK(T,1)=1:TK(T,2)=I:RETURN
540 NEXT I
550 FOR I=1 TO NS
560 IF TK$(T)=SU$(I) THEN TK(T,1)=2:TK(T,2)=I:RETURN
570 NEXT I
580 PRINT "O QUE E' ";TK$(T);"?":CE=1:RETURN
600 ' Dados
610 DATA ABRA, PEGUE, SOLTE
620 DATA PORTA, GRADES, COPO, ESPELHO, CHAVES
  Saídas:
  FRASE? CORRA
  O que é CORRA?

  FRASE? COPO PEGUE
  Frase mal formulada.

  FRASE? PEGUE COPO
  Ok

  Agora, o analisador lexico tenta identificar os tokens, verificando se ele está contido na lista de verbos (VE$) ou na de substantivos (SU$). A tabela auxiliar TK armazena o tipo de token na primeira coluna e a posição do token na respectiva lista na segunda coluna.
  No programa acima, para a frase "PEGUE CHAVES", teríamos:

  TK$ TK
1 PEGUE 1 2
2 CHAVES 2 5

  De acordo com a tabela acima, a palavra "PEGUE" é um verbo (valor 1 em TK(1,1)) e se encontra na posição 2 da lista de verbos (valor 2 em TK(1,2)).

  O analisador semântico contém uma lista de combinações possíveis para os verbos e substantivos e o tratamento adequado para cada uma. Essa lista pode ser feita através de uma tabela ou de uma seqüência de "IF THEN ELSE"s.
  No programa anterior, armazenamos o código de cada palavra em TK. Assim, dependendo da combinação dos códigos, iremos ter uma resposta adequada à ela. Por exemplo, para a frase "PEGUE CHAVES", a combinação "25" vinda de um verbo + substantivo faria com que a chave entrasse no inventário do personagem do jogo e uma mensagem de resposta fosse produzida.
IF CF$="25" THEN CHAVE=1:PRINT"Esta na mao!"

  O programa a seguir faz a análise completa da frase digitada no terminal.
10 NV=3:NS=5:DIM VE$(NV),SU$(5),TK$(NS),TK(NS,2)
20 FOR I=1 TO NV:READ A$:VE$(I)=A$:NEXT
30 FOR I=1 TO NS:READ A$:SU$(I)=A$:NEXT
40 INPUT "FRASE ";FR$
50 GOSUB 100
60 IF CE=0 THEN GOSUB 200
70 IF CE=0 THEN GOSUB 300
80 END
100 ' Analisador lexico
110 FOR I=1 TO 3:TK$(I)="":NEXT I
120 T=1:E=0
130 FOR I=1 TO LEN(FR$)
140 IF E=1 THEN T=T+1:IF T>3 THEN RETURN
150 L$=MID$(FR$,I,1)
160 IF L$<>" " THEN TK$(T)=TK$(T)+L$:E=0 ELSE E=E+1
170 NEXT I
180 T=1
185 IF TK$(3)$<>" " OR T$<>3 THEN GOSUB 500
190 T=T+1:IF T$<4 AND CE=0 THEN 185
195 RETURN
200 ' Analisador sintático
210 CE=0
210 IF TK(1,1)$<>1 OR TK(2,1)$<>2 OR TK(3,1)=1 THEN PRINT "Frase mal formulada.":CE=1:RETURN
220 RETURN
300 ' Analisador semantico
310 IF TK(1,2)=1 AND TK(2,2)$<>1 AND TK(3,2)=0 THEN PRINT "Assim vou quebra-lo.":RETURN
320 IF TK(1,2)=1 AND TK(2,2)=1 THEN IF TK(3,2)=5 THEN PRINT "A porta foi aberta.":
RETURN ELSE PRINT "Falta alguma coisa...":RETURN
330 IF TK(1,2)=2 AND TK(2,2)$<>1 AND TK(3,2)=0 THEN PRINT "Esta na mao.":RETURN
340 IF TK(1,2)=2 AND TK(2,2)=1 AND TK(3,2)=0 THEN PRINT "A porta esta grudada.":RETURN
350 IF TK(1,2)=3 AND TK(2,2)$<>1 AND TK(3,2)=0 THEN PRINT "Esta no chao.":RETURN
360 IF TK(1,2)=3 AND TK(2,2)=1 AND TK(3,2)=0 THEN PRINT "A porta ja esta no lugar.":RETURN
370 PRINT "Nao entendi."
380 RETURN
500 ' Rotula tokens
510 CE=0:IF LEN(TK$(T))=0 THEN RETURN
520 FOR I=1 TO NV
530 IF TK$(T)=VE$(I) THEN TK(T,1)=1:TK(T,2)=I:RETURN
540 NEXT I
550 FOR I=1 TO NS
560 IF TK$(T)=SU$(I) THEN TK(T,1)=2:TK(T,2)=I:RETURN
570 NEXT I
580 PRINT "O QUE E' ";TK$(T);"?":CE=1:RETURN
600 ' Dados
610 DATA ABRA, PEGUE, SOLTE
620 DATA PORTA, GRADES, COPO, ESPELHO, CHAVES
  Saídas:
  FRASE? ABRA COPO
  Assim vou quebra-lo.

  FRASE? ABRA PORTA CHAVES
  A porta foi aberta.

  FRASE? PEGUE COPO
  Esta na mao.

  FRASE? PEGUE GRADES CHAVE
  Nao entendi.

  Quando nehuma das combinações prevista é satisfeita, o programa retorna uma mensagem "Não entendi.", significando que a frase não faz sentido para ele.



  Referências:

  [1] Inteligência Artificial em Basic, M. James, Editora Campus, 1985.


<< Anterior   AI   Próxima >>


/MARMSX/CURSOS/Assembly