Разбор выражения в Прологе и возврат абстрактного синтаксиса
Я должен написать parse (Tkns, T), который принимает математическое выражение в виде списка токенов и находит T, и возвращает инструкцию, представляющую абстрактный синтаксис, соблюдая порядок операций и ассоциативность.
Например,
?- parse( [ num(3), plus, num(2), star, num(1) ], T ).
T = add(integer(3), multiply(integer(2), integer(1))) ;
No
Я попытался реализовать + и * следующим образом
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)
).
Который находит правильный ответ, но также возвращает ответы, которые не соответствуют ассоциативности или порядку операций.
ех)
parse( [ num(3), plus, num(2), star, num(1) ], T ).
также возвращает
mult(add(integer(3), integer(2)), integer(1))
а также
parse([num(1), plus, num(2), plus, num(3)], T)
возвращает эквивалент 1 + 2 + 3 и 1+ (2 + 3), когда он должен возвращать только первое.
Есть ли способ, которым я могу заставить это работать?
Изменить: дополнительная информация: мне нужно только реализовать +, -, *, /, отрицание (-1, -2 и т. Д.) И все числа являются целыми числами. Намек был дан, что код будет структурирован аналогично грамматике
<expression> ::= <expression> + <term>
| <expression> - <term>
| <term>
<term> ::= <term> * <factor>
| <term> / <factor>
| <factor>
<factor> ::= num
| ( <expression> )
Только с реализованным отрицанием.
Edit2: я нашел грамматический парсер, написанный на прологе (http://www.cs.sunysb.edu/~warren/xsbbook/node10.html). Есть ли способ, которым я мог бы изменить его, чтобы вывести левосторонний вывод грамматики («print» в том смысле, что интерпретатор Prolog выведет «T = [правильный ответ]»)