:- op(500, xfx, ==>).
:- op(400, xfx, °).

analisa(Expressão) :-
	analisa(1, Final, Expressão, [], Tabela),
	escreve_tabela(Tabela),
	member(arco(1, Categoria ==> _ ° _, Final), Tabela),
	nl,
	write('Análise bem sucedida.'),
	nl, nl,
	write('Categoria da expressão: '),
	write(Categoria),
	nl, nl, fail.

analisa(I, I, [], Resultado, Resultado).
analisa(I, K, Fila, Tabela, Resultado) :-
	desloca(I, J, Fila, Tabela, NovaFila, NovaTabela),
	expande(NovaTabela, TabelaReduzida),
	analisa(J, K, NovaFila, TabelaReduzida, Resultado).

desloca(I, J, [Palavra|Palavras], Tabela, Palavras, [arco(I, Categoria ==> [Palavra] ° [], J)|Tabela]) :-
	Categoria ==> [Palavra],
	succ(I, J).

expande(Tabela, NovaTabela) :-
	member(arco(I, Categoria ==> _ ° [], J), Tabela),
	succ(I, J),
	Categoria1 ==> [Categoria|Categorias],
	\+ member(arco(I, Categoria1 ==> [] ° [Categoria|Categorias], I), Tabela),
	!,
	expande([arco(I, Categoria1 ==> [] ° [Categoria|Categorias], I)|Tabela], NovaTabela).
expande(Tabela, NovaTabela) :-
	member(arco(I, Categoria1 ==> Categorias1 ° [Categoria2|Categorias2], J), Tabela),
	member(arco(J, Categoria2 ==> _ ° [], K), Tabela),
	append(Categorias1, [Categoria2], Categorias3),
	\+ member(arco(I, Categoria1 ==> Categorias3 ° Categorias2, K), Tabela),
	!,
	expande([arco(I, Categoria1 ==> Categorias3 ° Categorias2, K)|Tabela], NovaTabela).
expande(Tabela, Tabela).

s ==> [sn, sv].
sv ==> [v, sn].

sn ==> [pedro].
sn ==> [maria].
v ==> [ama].

escreve_tabela([Arco]) :-
	write(Arco),
	!.
escreve_tabela([Arco|Arcos]) :-
	escreve_tabela(Arcos),
	nl,
	write(Arco).