Prolog - 解析

Question

我是语言序言的新手,并且已经获得了关于在prolog中解析的任务.我需要一些帮助来解决问题.

在协助中我们有语法:

Expr ::= + Expr Expr | * Expr Expr | Num | Xer  
Xer  ::= x | ^ x Num  
Num  ::= 2 | 3 | .... a Integer (bigger than 1) ...

令牌^与数学中的令牌相同.5^5等于25.

解析需要双向工作:使用实例化列表调用以生成Ast,而使用实例化Ast调用应生成类似的前缀列表.

我的assingment说我需要做一个前缀解析,这样做:
示例(删除Ast的值):

?- parse([+, *, 2, x, ^, x, 5 ], Ast), parse(L, Ast).  
X = ...,  
L = [+, *, 2, x, ^, x, 5]  

我也想知道解析树的样子.

Answer 1

Prolog有一种特殊的形式主义来直接处理无上下文语法:DCG(Definite Clause Grammars).您的示例几乎立即转换为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.

只是一个挑剔:DCG的界面谓词phrase/2不是parse/2.