使用列表的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).

关于代码的上下文.这个prolog代码决定上下文无关语法是否为空.

这意味着对于所有的规则(例如，对于生产S，->，ABC，XYZ，规则是: ABC，XYZ )，如果其中任何一个是可空的，那么整个规则是可空的。这相当于OrLattice。 eq Rule.getNDecl().nullable() { for (int i= 0；i< getNumProd()；i++) { if (getProd(i).nullable())返回true；}返回false；} 这意味着对于生产中的所有终端和非终端(例如，对于生产S -> ABC，符号是ABC )，如果它们都是可空的，那么整个规则是可空的。这相当于AndLattice。 eq Prod.nullable() { for (int i= 0；i< getNumSymbol()；i++) { if (!getSymbol(i).nullable())返回false；}返回true；} Epsilon终端是可空的 eq Terminal.nullable() {返回false；} 如果非终端的使用是可空的，则它是空的。 eq NUse.nullable(){返回decl().nullable()；}

原始总和

纸张(免费下载) (第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 (如果我正确理解抽象和代码示例)都是这样做的。

对于Datalog部分，需要将数据合理地表示为事实。考虑一条规则，您可以将其表示为Prolog术语rule(x, [a, b, c])。这不是Datalog，但是通过给这个规则取一个任意名称(如rule1)，您可以表示一系列事实，表示“rule1产生的第一个符号是a”、“rule1产生的第二个符号是b”等等：

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

类似于峭壁的系统的更完整的版本稍微复杂一些，因为规则可以有多个产品，这些产品本身就会产生符号。这是我的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).

对于此联机数据记录，查询nullable_rule(Rule)给出了预期的答案：

{
  nullable_rule(r2)
}

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