Analisador de gramática em Prolog

Prolog tem a capacidade de carregar regras gramaticais de cláusulas definidas (regras DCG - definite clause grammar) e convertê-las automaticamente em regras de análise Prolog. Como ilustração, considere um tipo típico de gramática regular à esquerda para a linguagem regular a*bb ...

S --> a S
S --> B
B --> bC
C --> b

Para Prolog, reescreva esta gramática algo assim ...

s1 --> [a], s1.
s1 --> b.

b --> [b,b].

Observe que juntamos as duas últimas regras em uma. Não se confunda com o uso de 'b' tanto como um símbolo não terminal quanto como um símbolo terminal. Em gramáticas Prolog, qualquer uso como símbolo de terminal deve sempre estar entre colchetes '[..]'.

Quando carregadas no Prolog, essas regras gramaticais são traduzidas nas seguintes cláusulas

s1(A,B) :-
   'C'(A,a,C),
   s1(C,B).
s1(A,B) :- b(A,B).

b([b,b|A],A).

'C' é um predicado Prolog embutido, cujo significado intuitivo é "conecta" e cuja definição é ...

'C'([A|B],A,B).

Pode-se usar a gramática como analisador ...

?- 'C'([1,2,3],1,[2,3]).
Yes

?- s1([a,a,a,b,b],[]).
Yes

?- s1([a,b[,[]).
No

... but not as a generator ...

?- s1(S,[]).
... (infinite loop)

O uso de uma gramática Prolog como gerador é incomum. Veremos que a maioria das gramáticas úteis são especificadas para fins de análise, não para geração de expressão.

Aqui está uma árvore de cláusulas, com raiz s1([a,b,b],[]) ...

Fig. 7.1.1

Pares de parâmetros como [a,b,b] e [], como na raiz da árvore, "representam diferenças". Assim, o par de parâmetros [a,b,b] e [b] representa a diferença [a,a].

A razão pela qual a gramática Prolog (regular à esquerda) não pode ser usada para gerar sequências é que a gramática é recursiva à direita. Pode haver qualquer número de 'a' no início da sequência 'S', e a primeira cláusula para 's1' pode ser usada repetidamente. A seguinte derivação revela o problema ...

Fig. 7.1.2

Aqui está uma gramática Prolog alternativa (na forma livre de contexto) para a*bb que também pode ser usada como um gerador

s_1 --> a, b.

a --> [].    % empty production
a --> [a],a.

b --> [b,b].

With this grammar ...

?- s_1(S,[]).
S = [b,b] ;
S = [a,b,b] ;
S = [a,a,b,b] ;
...

A propósito, a produção vazia (2ª regra gramatical) será carregada como a seguinte cláusula -- o que significa não consumir nada (ao analisar) ou não gerar nada ...

a(A,A).

Exercício 7.1 Explique por que essa gramática irá gerar sequências.

Exercício 7.2 Especifique uma gramática Prolog para a linguagem de sequências consistindo em 'a' seguidos por um número igual (zero ou mais) de 'b'. Lembre-se de que essa linguagem é livre de contexto, mas não regular.

Para linguagens não livres de contexto, pode-se usar gramáticas Prolog com parâmetros -= um dispositivo inteligente -- objetivos do Prolog entre colchetes, incorporados -- para especificar informações de contexto (ou outras). Por exemplo, considere a seguinte gramática Prolog para sequências de números iguais de 'a' seguidos por 'b' seguidos por 'c' ...

s2 --> a(N), b(N), c(N).

a(0) --> [].
a(M) --> [a],
         a(N),
         {M is N + 1}.  % embedded Prolog Goal

b(0) --> [].
b(M) --> [b],
         b(N),
         {M is N + 1}.

c(0) --> [].
c(M) --> [c],
         c(N),
         {M is N + 1}.

Exercício 7.1.3 Carregue a gramática s2 e teste com várias entradas, como analisador e gerador. Além disso, consulte a lista do Prolog para ver como os objetivos incorporados são tratados.

Veja Também

• Código do Prolog para esta seção.
• 7.2 Gramática do Prolog para estruturas simples de frases em inglês
• Prolog Tutorial Sumário