如何将编程语言变量定义文法转换为Prolog识别程序？

刚接触Prolog时确实会觉得和命令式语言差异很大，不过它的声明式特性处理上下文无关文法（CFG）特别顺手，尤其是用确定子句文法（DCG）——这是Prolog专门为语法分析设计的语法，几乎可以直接映射你的文法规则。

第一步：直接映射文法到DCG规则 #

你的文法规则可以直接转写成下面的DCG代码，每个非终结符对应一个DCG谓词，终结符用[token]表示：

% S -> T S | T
s --> t, s.
s --> t.

% T -> char F semicolon | int F semicolon
t --> [char], f, [semicolon].
t --> [int], f, [semicolon].

% F -> id | id G
f --> [id].
f --> [id], g.

% G -> comma F
g --> [comma], f.

第二步：理解DCG的工作方式 #

DCG本质上是Prolog子句的语法糖，它会自动处理输入的token列表。比如s --> t, s会被转换成对应的Prolog子句，负责先匹配t对应的token序列，再匹配剩余部分的s，完全贴合你定义的文法逻辑。

第三步：测试你的例子 #

在Prolog解释器里加载上面的代码后，用phrase/2谓词来测试输入的token序列是否符合文法：

• 测试"char id semicolon"对应的token列表：

  ?- phrase(s, [char, id, semicolon]).
  true.
  

• 测试"int id comma id semicolon char id semicolon"对应的token列表：

  ?- phrase(s, [int, id, comma, id, semicolon, char, id, semicolon]).
  true.
  

• 如果输入不符合文法（比如少了分号），会返回false：

  ?- phrase(s, [char, id]).
  false.
  

额外说明 #

如果你暂时不想用DCG，也可以手动写处理列表的Prolog子句，不过DCG版本显然更易读，完全匹配你的文法结构，非常适合入门。比如手动实现s/1的话：

s(Tokens) :- t(Tokens).
s(Tokens) :- append(TPart, SPart, Tokens), t(TPart), s(SPart).

t([char | Rest]) :- f(FPart), Rest = [semicolon | FPart].
t([int | Rest]) :- f(FPart), Rest = [semicolon | FPart].

f([id]).
f([id | Rest]) :- g(Rest).

g([comma | Rest]) :- f(Rest).

内容的提问来源于stack exchange，提问作者bock.steve