解析 Prolog 中的表达式并返回抽象语法

我必须编写 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)
  ).

它找到了正确的答案，但也返回不遵循关联性或运算顺序的答案。

ex)

parse( [ num(3), plus, num(2), star, num(1) ], T ). 

也返回

mult(add(integer(3), integer(2)), integer(1))

and

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：我发现了一个用 Prolog 编写的语法解析器（http://www.cs.sunysb.edu/~warren/xsbbook/node10.html）。有没有一种方法可以修改它以打印语法的左手推导（“打印”是指 Prolog 解释器将输出“T=[正确答案]”）

去除左递归将推动您走向基于 DCG 的语法。

但有一个有趣的替代方法：实施自下而上解析。

这在 Prolog 中有多难？好吧，正如佩雷拉和希伯在他们精彩的书中所展示的那样 “Prolog 和自然语言分析”非常简单：来自第 6.5 章

Prolog 默认提供自上而下、从左到右、回溯解析算法 DCG。

众所周知，这种自上而下的解析算法会循环往复 左递归规则（参见程序2.3的例子）。

尽管技术是可用的 能够从上下文无关语法中删除左递归，这些技术不是 很容易推广到 DCG，此外，它们还可以通过以下方式增加语法大小： 大因素。

作为替代方案，我们可以考虑实现自下而上的解析方法 直接在 Prolog 中。在各种可能性中，我们将在这里考虑左角 方法是其对 DCG 的一种修改。

为了编程方便，左角 DCG 解释器的输入语法以 DCG 符号的细微变化表示。的右侧 规则以列表的形式给出，而不是文字的连词。因此规则是单元子句 的形式，例如

s ---> [np, vp].

or

optrel ---> [].

终结符由 word(w,PT) 形式的字典单元子句引入。

考虑在继续之前完成讲座（按标题查找免费书籍条目）信息页).

现在让我们尝试编写一个自下而上的处理器：

:- op(150, xfx, ---> ).

parse(Phrase) -->
    leaf(SubPhrase),
    lc(SubPhrase, Phrase).

leaf(Cat) --> [Word], {word(Word,Cat)}.
leaf(Phrase) --> {Phrase ---> []}.

lc(Phrase, Phrase) --> [].

lc(SubPhrase, SuperPhrase) -->
    {Phrase ---> [SubPhrase|Rest]},
    parse_rest(Rest),
    lc(Phrase, SuperPhrase).

parse_rest([]) --> [].
parse_rest([Phrase|Phrases]) -->
    parse(Phrase),
    parse_rest(Phrases).

% that's all! fairly easy, isn't it ?

% here start the grammar: replace with your one, don't worry about Left Recursion
e(sum(L,R)) ---> [e(L),sum,e(R)].
e(num(N)) ---> [num(N)].

word(N, num(N)) :- integer(N).
word(+, sum).

例如，产生

phrase(parse(P), [1,+,3,+,1]).
P = e(sum(sum(num(1), num(3)), num(1))) 

注意使用的左递归语法是e ::= e + e | num