基于Prolog验证形式语言G1的合法句子识别问题排查

问题背景 #

你定义了上下文无关文法G1：

G1 = { V , T , S , P }, 
where V = { S , E } 
      T = { x , y , z } 
      P = { S→E , E→xE , E→yE , E→z }

并想用Prolog的DCG（确定子句文法）验证集合{xz, xy, xyz, xyxz, z, xxyz, Xyz}中的句子是否属于该语言的合式公式。你写了这段DCG代码：

s --> e.
e --> [x], e.
e --> [y], e.
e --> [z].

但测试时发现只有s([z], R)能成功返回R = []，像s([xz], R)、s([x], R)都返回false，这是怎么回事呢？

问题根源分析 #

其实你遇到的问题主要来自两个细节错误：

1. 句子的列表表示错了 #

在Prolog里，[xz]是一个只包含单个原子xz的列表，但你的文法里的终结符是单个字符x、y、z——也就是说，正确的句子应该是单个字符组成的列表。比如句子xz对应的应该是[x,z]，或者用双引号包裹的"xz"（大多数Prolog实现会自动把双引号字符串解析成字符列表）。

你调用s([xz], R)时，Prolog会尝试把原子xz和规则里的[x]/[y]/[z]匹配，显然完全不匹配，所以返回false。

2. 完整句子的匹配逻辑没搞对 #

要验证一个句子是合式公式，必须确保整个句子都被匹配完——也就是剩余的字符列表为空。正确的调用方式应该是s(Sentence, [])，而不是只写s(Sentence, R)（除非你故意留剩余字符，但这里我们要的是完整匹配）。

修正后的验证方案 #

1. 确认代码有效性 #

你的DCG代码本身没问题，只要确保箭头是Prolog标准的-->（不是转义的-->）就可以正常使用。

2. 正确的测试调用 #

我们逐个验证目标集合里的句子：

• z：?- s([z], []). 或者 ?- s("z", []). → 成功（返回true）
• xz：?- s([x,z], []). 或者 ?- s("xz", []). → 成功
• xy：?- s([x,y], []). 或者 ?- s("xy", []). → 失败，因为文法要求推导必须以z结尾，xy没有z，不符合规则
• xyz：?- s([x,y,z], []). 或者 ?- s("xyz", []). → 成功
• xyxz：?- s([x,y,x,z], []). 或者 ?- s("xyxz", []). → 成功
• xxyz：?- s([x,x,y,z], []). 或者 ?- s("xxyz", []). → 成功
• Xyz：?- s(['X',y,z], []). → 失败，因为文法里的终结符是小写x，大写X不匹配

3. 批量验证的小技巧 #

如果想一次性检查所有句子，可以写个辅助谓词：

check_sentence(Sentence) :-
    (s(Sentence, []) -> 
        format("Sentence ~w is valid.~n", [Sentence])
    ; 
        format("Sentence ~w is NOT valid.~n", [Sentence])
    ).

check_all :-
    check_sentence("z"),
    check_sentence("xz"),
    check_sentence("xy"),
    check_sentence("xyz"),
    check_sentence("xyxz"),
    check_sentence("xxyz"),
    check_sentence("Xyz"). % 这里"Xyz"会被解析为['X','y','z']，和文法的小写x不匹配

调用check_all.就能直接看到所有句子的验证结果了。

总结 #

• 别把多字符句子写成单个原子的列表，要用单个字符的列表或者双引号字符串。
• 验证合式公式一定要匹配整个列表，记得调用s(Sentence, [])。
• 文法里的终结符是小写的，大写字符不会被匹配，所以Xyz是非法的。

内容的提问来源于stack exchange，提问作者Xueqi Zhao