Implementação de
Analisadores Gramaticais por
Deslocamento e Redução (AGDR)
Sobre a análise gramatical por deslocamento e
redução, consultar agdr.
(Como estou usando a mesma sigla -- AGDR -- tanto para a análise
quanto para o analisador gramatical por deslocamento e
redução, convém lembrar que a diferença
pode ser estabelecida, já que "o AGDR" é o analisador e
"a AGDR" é a análise.)
De Covington
Em seu livro, Covington apresenta uma implementação em
Prolog de um AGDR em Prolog. Apesar de não ser um AGDR
clássico, porque não necessita de um oráculo,
não apresentando portanto conflitos de
deslocamento-redução ou
redução-redução, esta
implementação não entre em regressão
infinita com regras de estrutura sintagmática com
recursão à esquerda. O programa que executa a
análise é o seguinte (Covington
1994:
159):
% Bottom-up
shift-reduce parser
% parse(+S,
?Result)
% parses input string S, where Result
% is list of categories to which it reduces.
parse(S, Result) :-
shift_reduce(S, [], Result).
% shift_reduce(+S, +Stack, ?Result)
% parses input string S, where Stack is
% list of categories parsed so far.
shift_reduce(S, Stack, Result) :-
shift(Stack, S, NewStack, S1), % fails
if S = []
reduce(NewStack, ReducedStack),
shift_reduce(S1, ReducedStack, Result).
shift_reduce([], Result, Result).
%
shift(+Stack, +S, -NewStack, -NewS)
%
shifts first element from S onto Stack.
shift(X, [H|Y], [H|X], Y).
% reduce(+Stack, -ReducedStack)
% repeatedly reduces beginning of Stack
% to form fewer, larger constituents.
reduce(Stack, ReducedStack) :-
brule(Stack, Stack2),
reduce(Stack2, ReducedStack).
reduce(Stack, Stack).
% Phrase structure rules
brule([vp, np | X], [s | X]).
brule([n, d | X], [np | X]).
brule([np, v | X], [vp | X]).
brule([Word | X], [Cat | X]) :-
word(Cat, Word).
% Lexicon
word(d, the).
word(n, dog). word(n, dogs).
word(n, elephant). word(n, elephants).
word(v, chase). word(v, chases).
word(v, see). word(v, sees).
Duas Pequenas Revisões no AGDR de
Convington
Ao executar o programa acima, para uma sentença como "the dog
sees the elephant" (com ?- parse([the,
dog, sees, the, elephant], Result).), por exemplo, o analisador
efetivamente chega a uma resposta adequada: Result = [s].
No entanto, se solicitarmos as respostas alternativas que o analisador
ainda é capaz de oferecer, vamos perceber que ele responde com
um grande número de soluções completamente
inadequadas, como Result = [vp, np],
Result = [np,
v, np], Result = [n, d, v,
np], ... desfazendo passo-a-passo as operações de
redução.
Isso se deve ao fato de que uma parte importante da
condição de término da análise gramatical
por deslocamento e redução não tenha sido
incluída no analisador: a exigência de que a
análise só tenha sido bem-sucedida se a pilha contiver um
único símbolo categorial, e não apenas que a fila
tenha sido esgotada. A inclusão desta condição
é muito simples: ao invés da cláusula
shift_reduce([], Result, Result)., bastaria escrever
shift_reduce([], [Result], Result)., pois a simples
exigência de que a lista que representa a pilha contivesse um
único elemento seria suficiente.
Uma segunda revisão proposta aqui não se deve tanto a uma
imprecisão da implementação, mas antes a uma
pequena divergência de concepção entre a
perspectiva lingüística e a computacional sobre o
analisador gramatical por deslocamento e redução,
apresentada em agdr:
revisão.
Para implementar esta concepção mais
lingüisticamente motivada, a operação de
reconhecimento lexical ao invés de ser feita durante a
redução (brule([Word | X],
[Cat | X]) :- word(Cat, Word).), deve ser feita no deslocamento (shift(Stack,
[Word|Words], [Category|Stack], Words) :- word(Category, Word).).
A nova versão revista do mesmo programa seria:
% Bottom-up
shift-reduce parser
% parse(+S,
?Result)
% parses input string S, where Result
% is list of categories to which it reduces.
parse(S, Result) :-
shift_reduce(S, [], Result).
% shift_reduce(+S, +Stack, ?Result)
% parses input string S, where Stack is
% list of categories parsed so far.
shift_reduce(S, Stack, Result) :-
shift(Stack, S, NewStack, S1), % fails
if S = []
reduce(NewStack, ReducedStack),
shift_reduce(S1, ReducedStack, Result).
shift_reduce([], [Result], Result).
% shift(+Stack, +S, -NewStack, -NewS)
% shifts first element from S onto Stack.
shift(Stack, [Word|Words], [Category|Stack], Words) :-
word(Category, Word).
% reduce(+Stack, -ReducedStack)
% repeatedly reduces beginning of Stack
% to form fewer, larger constituents.
reduce(Stack, ReducedStack) :-
brule(Stack, Stack2),
reduce(Stack2, ReducedStack).
reduce(Stack, Stack).
% Phrase structure rules
brule([vp, np | X], [s | X]).
brule([n, d | X], [np | X]).
brule([np, v | X], [vp | X]).
% Lexicon
word(d, the).
word(n, dog). word(n, dogs).
word(n, elephant). word(n, elephants).
word(v, chase). word(v, chases).
word(v, see). word(v, sees).
Adaptação do AGDR revisto
de Convington para DCG e
Português
O AGDR acima pode ser facilmente transposto para DCG, reposicionando
devidamente os argumentos que controlam a fila com a expressão,
e algumas vezes introduzindo a variável que falta para fazer a
diferença de lista. Abaixo apresenta-se esta
transposição, adaptando-se ainda para o português,
tanto as próprias definições dos predicados que
executam a análise, quanto a língua da expressão a
ser analisada.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
Analisador gramatical %
% por
deslocamento e redução %
%
em
DCG
%
%
para português %
%
baseado no de Covington %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
analisa(+Expressão, ?Resultado)
%
inicia o processo de análise da Expressão,
% com a
pilha vazia,
% de
forma que em Resultado apareça
% a
lista de categorias a que ela se reduz
analisa(Expressão,
Resultado) :-
analisa([], Resultado, Expressão, []).
%
analisa(+Expressão, +Pilha, ?Resultado)
%
analisa a Expressão, sendo que a Pilha
%
contém a lista das categorias já analisadas
analisa(Pilha,
Resultado) -->
desloca(Pilha,
NovaPilha),
% falha se Expressão = []
{reduz(NovaPilha, PilhaReduzida)},
analisa(PilhaReduzida, Resultado).
analisa([Resultado],
Resultado) --> [].
%
desloca(+Pilha, +Expressão, -NovaPilha,
-RestoDaExpressão)
%
desloca a categoria da próxima Palavra para a NovaPilha
desloca(Pilha,
[Categoria|Pilha]) --> [Palavra],
{palavra(Palavra, Categoria)}.
%
reduz(+Pilha, -PilhaReduzida)
% reduz
repetidamente o topo da Pilha
% para
formar constituintes constituintes maiores
reduz(Pilha,
PilhaReduzida) :-
regra_invertida(Pilha, PilhaIntermediária),
reduz(PilhaIntermediária, PilhaReduzida).
reduz(Pilha,
Pilha).
%
regra_invertida(+LDR, ?LER)
% uma
regra de estrutura sintagmática como A --> B C
%
é representada como "regra_invertida([b, c | Resto], [a |
Resto])."
regra_invertida([sv,
sn | Resto], [s | Resto]).
% S --> SN SV
regra_invertida([n,
det | Resto], [sn | Resto]).
% Sn --> Det N
regra_invertida([sn,
v | Resto], [sv | Resto]).
% SV --> V SN
%
Léxico
palavra(o,
det).
palavra(menino,
n).
palavra(bolo,
n).
palavra(comeu,
v).
De Matthews
Há uma outra proposta de implementação em Prolog,
um pouco diferente da de Covington, feita por Matthews. A proposta (Matthews
1998:
219-220) é extremamente simples, e tem o seguinte formato:
:- op(1200, xfx,
==>).
parse(Parse, String) :-
parse([], Parse, String - []).
parse([s(Parse)], Parse, [] -[]).
parse(Stack, Parse, [Word|String] - String1) :-
word(Word, Cat),
parse([Cat|Stack], Parse, String - String1).
parse([Cat2, Cat1|Stack], Parse, String - String1) :-
(Cat ==> [Cat1, Cat2]),
parse([Cat|Stack], Parse, String - String1).
s(s(NP, VP)) ==> [np(NP), vp(VP)].
np(np(Det, N)) ==> [det(Det), n(N)].
vp(vp(V, NP)) ==> [v(V), np(NP)].
word(the, det(det(the))).
word(snow, n(n(snow))).
word(road, n(n(road))).
word(blocked, v(v(blocked))).
Nesta implementação, como na do Covington acima, o AGDR
não enfrenta nunca nenhum tipo de conflito; mas, ao
contrário do outro, o deslocamento tem prioridade absoluta em
relação à redução. Mas ainda ao
contrário da implementação de Covington, nesta
já se encontra a compartimentação entre as
expressões e as categorias lingüísticas propostas
acima.
Assim, uma conseqüência desta implementação
é que a análise sintática só começa
efetivamente depois de toda a análise lexical ter sido executada
(na de Covington, a relação entre o processamento
sintático e o lexical era incremental, e não estritamente
serial como neste). Contudo, isso poderia ser facilmente resolvido
invertendo a ordem entre a primeira e a segunda cláusula da
definição do predicado parse/2.
Essa inversão resolveria também a questão da
recursividade interna das reduções, já que na
versão original só poderia ocorrer duas
reduções consecutivas depois que não houvesse mais
nenhum deslocamento possível.
Além disso, ainda como no AGDR de Covington, aqui também
não teria sido necessário exigir na cláusula de
término (parse([s(Parse)],
Parse, [] -[]).) que a expressão analisada seja
necessariamente uma sentença; para garantir que ela seja uma
expressão totalmente conexa, basta impor que o primeiro
argumento do predicado nesta cláusula seja uma lista com apenas
um elemento.
Revisão e adaptação do AGDR de Matthews para
DCG e português
Como o AGDR de Matthews já recorre à técnica de
diferença de lista, sua adaptação para DCG
é imediata. Apresentaremos abaixo, então, esta
adaptação, adotando as pequenas adaptações
propostas acima, traduzindo os predicados para o português e
adotando o português também como língua da
gramática.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
Analisador gramatical %
% por
deslocamento e redução %
%
em
DCG
%
%
para português %
%
baseado no de Matthews %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
Definição do operador da regra gramatical
:- op(1200, xfx,
==>).
%
inicialização
analisa(Análise,
Expressão) :-
analisa([], Análise, Expressão, []).
%
condição de término
analisa([Análise], Resultado) --> [],
{Análise =.. [_, Resultado]}.
%
redução
analisa([SubAnálise2,
SubAnálise1|Pilha], NovaPilha) -->
{Análise ==> [SubAnálise1, SubAnálise2]},
analisa([Análise|Pilha], NovaPilha).
% deslocamento
analisa(Pilha,
NovaPilha) -->
palavra(Análise),
analisa([Análise|Pilha], NovaPilha).
%
Gramática
s(s(SN, SV)) ==> [sn(SN), sv(SV)].
sn(sn(Det,
N)) ==> [det(Det), n(N)].
sv(sv(V, SN))
==> [v(V), sn(SN)].
%
Léxico
palavra(det(det(o))) --> [o].
palavra(n(n(bolo)))
--> [bolo].
palavra(n(n(menino)))
--> [menino].
palavra(v(v(comeu)))
--> [comeu].
