Gramática de cláusulas definidas - Definite clause grammar

Uma gramática de cláusula definida ( DCG ) é uma forma de expressar a gramática, tanto para linguagens naturais quanto formais , em uma linguagem de programação lógica como o Prolog . Está intimamente relacionado ao conceito de gramáticas de atributos / gramáticas de afixo a partir do qual Prolog foi originalmente desenvolvido. DCGs são geralmente associados com Prolog, mas linguagens semelhantes como Mercury também incluem DCGs. Elas são chamadas de gramáticas de cláusulas definidas porque representam uma gramática como um conjunto de cláusulas definidas na lógica de primeira ordem .

O termo DCG refere-se ao tipo específico de expressão em Prolog e outras linguagens semelhantes; nem todas as formas de expressar gramáticas usando cláusulas definidas são consideradas DCGs. No entanto, todos os recursos ou propriedades dos DCGs serão os mesmos para qualquer gramática representada com cláusulas definidas essencialmente da mesma maneira que no Prolog.

As orações definidas de um DCG podem ser consideradas um conjunto de axiomas onde a validade de uma sentença, e o fato de ela ter uma certa árvore de análise, podem ser considerados teoremas que decorrem desses axiomas. Isso tem a vantagem de fazer com que o reconhecimento e a análise de expressões em uma linguagem se tornem uma questão geral de declarações de comprovação, como as declarações em uma linguagem de programação lógica.

História

A história dos DCGs está intimamente ligada à história do Prolog, e a história do Prolog gira em torno de vários pesquisadores em Marselha, na França, e em Edimburgo, na Escócia. De acordo com Robert Kowalski , um dos primeiros desenvolvedores do Prolog, o primeiro sistema Prolog foi desenvolvido em 1972 por Alain Colmerauer e Phillipe Roussel. O primeiro programa escrito na linguagem foi um grande sistema de processamento de linguagem natural. Fernando Pereira e David Warren da Universidade de Edimburgo também estiveram envolvidos no desenvolvimento inicial do Prolog.

Colmerauer havia trabalhado anteriormente em um sistema de processamento de linguagem chamado Q-systems, que era usado para traduzir entre o inglês e o francês. Em 1978, Colmerauer escreveu um artigo sobre uma maneira de representar gramáticas chamadas gramáticas de metamorfose, que faziam parte da versão inicial do Prolog chamada Marseille Prolog. Neste artigo, ele deu uma descrição formal das gramáticas de metamorfose e alguns exemplos de programas que as usam.

Fernando Pereira e David Warren, dois outros arquitetos pioneiros do Prolog, cunharam o termo "gramática da cláusula definida" e criaram a notação para DCGs que é usada no Prolog hoje. Eles deram crédito pela ideia a Colmerauer e Kowalski, e notaram que os DCGs são um caso especial das gramáticas de metamorfose de Colmerauer. Eles introduziram a ideia em um artigo chamado "Gramáticas de cláusulas definidas para análise de linguagem", onde descrevem DCGs como um "formalismo ... em que as gramáticas são cláusulas expressas de lógica de predicado de primeira ordem" que "constituem programas eficazes da linguagem de programação Prolog ".

Pereira, Warren e outros pioneiros do Prolog escreveram posteriormente sobre vários outros aspectos dos DCGs. Pereira e Warren escreveram um artigo chamado "Parsing as Deduction", descrevendo coisas como o procedimento de prova Earley Deduction usado para análise. Pereira também colaborou com Stuart M. Shieber em um livro chamado "Prolog and Natural Language Analysis", que pretendia ser uma introdução geral à linguística computacional usando programação lógica.

Exemplo

Um exemplo básico de DCGs ajuda a ilustrar o que são e como são.

 sentence --> noun_phrase, verb_phrase.
 noun_phrase --> det, noun.
 verb_phrase --> verb, noun_phrase.
 det --> [the].
 det --> [a].
 noun --> [cat].
 noun --> [bat].
 verb --> [eats].

Isso gera frases como "o gato come o morcego", "um morcego come o gato". Pode-se gerar todas as expressões válidas na linguagem gerada por esta gramática em um interpretador Prolog digitando sentence(X,[]) . Da mesma forma, pode-se testar se uma frase é válida no idioma digitando algo como sentence([the,bat,eats,the,bat],[]) .

Tradução em cláusulas definidas

A notação DCG é apenas um açúcar sintático para cláusulas definidas normais em Prolog. Por exemplo, o exemplo anterior pode ser traduzido no seguinte:

 sentence(A,Z) :- noun_phrase(A,B), verb_phrase(B,Z).
 noun_phrase(A,Z) :- det(A,B), noun(B,Z).
 verb_phrase(A,Z) :- verb(A,B), noun_phrase(B,Z).
 det([the|X], X).
 det([a|X], X).
 noun([cat|X], X).
 noun([bat|X], X).
 verb([eats|X], X).

Listas de diferenças

Os argumentos para cada functor, como (A,B) e (B,Z) são listas de diferenças ; listas de diferenças são uma forma de representar um prefixo de uma lista como a diferença entre seus dois sufixos (o maior incluindo o menor). Usando a notação do Prolog para listas, um prefixo de lista singleton P = [H] pode ser visto como a diferença entre [H|X] e X , e assim representado com o par ([H|X],X) , por exemplo.

