我是语言 prolog 的新手，并且被分配了关于在 prolog 中解析的任务。我需要一些帮助来解决这个问题。
在评估中，我们有语法：
Expr ::= + Expr Expr | * Expr Expr | Num | Xer
Xer ::= x | ^ x Num
Num ::= 2 | 3 | .... a Integer (bigger than 1) ...
令牌^与数学中的相同。5^5等于25。
Parse 需要以两种方式工作：使用实例化列表调用生成 Ast，而使用实例化 Ast 调用应该生成类似的前缀列表。
我的评估说我需要做一个前缀解析来做到这一点：
示例（删除了 Ast 的值）：
?- parse([+, *, 2, x, ^, x, 5 ], Ast), parse(L, Ast).
X = ...,
L = [+, *, 2, x, ^, x, 5]
我也想知道解析树的样子。
Prolog 具有直接处理上下文无关文法的特殊形式：DCG（定句文法）。您的示例几乎立即转换为 DCG：
expr --> [+], expr, expr | [*], expr, expr | num | xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] | [4] | [5].
现在，您已经可以测试句子了：
?- phrase(expr, [+, *, 2, x, ^, x, 5 ]).
true ;
false.
?- phrase(expr, [+, *, *, 2, x, ^, x, 5 ]).
false.
你甚至可以像这样生成所有可能的句子：
?- length(L, N), phrase(expr, L).
L = [2],
N = 1 ;
L = [3],
N = 1 ;
...
最后，您可以将抽象语法树添加到您的定义中。
expr(plus(A,B)) --> [+], expr(A), expr(B).
expr(mul(A,B)) --> [*], expr(A), expr(B).
expr(Num) --> num(Num).
expr(Xer) --> xer(Xer).
xer(var(x)) --> [x].
xer(pow(var(x),N)) --> [^], [x], num(N).
num(num(2)) --> [2].
num(num(3)) --> [3].
num(num(4)) --> [4].
num(num(5)) --> [5].
所以现在您可以根据需要使用它：
?- phrase(expr(AST), [+, *, 2, x, ^, x, 5 ]), phrase(expr(AST),L).
AST = plus(mul(num(2), var(x)), pow(var(x), num(5))),
L = [+, *, 2, x, ^, x, 5] ;
false.
只是一个挑剔：DCGs 的接口谓词phrase/2不是parse/2.