1. DCG — 定从句文法

DCG 描述一个序列。操作上，DCG 可用于解析、生成、补全和检查列表形式的序列。

前置：回溯与控制流 | 难度：★★★ | 后续：元编译器

写代码最烦什么？处理字符串。拆句子、切单词、手动管理状态、边界条件报错……

Prolog 说——你写规则，剩下的我来。

DCG（定从句文法）就是干这个的。这章学完，你能用 10 行写一个 CSV 解析器，用一个算术表达式求值器秀翻同事，甚至——同一套规则既能解析句子也能生成句子，给规则剩下 Prolog 搞定。

先看个酷的。

1.1. Show Off：4 行句子解析

历史上 Prolog 起源于自然语言处理系统，DCG 是这起源留下的最重要遗产。看最基本的例子：

%% 语法：句子 -> 名词短语 + 动词短语
s --> np, vp.

np --> [the], [cat].
vp --> [sat], [on], [the], [mat].

保存 dcg_basic.pl，加载查询：

?- phrase(s, [the, cat, sat, on, the, mat]).
X = [1,2,3,4] .

嗯嗯嗯！4 行规则搞定一个句子解析器。不用递归、不用削列表，就写规则。

Prolog 时刻 — DCG 能用同一套规则做解析和生成。给规则，剩下的 Prolog 搞定。

phrase/2 是 DCG 的入口：第一个参数是语法规则名，第二个是待解析的列表。

1.2. 前置知识：差量列表

好看归好看，DCG 背后到底发生了什么？要理解这一点，先看 Prolog 里一个经典技巧——差量列表（Difference List）。

形式上写作 [1,2,3|T]-T。不是特殊数据类型，就是一个额外的未绑定变量标记"已消耗/未消耗"的边界。关键不在于那一对值，在于它们的差。

1.2.1. X-Y 模式

?- X = [1,2,3|T]-T.
X = [1,2,3|T]-T.

1.2.2. O(1) 拼接

append_dl(X-Y, Y-Z, X-Z).

对比常规 append——遍历整个第一个列表 O(n)。差量列表直接变量绑定搞定：

?- A = [1,2|T1]-T1, B = [3,4|T2]-T2, append_dl(A, B, C), C = X-[].
A = [1,2,3,4|_]-[3,4|_],   % 简化输出
B = [3,4|_]-_,
C = [1,2,3,4]-[].

1.2.3. flatten 对比

常规 flatten——递归 + append 三层：

flatten([], []).
flatten([H|T], Flat) :-
    flatten(H, FH),
    flatten(T, FT),
    append(FH, FT, Flat).
flatten(X, [X]).

差量列表版——直接绑定：

flatten_dl([], T-T).
flatten_dl([H|T], X-Z) :-
    flatten_dl(H, X-Y),
    flatten_dl(T, Y-Z).
flatten_dl(X, [X|T]-T).

查询：

?- flatten([1,[2,3],[4]], F).
F = [1,2,3,4].

?- flatten_dl([1,[2,3],[4]], X-[]), X = [1,2,3,4].
true .

思路从"遍历拼接"变成了"打通路径"——每次递归把未绑定的尾变量传给下一层，由最后一层绑定。所以 flatten_dl 的最后一个子句是 [X|T]-T 而不是 [X]——它在预留通道。

1.2.4. 与 DCG 的联系

DCG 的两个隐藏参数本质上就是差量列表：

%% DCG 规则
s --> np, vp.

%% 展开后——差量列表传递
s(S0, S) :- np(S0, S1), vp(S1, S).
%%    S0 是输入列表，S 是剩余列表
%%    中间结果通过 S1 串联

phrase/2 调用时传入完整列表，期望最终剩余为 []——等价于差量列表 List-[] 模式。

理解差量列表，DCG 的隐藏参数就不再"隐藏"了——S0, S1, S 只是显式串联的差量列表拼接。

1.3. DCG 的本质

每个 DCG 规则编译为带两个额外参数的 Prolog 谓词。

s --> np, vp.

编译后等价于：

s(S0, S) :- np(S0, S1), vp(S1, S).

S0 是剩余输入，S 是消耗后的剩余。phrase/2 只是把完整列表传进去，期望剩余为空。

终端符 [word] 编译为：

[word] --> [word].
% 等价于：
[word](S0, S) :- S0 = [word|S].

1.4. 实战 1：解析 CSV

理论够了，干点实际的。写个 CSV 解析器——一行 CSV，逗号分隔字段：

%% 解析一行 CSV：字段间用逗号分隔
csv_line(Fields) --> field(Fields).

field([F|Fs]) --> value(F), separator_or_end, field(Fs).
field([])     --> [].

value(V) --> token(V).

separator_or_end --> [','].
separator_or_end --> [].

