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

Question

我是 Prolog 的新手，我想了解如何将文法从 DCG 翻译成普通的定语从句。我知道 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 系统上的事实上的标准谓词。

Answer 2

你走对了！继续前进，你会得到这样的东西：

expr(Xs0,Xs) :-                         % expr -->
   term(Xs0,Xs1),                       %    term,
   addterm(Xs1,Xs).                     %    addterm.

addterm(Xs0,Xs) :-                      % addterm --> 
   Xs0 = Xs.                            %    [].
addterm(Xs0,Xs) :-                      % addterm -->
   Xs0 = [+|Xs1],                       %    [+], 
   expr(Xs1,Xs).                        %    expr. 

term(Xs0,Xs) :-                         % term --> 
   factor(Xs0,Xs1),                     %    factor,
   multfactor(Xs1,Xs).                  %    multfactor.

multfactor(Xs0,Xs) :-                   % multfactor -->
   Xs0 = Xs.                            %    [].
multfactor(Xs0,Xs) :-                   % multfactor -->
   Xs0 = [*|Xs1],                       %    [*],
   term(Xs1,Xs).                        %    term.  

factor(Xs0,Xs) :-                       % factor --> 
   Xs0 = [I|Xs],                        %    [I],
   integer(I).                          %    {integer(I)}.
factor(Xs0,Xs) :-                       % factor --> 
   Xs0 = ['('|Xs1],                     %    ['('], 
   expr(Xs1,Xs2),                       %    expr,
   Xs2 = [')'|Xs]. `                    %    [')'].

Answer 3

某些 Prolog 系统将 DCG 转换为子句的方式与@repeat 和@PauloMoura 的答案中的方式不同：终端与正在 analyzed/generated 的列表成员的直接统一被替换通过调用谓词 'C'/3。例如

a(X) --> b(X), [x, y], c(X).

翻译成

a(A,B,C) :-
  b(A,B,D),
  'C'(D,x,E),
  'C'(E,y,F),
  c(A,F,C).

这个谓词在那些系统中被预定义为在那些答案中通过子句

进行统一

'C'([X|S],X,S).

但用户可以根据需要重新定义。

这是 DCG 定义的一部分，首先在 Fernando Pereira 和 David Warren 的论文用于语言分析的定句语法中提出，在人工智能, 13, 1980，这是与 Alain Colmerauer 等人的不同之处之一。之前的论文 Metamorphosis Grammars。使用 'C'/3 谓词，最初命名为 connects，使得 DCG 独立于字符串 parsed/generated 的表示方式：在上面给出的翻译中，没有任何要求变量 B 到 F 代表列表，并且 'C'/3 可以重新定义以将它们解释为其他类型的术语。为了避免效率损失，本文建议在使用列表的情况下在编译期间对 DCGs 子句进行预处理。

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

Is there a way or an algorithm to convert DCG into normal definite clauses in Prolog?

algorithm

parsing

prolog

grammar

dcg