% earley.pl
% -------------------
% Luiz Arthur Pagani
% arthur@ufpr.br

%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Algoritmo de Earley   %
%      baseado no de      %
% Covington 1994: 178-183 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- dynamic aresta/4.

:- unknown(_,fail).

analisa(Exp) :-
   abolish(aresta/4),
   writeln('Começa com:'),
   armazena(aresta(início, [Cat], Exp, Exp)),
   processa(Exp),
   aresta(Cat, [], Exp, []),
   Cat \= início, nl,
   write('-- Categoria = '),
   write(Cat),
   fail.

processa([]) :- !.
processa(Exp) :-
   nl, writeln('Previsão:'),
   previsão(Exp),
   nl, writeln('Varredura:'),
   varredura(Exp, RestExp),
   nl, writeln('Completamento:'),
   completamento(RestExp),
   processa(RestExp).

previsão(Exp) :-
   aresta(_, [Cat | _], _, Exp),
   prevê(Cat, Exp),
   fail.
previsão(_).

prevê(CatLER, Exp) :-
   regra(CatLER, [CatLDR | CatsLDR]),
   armazena(aresta(CatLER, [CatLDR | CatsLDR], Exp, Exp)),
   prevê(CatLDR, Exp),
   fail.
prevê(Cat, Exp) :-
   regra(Cat, []),
   armazena(aresta(Cat, [], Exp, Exp)),
   completa(Cat, Exp, Exp),
   fail.
prevê(_, _).

varredura([Pal | Pals], Pals) :-
   aresta(CatMeta, [Cat | Cats], Exp, [Pal | Pals]),
   CatMeta \== início,
   palavra(Cat, Pal),
   armazena(aresta(CatMeta, Cats, Exp, Pals)),
   fail.
varredura([_ | Palavras], Palavras).

completamento(RestExp) :-
   aresta(Cat, [], Exp, RestExp),
   completa(Cat, Exp, RestExp),
   fail.
completamento(_).

completa(Cat, Exp, RestExp) :-
   aresta(CatMeta, [Cat | Cats], OutraExp, Exp),
   CatMeta \== início,
   armazena(aresta(CatMeta, Cats, OutraExp, RestExp)),
   Cats == [],
   completa(CatMeta, OutraExp, RestExp),
   fail.
completa(_, _, _).

armazena(Aresta) :-
   Aresta =.. [aresta, Cat, Cats, Exp, RestExp],
   \+ (aresta(CatHiper, CatsHiper, Exp, RestExp),
       subsumes_chk(CatHiper, Cat),
       subsumes_chk(CatsHiper, Cats)),
   asserta(Aresta),
   write(' - '),
   writeln(Aresta).

% Carrega gramática (regras e léxico)
:- [gram].