Prolog - 解析 [英] Prolog - Parsing
问题描述
我是语言序言的新手,并获得了有关在序言中解析的任务.我需要一些帮助来解决问题.
I'm new to the language prolog and have been given an assignment regarding parsing in prolog. I need some help in solving the problem.
在评估中,我们有语法:
In the assingment we have the grammar:
Expr ::= + Expr Expr | * Expr Expr | Num | Xer
Xer ::= x | ^ x Num
Num ::= 2 | 3 | .... a Integer (bigger than 1) ...
标记 ^
与数学中的相同.5^5
等于 25
.
The token ^
is the same as in math. 5^5
equals 25
.
Parse 需要双向工作:使用实例化列表进行调用以生成 Ast,而具有实例化 Ast 的调用应该生成类似的前缀列表.
Parse needs to work both ways: a call with an instantiated list to generate an Ast, while a call with an instantiated Ast should generate similar prefix list.
我的评估说我需要做一个前缀解析来做到这一点:
示例(删除了 Ast 的值):
My assingment says that I need to make a prefix parse that does this:
Example(with the value of Ast removed):
?- parse([+, *, 2, x, ^, x, 5 ], Ast), parse(L, Ast).
X = ...,
L = [+, *, 2, x, ^, x, 5]
我也想知道解析树的样子.
I would also like to know how the parse tree will look like.
推荐答案
Prolog 有一个特殊的形式来直接处理上下文无关文法:DCGs(定句文法).您的示例几乎立即转换为 DCG:
Prolog has a particular formalism to handle context-free grammars directly: DCGs (Definite Clause Grammars). Your example translates almost immediately into a DCG:
expr --> [+], expr, expr | [*], expr, expr | num | xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] | [4] | [5].
现在,您已经可以测试句子了:
Now, you already can test sentences:
?- phrase(expr, [+, *, 2, x, ^, x, 5 ]).
true ;
false.
?- phrase(expr, [+, *, *, 2, x, ^, x, 5 ]).
false.
您甚至可以像这样生成所有可能的句子:
You can even generate all possible sentences like so:
?- length(L, N), phrase(expr, L).
L = [2],
N = 1 ;
L = [3],
N = 1 ;
...
最后,您可以将抽象语法树添加到您的定义中.
And, finally, you can add the abstract syntax tree to your definition.
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].
所以现在你可以随意使用它了:
So now you can use it as desired:
?- 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
.
Just a nitpick: The interface predicate to DCGs is phrase/2
not parse/2
.
这篇关于Prolog - 解析的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!