使用列表的 Prolog 到 Datalog 代码转换

Question

我想知道如何将此 Prolog 代码转换为在 Datalog 中工作。
我认为它不适用于 Datalog，因为我们不允许使用诸如 nullable(rule(z,[d])) 之类的东西。在数据日志中。另外，我不知道 Datalog 是否允许列表。也许另一种选择是将规则编写为字符串，但我不知道 Datalog 是否允许字符串以及所有需要的字符串函数是否可用。

% rules for nullable

% If we have the rule X -> Y where X does not appear in Y and each component of Y is nullable, then X is nullable
% We need that X does not appear in Y to avoid circular loops (If X is nullable it would be because of a non-circular definition so we are not omitting any case)
nullable(X) :- variable(X), rule(X,Y), \+ member(X, Y), nullable(Y).      % The Y here is a list so we need to define nullable(Y) for lists which is one below

% The empty list is always a nullable list
nullable([]).
% A list is nullable if all of its components are nullable
nullable([X|Y]) :- nullable(X), nullable(Y).

% A rule X -> Y is nullable if Y is nullable
nullable(rule(_,Y)) :- nullable(Y).

关于代码的上下文。
此序言代码确定上下文无关文法是否可为空。

This means for all rules (e.g. for production S -> ABC | XYZ, the rules are: [ABC, XYZ ] ) if ANY of them is nullable then the whole rule is nullable. This is equivalent to OrLattice.

eq Rule.getNDecl().nullable() {
  for (int i = 0; i < getNumProd(); i++) {
    if (getProd(i).nullable())
      return true;
  }
  return false;
}

This means for all terminals and non-terminals in production (e.g. for a production S -> ABC, symbols are ABC ) if ALL of them is nullable then the whole rule is nullable. This is equivalent to AndLattice.

eq Prod.nullable() {
  for (int i = 0; i < getNumSymbol(); i++) {
    if (!getSymbol(i).nullable())
      return false;
  }
  return true;
}

an Epsilon terminal is nullable

eq Terminal.nullable() {  
     return false;
}

non-terminal is nullable if its use is nullable

eq NUse.nullable(){
    return decl().nullable();
}

Original Omplementation
Paper (free to download) (第 14-15 页)

Answer 1

我认为 Prolog 代码会分散注意力。正如您所说，除了原子和变量之外，Datalog 不支持列表和其他 Prolog 术语，因此尝试通过 Prolog 似乎没有帮助。
也就是说，您的 Prolog 代码也写得不是很好。该语言允许您编写看似单一的内容 nullable/1谓词处理符号、产生式和规则。但这并不是一个好主意。给列表变量赋予无用的名称，例如 Y，你也会让自己非常不高兴。 .一个常见的约定是添加一个 s列表变量名的后缀。这是您的 Prolog 代码的更清晰版本:

nullable_nonterminal(X) :-
    variable(X),
    rule(X,Ys),
    \+ member(X, Ys),
    nullable_nonterminals(Ys).

nullable_nonterminals([]).
nullable_nonterminals([X|Xs]) :-
    nullable_nonterminal(X),
    nullable_nonterminals(Xs).

nullable_rule(rule(_,Ys)) :-
    nullable_nonterminals(Ys).

但同样，这不会直接转换为 Datalog。作为一个额外的复杂因素，它引入了循环的手动处理，Datalog 和 CRAG(如果我正确理解抽象和代码示例)都会为您做。
对于数据记录部分，您需要将数据合理地表示为事实。考虑您将表示为 Prolog 术语 rule(x, [a, b, c]) 的规则.这不是 Datalog，但是通过给这个规则一个任意的名字(比如 rule1)，你可以表示一系列的事实，表示“由 rule1 产生的第一个符号是 a”，“由rule1 是 b"等等:

rule(rule1, 1, a).
rule(rule1, 2, b).
rule(rule1, 3, c).

CRAG 类系统的完整版本稍微复杂一些，因为规则可以有多个产生式，这些产生式本身产生符号。这是我的 Datalog 版本，直接从 https://bitbucket.org/jastadd/crag-artifact/src/master/Nullable.jrag 处的示例代码翻译而来:

nullable_symbol(nothing).
nullable_symbol(Symbol) :-
    terminal(Symbol),
    nullable_terminal(Symbol).
nullable_symbol(Symbol) :-
    nonterminal(Symbol),
    nullable_nonterminal(Symbol).

nullable_terminal(_Symbol) :-
    false.
    
nullable_nonterminal(Nonterminal) :-
    rule(_Rule, _Index, Nonterminal, Production),
    nullable_production(Production). 
    
nullable_rule(Rule) :-
    rule(Rule, _Index, _Nonterminal, Production),
    nullable_production(Production). 
    
nullable_production(Production) :-
    not(some_nonnullable_symbol(Production)).
    
some_nonnullable_symbol(Production) :-
    production(Production, _Index, Symbol),
    not(nullable_symbol(Symbol)).

两个注意事项:

这有一个特殊的符号叫做 nothing它既不是终结符也不是非终结符，并且被硬编码为可以为空。

最困难的部分是表达这样一个事实，即如果至少一个符号不可为空，则产生式不可为空。这使用辅助谓词来正确嵌套否定。

例子:

% Example 1: a non-nullable rule
% r1: x --> a b
% where a and b are terminals.
rule(r1, 1, x, p1).

production(p1, 1, a).
production(p1, 2, b).

nonterminal(x).
terminal(a).
terminal(b).

% Example 2: a nullable rule
% r2: eps --> <nothing>
rule(r2, 1, eps, p2).

production(p2, 1, nothing).

nonterminal(eps).

% Example 3: a non-nullable rule
% r3: y --> eps x eps
rule(r3, 1, y, p3).

production(p3, 1, eps).
production(p3, 2, x).
production(p3, 3, eps).

nonterminal(y).

与 this online Datalog查询nullable_rule(Rule)给出了预期的答案:

{
  nullable_rule(r2)
}

例如，如果我们注释掉 production(p3, 2, x).这使得 r3不可为空，查询也正确识别修改后的 r3作为可空。