猴子都能敲出来的极简布尔解释器
好像也没什么是猴子敲不出来的
这篇文章是为了讲解本学期《离散数学》课程的最后一个大作业《根据命题逻辑解决实际问题》而作的。这个作业的本质其实就是要求我们编写一个命题求解器，能对给定的命题求值，从而对含有变量的命题求出所有能使其为真的变量取值。
说实话，刚听到这个作业我还有点兴奋，因为正正好在撸和编译器相关的东西，总算有点用武之地了。我实现的这个求解器参考了 60-lines-of-python/calculator，也在 Github 上开源了，欢迎去戳！diredocks/discrete-math-lab-fdzc - resolver
正经解释器该长什么样？
一个“正经”的解释器（或编译器）通常包括两个核心组件：分词器（tokenizer） 和 解析器（parser）。
- 分词器负责将原始文本解析为解释器内部能够理解的“词法单元”，比如数字、符号、关键字等，同时会自动忽略掉诸如注释、空行等对语义无影响的部分。
- 接下来，解析器会根据这些词法单元构建出抽象语法树（AST），这棵树描述了表达式的结构和语义关系。
在此基础上，不同语言的编译/解释器会将 AST 翻译为目标平台可执行的形式：
- 编译成汇编：直接运行在目标平台的本地环境（比如 x86、ARM）。这种方式性能最佳，但生成的程序具有平台依赖性。
- 翻译为字节码：由语言的虚拟机解释执行。只要目标平台上存在该虚拟机，就可以运行字节码程序。
当然，现实中的解释器还会涉及如 JIT（即时编译）、AOT（预编译）等性能优化策略。但这些都不是我们今天的重点，因为我们要实现的是一种非常简洁的 即时解释器（on-the-fly interpreter）——在分词的同时完成解析与求值。虽然没有多少优化空间，但胜在结构清晰、实现简单。
架构设计：我们如何构建解释流程？
与其说我们要设计一个解释器，不如说我们要先分析清楚，究竟要处理怎样的问题。简单来说，我们希望能够解析并计算类似下面这样的布尔表达式：
(!0&1)|(1+1)&(0-1)
这个表达式看起来复杂，其实可以用一种名为 EBNF 的语言描述。EBNF 本身非常强大，不过为了简洁起见，我们这里使用一个简化版本来描述整个计算过程：
exp ::= term [ [ '&' | '|' ] term ]*
term ::= factor [ [ '+' | '-' ] factor ]*
factor ::= <bool> | '(' exp ')' | '-' factor
看不懂吗？没关系，我第一次看也看不懂。我来解释一下其中的符号和组合，先从第一个句子开始：
::=表示定义规则。等号左边是规则的名称，右边是这个规则所对应的表达式结构。一个规则通常可以嵌套引用其他规则。[...]表示“候选组”，即括号内的内容是可选的。如果组内使用|分隔，表示只能选其中之一；若无分隔符，则表示需要包含所有元素。[...]*表示这个部分可以重复零次或多次，通常在解析时会通过循环处理。<bool>是我们的操作数，只有True或者False。
理解了这些符号后，我们就能解释第一个规则：
exp是一个表达式，必须至少包含一个term；- 然后是一个可选的部分，即
[ '&' | '|' ] term，这个部分可以重复出现任意次； - 也就是说，一个
exp可能是term，也可能是term & term，或者term & term | term，依此类推。
举几个例子帮助理解：
term：合法的exp，最简单的形式；term & term：也是合法的exp，带一个连接操作；term & term | term：依旧合法，这里的连接操作出现了两次。
是不是开始有点感觉了？接下来的规则也是按照同样的方式定义的：从最小的单位 factor 开始，逐步组合成更复杂的结构。
你可能已经注意到：我们到现在还没有真正对 term 进行求值。那么，表达式的最终值是怎么计算出来的呢？
这正是递归定义发挥作用的地方。 当我们在解析 exp 的过程中遇到一个 term，就会进入 term 的求解阶段。解析 term 时，我们需要它的组成部分——factor 的值，于是我们继续向下，进入 factor 的解析与求解。
这个过程会一路递归下去，直到我们遇到无法再继续递归的基本单位，比如一个布尔值或者括号内的表达式。这个时候，我们就可以返回一个“真实的值”，然后将这个值逐层传回上一层的解析过程。
整个求值流程就像一棵树从叶子结点开始计算，逐步向上汇总结果，直到根结点完成整个表达式的求解。我们直接利用了编程语言提供的栈结构——递归是天生先进先出、后进后出的。
那么，如何实现呢？
讲完了理论，接下来就要动手实现了。虽然听起来像是“脏活累活”，但其实并不复杂——整个求解器最终只用了大约 60 行代码就完成了。
我们从主角 parse 函数开始。这个函数接受一个字符串类型的表达式，返回一个布尔值作为最终的计算结果。它的内部逻辑也很直接：先初始化一个内部变量 line 来保存当前待解析的表达式，然后调用 _exp 开始顶层解析。
def parse(self, expr: str) -> bool:
self.line = expr
result = self._exp()
if self.line != "":
raise SyntaxError(
f"Unexpected character after expression: '{self.line[0]}'"
)
return result
上一节我们提到过“分词器”（tokenizer），也就是将字符串拆解成有意义片段的工具。在这段代码中，分词的核心是一个辅助函数 _is_next，定义如下：
import re
def _is_next(self, regexp: str) -> bool:
m = re.match(r'\s*' + regexp + r'\s*', self.line)
if m:
self.current = m.group().strip()
self.line = self.line[m.end():]
return True
return False
这个函数的作用是判断当前表达式是否符合给定的正则模式，并在匹配成功时做出相应的处理。它的参数 regexp 是一个正则表达式，用来匹配我们期望的符号。注意它会在前后加上 \s*，也就是忽略前后所有的空白字符，提升解析的容错性。
如果匹配成功，它会：
- 将当前匹配到的符号保存到
self.current； - 从原始表达式
self.line中剔除这部分匹配内容； - 然后返回
True，表示成功匹配；
如果没有匹配成功，就什么都不做，返回 False，表达式保持原样留给后续的解析逻辑继续处理。
接下来是我们根据语法规则实现的三条解析函数，每个函数都严格遵循我们前面定义的语法规则。
def _exp(self) -> bool:
result = self._term()
while self._is_next("[&|]"):
match self.current:
case "&":
result = self._term() and result
case "|":
result = self._term() or result
return result
_exp：首先解析一个 term，然后循环匹配 & 或 |。每匹配到一个运算符，就再次解析一个 term 并与已有结果进行组合求值。
def _term(self) -> bool:
result = self._factor()
while self._is_next("[+-]"):
match self.current:
case "+":
result = result == self._factor()
case "-":
result = self._factor() or (not result)
return result
_term：结构类似，不过这里的运算符是 + 和 -，它们的语义与布尔等价和或操作略有不同，具体行为在匹配分支中体现。
def _factor(self) -> bool:
if self._is_next(r"[0-1]*\.?[0-1]+"):
return bool(int(self.current))
if self._is_next("!"):
return not self._factor()
if self._is_next("[(]"):
result = self._exp()
if not self._is_next("[)]"):
raise SyntaxError(
f"Expected ')' but got '{'<EOL>' if not self.line else self.line[0]}'"
)
return result
raise SyntaxError(
f"Expected operand or '-' or '(' but got '{'<EOL>' if not self.line else self.line[0]}'"
)
_factor：负责处理最基本的元素。它可以是：
- 一个布尔值（用正则匹配
0或1）； - 一个逻辑非操作
!，递归解析其后面的因子； - 一个括号包裹的表达式，递归调用
_exp并确保匹配闭合的)； - 若都不匹配，则抛出语法错误。
每个解析层级都只关心自己该解析的部分，复杂表达式的求值自然通过递归完成，语法与求值过程紧密对应。同时你应该也注意到了，优先级最高的符号被我们写到了递归的最内侧（factor），也就是说，递归不仅帮助我们保证了某一层的正确性，还确保不同层之间求值顺序的正确性！ （快说：谢谢递归）
Read-eval-print, Loop!
至此，我们已经介绍完整个求解器模块的架构和实现了，但要想让最终用户使用这个模块，我们还需要为其设计一个命令行界面。
一般来说，解释型语言都会附带一个 REPL 编程环境供用户调试程序，例如你在终端直接运行 python 就会启动 Python 的 REPL。这个术语最早来自于 Lisp 语言，意思是 读取（Read），求值（Eval），输出（Print），循环（Loop）。
我们这里的迷你解释器也不例外。为了实现这个 REPL，让我们来看看刚刚求解器模块的接口 Resolver.parse。这个方法接受一个形如 (1&0)|!0|(0&1) 的表达式，并返回这个表达式的结果（真或假）。聪明的小朋友可能发现了，说好的 p,q,r 呢？
别急，我们既然已经有个可用的求解器，剩下的就只是把需要求解的、带有变项命题中的变项替换为所有可能的值就行了。下面这个函数就是来实现这个功能的：
def generate_binary_replacements(expr) -> list[str]:
letters = sorted(set(re.findall(r"[a-zA-Z]", expr)))
combinations = itertools.product("01", repeat=len(letters))
return [
"".join(mapping[c] if c in mapping else c for c in expr)
for combo in combinations
if (mapping := dict(zip(letters, combo)))
]
首先，筛选出表达式中所有的英文字母（包含大小写），去重后排序，存入变量 letters 里。
letters = sorted(set(re.findall(r"[a-zA-Z]", expr)))
然后生成这些字母所能产生的所有 01 组合。
combinations = itertools.product("01", repeat=len(letters))
如果我们有三个不同的符号，则 combinations 中会有：
combinations = [('0', '0', '0'), ('0', '0', '1'), ('0', '1', '0'), ('0', '1', '1'), ('1', '0', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '1', '1')]
然后我们利用 Python 的列表推导式，先遍历 combinations 中的所有组合，然后把每个组合映射到对应的字母上，生成一个映射表。
if (mapping := dict(zip(letters, combo))) # mapping 就是我们的映射表
# 举个栗子
dict(zip(['p', 'q', 'r'], [0, 0, 1])) -> {'p': 0, 'q': 0, 'r': 1}
接着利用这个映射表生成带值的命题。
"".join(mapping[c] if c in mapping else c for c in expr)
# 遍历表达式中每一个字符
for c in expr
# 若 c 是映射表中的键（即要替换的符号），则替换成映射表中对应的值
mapping[c] if c in mapping
# 否则保留 c 本身
else c
试着调用这个函数，我们就得到：
generate_binary_replacements("p-q-!r") ->
['0-0-!0', '0-0-!1', '0-1-!0', '0-1-!1', '1-0-!0', '1-0-!1', '1-1-!0', '1-1-!1']
然后写个循环就行了：
def repl():
calc = Resolver()
while True:
line = input("> ")
if line == "BYE":
print("< bye!")
exit()
lines = generate_binary_replacements(line)
for line in lines:
try:
print(f"< {line}", calc.parse(line))
except SyntaxError as e:
print(f"Syntax Error: {e.msg}")
最后跑起来就像这样：
> p-q-!r
< 0-0-!0 True
< 0-0-!1 False
< 0-1-!0 True
< 0-1-!1 False
< 1-0-!0 True
< 1-0-!1 True
< 1-1-!0 True
< 1-1-!1 False
> BYE
< bye!
说得好，可这还不是作业要求…
感谢你看到这，写到这文章已经有三千多个词了，但是这还不是结尾。233 作业要求我们编写一个更直观的 REPL，用户输入命题和条件，程序返回使所有条件成真的取值，以命题形式输出。
为此，我们首先读入一些命题：
def rep():
props = {}
props_n = int(input("请输入命题的数量: "))
from string import ascii_lowercase
start = ascii_lowercase.index("p") # 从 p 开始
symbols = ascii_lowercase[start:]
if props_n > len(symbols):
raise ValueError("命题数量超过可用的符号数量 (p-z)。")
print(f"输入 {props_n} 个命题: ")
for n in list(range(0, props_n)):
inp = input(f"{symbols[n]} = ").strip()
if inp:
props[symbols[n]] = inp
首先，输入命题的数量。然后程序会生成“符号-命题映射列表”（symbols），如果发现命题数量大于符号能表示的数量，就报错退出。之后再输入命题，每个符号对应一个命题。输入的命题存储在 props 字典里。
条件也是一样的，不过这里要注意下条件要加上括号，不然后面用 “&” 拼起来可能会有求值顺序的问题。
conds = []
conds_n = int(input("\n现在你可以输入条件的数量: "))
for n in list(range(conds_n)):
inp = input("> ").strip()
if inp:
conds.append("(" + inp + ")")
if not conds:
raise ValueError("未输入条件。")
然后就来了个大的：
def generate_binary_replacements(
expr: str, letters: list[str]
) -> list[tuple[str, dict[str, str]]]:
combinations = itertools.product("01", repeat=len(letters))
return [
("".join(mapping[c] if c in mapping else c for c in expr), mapping.copy())
for combo in combinations
if (mapping := dict(zip(letters, combo)))
]
cond_expressions = generate_binary_replacements(
"&".join(conds), sorted(props.keys())
)
这又是想干啥呢？首先，由于我们这里有多个条件，就要把每个条件用 “&” 连接起来（"&".join(conds)）。
其次，之前 REPL 里的替换函数 generate_binary_replacements 没有记录取值，这里则记录了每次替换过后，每个命题符号的取值。
generate_binary_replacements("p-q-!r", ['p', 'q', 'r']) ->
[('0-0-!0', {'p': '0', 'q': '0', 'r': '0'}), ('0-0-!1', {'p': '0', 'q': '0', 'r': '1'}), ('0-1-!0', {'p': '0', 'q': '1', 'r': '0'}), ('0-1-!1', {'p': '0', 'q': '1', 'r': '1'}), ('1-0-!0', {'p': '1', 'q': '0', 'r': '0'}), ('1-0-!1', {'p': '1', 'q': '0', 'r': '1'}), ('1-1-!0', {'p': '1', 'q': '1', 'r': '0'}), ('1-1-!1', {'p': '1', 'q': '1', 'r': '1'})]
可以看到每个项除了替换过后的内容之外，还有对应符号的取值。
至于 sorted(props.keys()) 就是获取每个命题的符号，没啥好说的。
做完这一些过后，我们就可以进入求解和输出环节：
calc = Resolver()
print("\n恭喜你：")
count = 0
for expr, truth_values in cond_expressions:
if calc.parse(expr):
true_props = [props[k] for k, v in truth_values.items() if v == "1"]
if true_props:
count += 1
print(f"方案 {count} ：", end="")
print("，".join(true_props))
print(f"我们一共找到 {count} 个方案")
if count == 0:
print("没有任何组合满足条件，别灰心，或许在另一个宇宙我们有着不同的逻辑。")
刚刚我们费了好大的劲，总算成功生成了所有最终要求解的表达式 cond_expressions，我们现在要做的就是遍历这些表达式，求解每一个表达式：
- 如果结果为”真“，则输出对应的命题
- 否则什么也不做
如果没有任何组合满足条件，别灰心，或许在另一个宇宙我们有着不同的逻辑。
后话
快水到四千个字了，多少诱惑我再水一点（）
我其实很喜欢这个作业，倒不是说它有多难，而是因为它比较有意思。作为一个灵长类动物。我一直比较痴迷这些看上去很酷、很优雅的玩意，虽然有时候感觉并没有什么屌用。我们刚刚搓的玩具没有任何优化，只能很死板的慢慢求值。
关于编译器和解释器我也是个小白，如果有错误欢迎指正。不过，好玩就行。希望大家能多写出来点好玩的东西！