%% 单个 token（不含逗号的连续字符列表）
token([C|Cs]) --> [C], { C \= 0'' }, token(Cs).
token([])     --> [].

测试：

?- phrase(csv_line(F), "a,b,c").
F = [[97], [98], [99]] .

输出 ASCII 码列表。转成原子：

?- phrase(csv_line(F), "a,b,c"), maplist(atom_codes, Atoms, F).
F = [[97], [98], [99]],
Atoms = [a, b, c].

看到 separator_or_end 那条规则了吗？两个分支：逗号或空。这就是 DCG 的"可选"模式——空规则 [] 表示"什么都不消耗就成功"，对应语法中的 ε（空产生式）。

1.5. 实战 2：简单算术表达式

DCG 天然适合解析嵌套结构。四则运算解析器——这次带运算符优先级：

expr(E)   --> term(T), expr_rest(T, E).
expr_rest(T0, E) --> [+], term(T), expr_rest(T0+T, E).
expr_rest(T0, E) --> [-], term(T), expr_rest(T0-T, E).
expr_rest(E, E)  --> [].

term(T)   --> factor(F), term_rest(F, T).
term_rest(F0, T) --> [*], factor(F), term_rest(F0*F, T).
term_rest(F0, T) --> [/], factor(F), term_rest(F0//F, T).
term_rest(T, T)  --> [].

factor(N) --> [N], { number(N) }.
factor(E) --> ['('], expr(E), [')'].

查询：

?- phrase(expr(E), [1,+,2,*,'(',3,+,4,')']), V is E.
E = 1+2*(3+4),
V = 15 .

注意 is/2 求值——DCG 建的语法树可以延迟计算。构建和求值分离，这种结构在其他语言里叫 AST（抽象语法树），Prolog 里就是——一个嵌套项而已。

1.6. DCG 与宏

DCG 本质是编译期语法变换——--> 在 Prolog 代码加载前被展开成带两个差量列表参数的普通谓词。这种"写 DSL，生成普通代码"的思路，在其他语言里叫宏。

1.6.1. C 的宏（#define）

纯文本替换，预处理阶段展开。危险——参数可能多次求值：

#define SQUARE(x) ((x)*(x))
int y = SQUARE(++a); // 展开为 ((++a)*(++a)) —— 未定义行为

1.6.2. Lisp/Scheme 的宏

操作 AST 而非文本——模式匹配 + 代码重写，比 C 安全：

(define-syntax my-when
  (syntax-rules ()
    ((my-when test body ...)
     (if test (begin body ...)))))

1.6.3. Rust 的声明宏（macro_rules!）

模式匹配式语法变换，写起来像 DCG 规则：

macro_rules! vec {
    ( $( $x:expr ),* ) => {
        {
            let mut v = Vec::new();
            $( v.push($x); )*
            v
        }
    };
}

1.6.4. 对比

特性	DCG	C 宏	Lisp 宏	Rust 宏
作用域	DCG 规则内	全局文本	代码 AST	模式匹配
安全性	高（语义明确）	低（文本替换）	中高	中高
展开时机	编译期	预处理	编译期	编译期
表达能力	受限（差量列表）	任意文本	任意 AST	有限 AST
运行时开销	零	零	零	零

DCG 是 Prolog 特有的宏系统——受限但有明确语义（差量列表上下文），不像 C 宏危险，不像 Lisp 宏通用。在"写语法规则"这个场景下，比任何其他语言的宏都自然。

1.7. DCG debug 技巧

DCG 编译后的隐藏参数让调试有点棘手。几个常用方法：

1. listing/1 看展开结果

?- listing(s/4).
s(A, B) :- np(A, C), vp(C, B).

2. 加 debug 打印（{} 包装普通谓词）

s --> np, { writeln(parsed_np) }, vp.

花括号里的代码是普通 Prolog，不参与差量列表展开。

3. phrase/3 看剩余

?- phrase(s, [the, cat, sleeps, and, dog, barks], Rest).

Rest 显示未被消费的部分，定位匹配失败。

4. listing/1 列出差量列表谓词定义

在 swipl 提示符下运行 listing/1：

:- listing(dcg_difflist/1).

% TODO: verify 这个设置是否还适用于当前版本

参考：The Power of Prolog - DCG — Markus Triska 的 DCG 深度讲解。实际 DCG 项目分析（bencode 编解码器）见「庖丁解牛」cs1 篇。

1.8. 总结

DCG 是 Prolog 最强大的语法糖之一。统一了解析和生成——同一套规则既能解析句子也能生成句子。记住几点：

--> 编译为带两个差量列表参数的普通谓词
[terminal] 匹配字面量，{code} 嵌入普通 Prolog
phrase/2 是标准入口，phrase/3 可获取剩余
listing/1 看展开是理解 DCG 的最好方式

DCG