Gramática de cláusulas definidas

Uma gramática de cláusulas definidas (Definite Clause Grammar - DCG) é um meio de expressar relações gramaticais. É comumente usada com a linguagem de programação Prolog.

parsing e DCGs

No processo de parsing, ao analisar uma stream de entrada, uma ferramenta poderosa para auxiliar nessa análise é a representação dos tokens por diferenças de listas. Diferenças de listas são pares de listas sendo analisadas, onde a lista "verdadeira" consiste na diferença entre a primeira lista e a segunda. Por exemplo, a lista [o, gato] poderia ser representada pelo par [o, gato, caça, o, rato] e [caça, o rato]. Ou, de um modo mais geral, [o, gato | X] e X.

Para analisar uma entrada (já separada em tokens) como

[x, =, 2]

pode-se usar uma manipulação de listas convencional de Prolog: um predicado binário que recebe a lista de entrada como seu primeiro argumento e qualquer resto que sobre depois que a análise se concluir (o resto eventualmente deve ser [] se o parsing for bem sucedido). Isso pode ser feito assim:

sentenca(A,B) :- identificador(A,C), op_atribuicao(C,D), digito(D,B).
identificador([x|R],R).
op_atribuicao([=|R],R).
digito([2|R],R).

A notação das gramáticas de cláusulas definidas (DCG) permitem que esse mesmo analisador seja escrito de um modo mais conveniente:

sentenca --> identificador, op_atribuicao, digito.
identificador --> [x].
op_atribuicao --> [=].
digito --> [2].

Nas implementações de Prolog que dão suporte a DGCs, uma regra definida via -->/2 em vez de :-/2 é expandida pelo pré-processador (expand_term/2, uma facilidade análoga às macros em outras linguagens) de acordo com algumas regras de reescrita bastante diretas, resultando em cláusulas Prolog ordinárias. A diferença mais notável é a adição de dois argumentos para representar a diferença de listas, de modo que o código gerado para os dois exemplos acima se torna idêntico.

Exemplo de parser

Um exemplo maior vai mostrar o potencial de se usar Prolog para parsing.

Dada a sentença expressa em BNF:

<sentenca>       ::=  <parte_instr>
<parte_instr>    ::=  <instrucao> | <parte_instr> <instrucao>
<instrucao>      ::=  <identificador> = <expressao> ;
<expressao>      ::=  <operando> | <expressao> <operador> <operando>
<operando>       ::=  <identificador> | <digito>
<identificador>  ::=  a | b
<digito>         ::=  0..9
<operador>       ::=  + | - | *

Isso pode ser escrito em Prolog usando DCGs (assumindo uma entrada como [a, =, 3, *, b, ;, b, =, 0, ;] etc.):

sentenca   --> instrucao, sentenca_r.
sentenca_r --> [].
sentenca_r --> instrucao, sentenca_r.

instrucao --> identificador, [=], expressao, [;].

expressao --> termo, expressao_r.
expressao_r --> [].
expressao_r --> [+], termo, expressao_r.
expressao_r --> [-], termo, expressao_r.

termo   --> fator, termo_r.
termo_r --> [].
termo_r --> [*], fator, termo_r.

fator --> identificador.
fator --> [D], { (number(D) ; var(D)), between(0, 9, D) }.

identificador --> [a].
identificador --> [b].

Esse programa pode ser usado para testar se uma lista dada está na linguagem gerada por essa gramática:

 ?- sentenca([a,=,1,+,3,*,b,';',b,=,0,';'],[]).
 Yes

Se aumentarmos esses predicados com argumentos adicionais para rastrear os elementos analisados, uma árvore sintática abstrata (abstract sintax tree - AST) da sentença pode ser criada em paralelo com seu parsing:

sentenca(S)   --> instrucao(S0), sentenca_r(S0, S).
sentenca_r(S, S) --> [].
sentenca_r(S0, seq(S0, S)) --> instrucao(S1), sentenca_r(S1, S).

instrucao(atribuicao(Id,E)) --> identificador(Id), [=], expressao(E), [;].

expressao(E) --> termo(T), expressao_r(T, E).
expressao_r(E, E) --> [].
expressao_r(E0, E) --> [+], termo(T), expressao_r(mais(E0, T), E).
expressao_r(E0, E) --> [-], termo(T), expressao_r(menos(E0,T), E).

termo(T)   --> fator(F), termo_r(F, T).
termo_r(T, T) --> [].
termo_r(T0, T) --> [*], fator(F), termo_r(vezes(T0, F), T).

fator(id(ID)) --> identificador(ID).
fator(digito(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D) }.

identificador(a) --> [a].
identificador(b) --> [b].

Exemplo de busca:

?- sentenca(S, [a,=,1,+,3,*,b,;,b,=,0,;], []).
S = seq(atribuicao(a, mais(digito(1), vezes(digito(3), id(b)))), atribuicao(b, digito(0))) ;

A AST é representada usando termos Prolog, podendo ser usadas para aplicar otimizações, para compilar essas expressões para código de máquina, ou para interpretar diretamente essas instruções. Como é típico para a natureza relacional dos predicados, essas definições podem ser usadas tanto para analisar ou gerar sentenças, e também para verificar se uma árvore dada corresponde a uma lista de tokens dada. Usando aprofundamento iterativo para enumerar de forma justa sentenças válidas junto com suas árvores sintáticas correspondentes ("justa" significa que cada sentença arbitrária porém finita será gerada eventualmente), obtemos:

?- length(Ts, _), sentenca(S, Ts, []).
 Ts = [a, =, a, (;)],
 S = atribuicao(a, id(a)) ;
 Ts = [a, =, b, (;)],
 S = atribuicao(a, id(b)) 
 etc.

Ver também

Ligações externas

«Definite Clause Grammars» (em inglês)