上下文无关文法可空性判定的Prolog代码转Datalog实现咨询

标准Datalog原生不支持复合项、列表类型，也不需要借助字符串处理即可实现该逻辑，核心思路是将文法的产生式结构拆为扁平的关系存储，完全遵循原Prolog代码的可空性判定逻辑。

1. 基础关系定义 #

1.1 EDB（外延数据库，需提前导入的事实） #

• non_terminal(X)：声明X为非终结符
• terminal(X)：声明X为普通终结符
• epsilon(X)：声明X为空串终结符
• production(ProdId, Lhs)：表示编号为ProdId的产生式左部为非终结符Lhs
• prod_symbol(ProdId, Pos, Sym)：表示编号为ProdId的产生式，第Pos位的符号为Sym（位置从1开始计数）
• prod_length(ProdId, MaxPos)：表示编号为ProdId的产生式总长度为MaxPos（可预生成，也可通过规则推导）

1.2 IDB（内涵数据库，推导规则） #

// 1. 空串直接可空
nullable_sym(S) :- epsilon(S).

// 2. 辅助谓词：产生式前N位符号全部可空
// 边界条件：0位前缀天然可空
prod_prefix_nullable(ProdId, 0) :- production(ProdId, _).
// 递推规则：前N位可空 + 第N+1位符号可空 → 前N+1位可空
prod_prefix_nullable(ProdId, N1) :-
    prod_prefix_nullable(ProdId, N),
    N1 = N + 1,
    prod_symbol(ProdId, N1, S),
    nullable_sym(S).

// 3. 整条产生式可空 = 所有位置符号都可空
prod_nullable(ProdId) :-
    prod_length(ProdId, M),
    prod_prefix_nullable(ProdId, M).

// 4. 非终结符可空 = 任意一条产生式可空
nullable_sym(X) :-
    non_terminal(X),
    production(ProdId, X),
    prod_nullable(ProdId).

2. 示例验证 #

以文法S → AB | ε, A → ε, B → a为例，对应的EDB事实如下：

non_terminal(s). non_terminal(a). non_terminal(b).
terminal(a). epsilon(epsilon).

% 产生式1：S → ε
production(p1, s). prod_symbol(p1, 1, epsilon). prod_length(p1, 1).
% 产生式2：S → A B
production(p2, s). prod_symbol(p2, 1, a). prod_symbol(p2, 2, b). prod_length(p2, 2).
% 产生式3：A → ε
production(p3, a). prod_symbol(p3, 1, epsilon). prod_length(p3, 1).

最终推导结果：nullable_sym(s)、nullable_sym(a)为真，符合预期。

3. 疑问解答 #

• 标准Datalog确实不支持复合项（如rule(z,[d])）和列表类型，上述方案完全规避了这两类特性，所有主流Datalog实现（Soufflé、LogicBlox等）都兼容
• 无需使用字符串存储规则，字符串处理方案不仅性能更低，还会引入额外的解析复杂度，扁平关系是该场景的标准实现方式
• Datalog原生的最小不动点语义天然避免了循环推导问题，无需额外添加非递归校验逻辑

内容的提问来源于stack exchange，提问作者Node.JS