algorithm - 有没有一种方法或算法可以将 DCG 转换为 Prolog 中的正常定性子句？

Question

我是 Prolog 的新手，我想了解如何将文法从 DC​​G 翻译成普通的定语从句。 我知道 DCG 表示法只是 Prolog 中普通定语子句的语法糖。我开始描述正常的确定语法和 DCG 之间的一些相似之处，但未能应用相同的模式，所以我想问是否有一些我遗漏的规则或可能有效的转换算法。

这是我正在研究的语法，这是我为翻译该语法所做的工作:

expr --> term, addterm.
addterm --> [].
addterm --> [+], expr.
term --> factor, multfactor.
multfactor --> [].
multfactor --> [*], term.
factor --> [I], {integer(I)}.
factor --> ['('], expr, [')'].

这个文法实际上是检查算术运算的句法正确性。 第一条规则实际上很容易转换，因为它的模式类似于普通的确定文法，第四条规则也是如此。但是我对其他四个一无所知。这是我如何转换规则:

expr(E0,E) :- term(E0,E1), addterm(E1,E).

Answer 1

如果您的 Prolog 系统提供了一个 expand_term/2 内置谓词，您可以使用 usually 将语法规则扩展为子句。例如:

?- expand_term((a --> b, c), Clause).
Clause = (a(_G1012, _G1013):-b(_G1012, _G1028), c(_G1028, _G1013)).

要获得更具可读性的输出(并且仅为此目的)，请尝试:

?- expand_term((a --> b, c), Clause), numbervars(Clause, 0, _).
Clause = (a(A, B):-b(A, C), c(C, B)).

numbervars/3 是大多数 Prolog 系统上的事实上的标准谓词。