一个简单的计算器
2.1 简介
构建编译器或解释器的第一步是将源代码解析成树状结构。大多数解析工作都可以通过递归的方式完成，一旦你学会了如何进行解析，就可以解析大多数计算机语言。
解析是编译器中比较枯燥的部分，而且大多数实际应用的编程语言都需要花费大量精力来进行解析。幸运的是，有一种语法可以用最少的工作量来解析，那就是S表达式（sexpr）。我们将使用它来节省时间。
2.2 S表达式
一个S表达式要么是一个用括号括起来的嵌套列表，要么是一个不可分割的元素，称为 “原子”。一些例子如下：
;; 原子
a
123
;; 列表
(a)
(a b c d)
;; 嵌套列表
(a ((b) c))它自然地表示了一棵树，而大多数解析工作就是将字符串表示转换为树状结构，所以为什么不直接使用S表达式作为语法呢？特别是当S表达式比其他选择更简单、更容易解析的时候。
除了明显的树状结构外，基于S表达式的语法通常使用前缀运算符，而不是中缀运算符。考虑以下情况：
中缀运算符：
1 + 2 * 3前缀运算符：
(+ 1 (* 2 3))中缀运算符由于不同的运算符优先级而变得复杂 —— 而前缀运算符则不存在这个问题。当前缀运算符在我们需要进一步解析时也更容易处理。这就是为什么我在本书中使用S表达式。如果你喜欢挑战，你可以尝试使用其他语法，比如类似C语言的带中缀运算符的语法。
我们将实现以下运算符：
二元运算符：(op a b)。
算术运算：
(+ 1 2)
(- 1 2)
(* 1 2)
(/ 1 2)比较运算：
(lt 1 2)，小于。
(gt 1 2)，大于。
(eq 1 2)，等于。
(ne 1 2)，不等于。布尔运算：
(and a b)
(or a b)一元运算符：
(- a)，取负。
(not a)，布尔非。条件运算：(? expr-cond expr-then expr-else)。
例如，(? (lt 1 2) "yes" "no") 的结果是 “yes”。
(print a b c)2.3 开始编码
一个S表达式将被解析成Python列表或者Python字符串。例如，S表达式 (a b (+ 1 2)) 将被解析成：
["a", "b", ["+", ["val", 1], ["val", 2]]]请注意，S表达式中的数字或字符串与符号a或b不同，它们被 ["val", x] 结构包裹着，这一点稍后会解释。
函数parse_expr将输入字符串和输入中的当前偏移量（idx）作为参数。它在解析过程中推进偏移量，直到遇到错误或者S表达式结束。
要解析一个S表达式，第一步是确定它是一个原子还是一个列表，这通过查看第一个非空白字符来完成。
def parse_expr(s: str, idx: int):
idx = skip_space(s, idx)
if s[idx] == '(':
# 一个列表
...
elif s[idx] == ')':
raise Exception('括号错误')
else:
# 一个原子
...如果它是一个列表，递归地解析，直到遇到右括号。
def parse_expr(s: str, idx: int):
idx = skip_space(s, idx)
if s[idx] == '(':
# 一个列表
idx += 1
l = []
while True:
idx = skip_space(s, idx)
if idx >= len(s):
raise Exception('括号不匹配')
if s[idx] == ')':
idx += 1
break
idx, v = parse_expr(s, idx)
l.append(v)
return idx, l
elif s[idx] == ')':
raise Exception('括号错误')
else:
# 一个原子
start = idx
while idx < len(s) and (not s[idx].isspace()) and s[idx] not in '()':
idx += 1
if start == idx:
raise Exception('程序为空')
return idx, parse_atom(s[start:idx])任何非空白字符都被视为原子的一部分。
def skip_space(s, idx):
while idx < len(s) and s[idx].isspace():
idx += 1
return idx由于我们要计算已解析的S表达式，从原子中提取诸如数字和字符串之类的值是有意义的。列表头部的 “val” 字符串用于区分已解析的值和其他原子（符号）。
# 布尔值、数字、字符串或一个符号
def parse_atom(s):
# 待办事项：实际实现此函数
import json
try:
return ['val', json.loads(s)]
except json.JSONDecodeError:
return s上面的函数只是一个占位符，我们将在后面的章节中弃用它。
正如我们所看到的，解析的模式是：
- 1. 查看开头的内容并决定下一步操作。
- 2. 必要时进行递归。
即使对于像C或Java这样更复杂的语言，它们的语法也可以用这种方式进行解析。尽管这一点此时你可能还不太清楚。
最后，我们需要检查输入是否已完全处理：
def pl_parse(s):
idx, node = parse_expr(s, 0)
idx = skip_space(s, idx)
if idx < len(s):
raise ValueError('存在多余内容')
return node2.4 表达式求值
计算一个S表达式非常简单：
- 1. 查看列表中的第一个元素并确定操作是什么。
- 2. 递归地计算其余元素。
- 3. 执行操作。
def pl_eval(node):
if len(node) == 0:
raise ValueError('列表为空')
# 布尔值、数字、字符串等
if len(node) == 2 and node[0] == 'val':
return node[1]
# 二元运算符
import operator
binops = {
'+': operator.add,
'-': operator.sub,
'*': operator.mul,
'/': operator.truediv,
'eq': operator.eq,
'ne': operator.ne,
'ge': operator.ge,
'gt': operator.gt,
'le': operator.le,
'lt': operator.lt,
'and': operator.and_,
'or': operator.or_,
}
if len(node) == 3 and node[0] in binops:
op = binops[node[0]]
return op(pl_eval(node[1]), pl_eval(node[2]))
# 一元运算符
unops = {
'-': operator.neg,
'not': operator.not_,
}
if len(node) == 2 and node[0] in unops:
op = unops[node[0]]
return op(pl_eval(node[1]))
# 条件运算
if len(node) == 4 and node[0] == '?':
_, cond, yes, no = node
if pl_eval(cond):
return pl_eval(yes)
else:
return pl_eval(no)
# 打印
if node[0] == 'print':
return print(*(pl_eval(val) for val in node[1:]))
raise ValueError('未知表达式')它基本上是将运算符映射到Python运算符。这个表达式求值器可以用作一个（非传统的）计算器。
def test_eval():
def f(s):
return pl_eval(pl_parse(s))
assert f('1') == 1
assert f('(+ 1 3)') == 4
assert f('(? (lt 1 3) "yes" "no")') == "yes"
assert f('(print 1 2 3)') is None我们已经实现了一个简单的计算器，它是下一章项目的基础 —— 一个带有变量、控制流和函数的编程语言。