Dizer que P é a diferença entre A e B é o mesmo que dizer que append(P,B,A) vale. Ou no caso do exemplo anterior append([H],X,[H|X]) ,.

As listas de diferenças são usadas para representar listas com DCGs por razões de eficiência. É muito mais eficiente concatenar diferenças de lista (prefixos), nas circunstâncias em que podem ser usadas, porque a concatenação de (A,B) e (B,Z) é justa (A,Z) .

Na verdade, append(P,B,A), append(Q,Z,B) acarreta append(P,Q,S), append(S,Z,A) . Isso é o mesmo que dizer que a concatenação de lista é associativa :

A = P + B = P + (Q + Z) = (P + Q) + Z = S + Z = A

Gramáticas não livres de contexto

No Prolog puro , as regras DCG normais sem argumentos extras nos functores, como o exemplo anterior, só podem expressar gramáticas livres de contexto ; há apenas um argumento do lado esquerdo da produção . No entanto, gramáticas sensíveis ao contexto também podem ser expressas com DCGs, fornecendo argumentos extras, como no exemplo a seguir:

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

Este conjunto de regras DCG descreve a gramática que gera a linguagem que consiste em cadeias de caracteres da forma . ${\ displaystyle a ^ {n} b ^ {n} c ^ {n}}$

 s --> symbols(Sem,a), symbols(Sem,b), symbols(Sem,c).
 symbols(end,_) --> [].
 symbols(s(Sem),S) --> [S], symbols(Sem,S).

Este conjunto de regras DCG descreve a gramática que gera a linguagem que consiste em strings da forma , por representar estruturalmente $n$ ${\ displaystyle a ^ {n} b ^ {n} c ^ {n}}$

Representando recursos

Vários recursos linguísticos também podem ser representados de forma bastante concisa com DCGs, fornecendo argumentos extras para os functores. Por exemplo, considere o seguinte conjunto de regras DCG:

 sentence --> pronoun(subject), verb_phrase.
 verb_phrase --> verb, pronoun(object).
 pronoun(subject) --> [he].
 pronoun(subject) --> [she].
 pronoun(object) --> [him].
 pronoun(object) --> [her].
 verb --> [likes].

Esta gramática permite frases como "ele gosta dela" e "ele gosta dele", mas não "ela gosta dele" e "ele gosta dele".

Análise com DCGs

Um exemplo de árvore de análise para esta gramática.

O principal uso prático de um DCG é analisar sentenças de uma dada gramática, ou seja, construir uma árvore de análise. Isso pode ser feito fornecendo "argumentos extras" para os functores no DCG, como nas seguintes regras:

 sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP).
 noun_phrase(np(D,N)) --> det(D), noun(N).
 verb_phrase(vp(V,NP)) --> verb(V), noun_phrase(NP).
 det(d(the)) --> [the].
 det(d(a)) --> [a].
 noun(n(bat)) --> [bat].
 noun(n(cat)) --> [cat].
 verb(v(eats)) --> [eats].

Agora é possível consultar o intérprete para produzir uma árvore de análise de qualquer frase dada:

 | ?- sentence(Parse_tree, [the,bat,eats,a,cat], []).
 Parse_tree = s(np(d(the),n(bat)),vp(v(eats),np(d(a),n(cat)))) ? ;

Outros usos

Os DCGs podem servir como um açúcar sintático conveniente para ocultar certos parâmetros no código em outros lugares, além de aplicativos de análise. Na linguagem de programação declarativamente pura, Mercury I / O deve ser representado por um par de io.state argumentos. A notação DCG pode ser usada para tornar o uso de E / S mais conveniente, embora a notação de variável de estado geralmente seja preferida. A notação DCG também é usada para análise e coisas semelhantes em Mercúrio como no Prolog.

Extensões

Desde que os DCGs foram introduzidos por Pereira e Warren, várias extensões foram propostas. O próprio Pereira propôs uma extensão chamada gramáticas de extraposição (XGs). Esse formalismo pretendia, em parte, tornar mais fácil a expressão de certos fenômenos gramaticais, como a extraposição à esquerda. Pereira afirma: "A diferença entre as regras XG e as regras DCG é que o lado esquerdo de uma regra XG pode conter vários símbolos." Isso torna mais fácil expressar regras para gramáticas sensíveis ao contexto.

Peter Van Roy estendeu DCGs para permitir múltiplos acumuladores.

Outra extensão, mais recente, foi feita por pesquisadores da NEC Corporation, denominada Gramáticas de cláusulas definidas multimodais (MM-DCGs), em 1995. Suas extensões tinham como objetivo permitir o reconhecimento e a análise de expressões que incluem partes não textuais, como imagens.

Outra extensão, chamada de gramáticas de tradução de cláusulas definidas (DCTGs) foi descrita por em 1984. A notação DCTG é muito semelhante à notação DCG; a principal diferença é que se usa em ::= vez de --> nas regras. Foi planejado para lidar com atributos gramaticais convenientemente. A tradução de DCTGs em cláusulas Prolog normais é como a de DCGs, mas 3 argumentos são adicionados em vez de 2.

Languages

In other projects