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

Question

我想知道如何将此 Prolog 代码转换为在 Datalog 中工作。

我认为它不适用于 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 似乎没有帮助。

也就是说，你的序言代码也写得不是很好。该语言允许您编写看似单个 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 的特殊符号，它既不是终结符也不是非终结符，并且被硬编码为可为空。
最困难的部分是表达这样一个事实，即如果 至少一个 符号是 ，则产生式不可为 null =]不 可为空。这使用辅助谓词来正确嵌套否定。

示例：

% 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)
}

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

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

Prolog to Datalog code conversion that uses lists

prolog

datalog