Prolog期末练习题：为比特串集合Ln定义3元谓词s/3对应的DCG

你要实现的DCG本质是匹配正则表达式(0|1)*1(0|1){n-1}，拆分后可以拆解为三个独立的匹配单元：

• 前缀：任意长度（包括0）的0/1比特序列
• 标志位：固定为1的比特，就是要求的倒数第n位
• 后缀：刚好n-1位的0/1比特序列

% 匹配单个比特：0或1
bit --> [0].
bit --> [1].

% 匹配指定长度N的比特序列
bits(0) --> [].
bits(N) --> 
    { N > 0, N1 is N - 1 },
    bit,
    bits(N1).

% 主谓词：匹配属于Ln的比特串
s(N) -->
    % 先校验输入N为正整数，计算后缀需要的长度
    { integer(N), N > 0, SuffixLen is N - 1 },
    % 匹配任意长度的前缀比特
    bits(_),
    % 匹配倒数第N位的1
    [1],
    % 匹配固定长度的后缀比特
    bits(SuffixLen).

你可以直接用题目要求的调用方式测试：

• 正例：s(2, [1,0], [])返回真，对应n=2时倒数第2位为1
• 正例：s(3, [0,1,0,1], [])返回真，倒数第3位是1
• 反例：s(2, [0,0], [])返回假，没有符合要求的标志位
• 生成用例：s(2, S, [])会枚举所有符合要求的比特串

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