Analisando uma expressão no Prolog e retornando uma sintaxe abstrata
Eu tenho que escrever parse (Tkns, T) que leva em uma expressão matemática na forma de uma lista de tokens e encontra T, e retorna uma declaração representando a sintaxe abstrata, respeitando a ordem das operações e associatividade.
Por exemplo,
?- parse( [ num(3), plus, num(2), star, num(1) ], T ).
T = add(integer(3), multiply(integer(2), integer(1))) ;
No
Eu tentei implementar + e * da seguinte forma
parse([num(X)], integer(X)).
parse(Tkns, T) :-
( append(E1, [plus|E2], Tkns),
parse(E1, T1),
parse(E2, T2),
T = add(T1,T2)
; append(E1, [star|E2], Tkns),
parse(E1, T1),
parse(E2, T2),
T = multiply(T1,T2)
).
Que encontra a resposta correta, mas também retorna respostas que não seguem associatividade ou ordem de operações.
ex)
parse( [ num(3), plus, num(2), star, num(1) ], T ).
também retorna
mult(add(integer(3), integer(2)), integer(1))
e
parse([num(1), plus, num(2), plus, num(3)], T)
retorna o equivalente a 1 + 2 + 3 e 1+ (2 + 3) quando deve retornar apenas o primeiro.
Existe uma maneira de fazer isso funcionar?
Edit: mais informações: eu só preciso implementar +, -, *, /, negate (-1, -2, etc.) e todos os números são inteiros. Uma dica foi dada que o código será estruturado de forma semelhante à gramática
<expression> ::= <expression> + <term>
| <expression> - <term>
| <term>
<term> ::= <term> * <factor>
| <term> / <factor>
| <factor>
<factor> ::= num
| ( <expression> )
Apenas com negado implementado também.
Edit2: Eu encontrei um analisador gramatical escrito em Prolog (http://www.cs.sunysb.edu/~warren/xsbbook/node10.html). Existe uma maneira que eu poderia modificá-lo para imprimir uma derivação da mão esquerda de uma gramática ("imprimir" no sentido de que o interpretador Prolog irá produzir "T = [a resposta correta]")