项目:一个小小的解释器
这是一个成长仪式:写一个读取一门语言并运行它的程序。你的语言是算术,但你会用构建真正解释器的方式来构建它,所以 2 + 3 * 4 得到 14,而不是 20。Python 在这里帮不了你:你要自己解析这个字符串,不用 eval()。
两个阶段。首先是分词:把原始字符串变成一个干净的片段列表。"2 + 30" 变成 ["2", "+", "30"]。走过各个字符,跳过空格,把 + - * / ( ) 中的每一个作为单独的词元输出,并把一串数字(和一个点)收集成一个数字词元。一个意外的字符就是一个 ValueError。
然后是求值,使用递归下降:每个优先级一个小函数,每个都调用下面结合得更紧的那一个。正是这种结构编码了运算顺序:
def parse_expr(): # lowest precedence: + and -
value = parse_term()
while peek() in ("+", "-"):
op = advance()
value = value + parse_term() if op == "+" else value - parse_term()
return value
def parse_term(): # higher: * and /
value = parse_factor()
while peek() in ("*", "/"):
...
def parse_factor(): # highest: a number, or ( expr )
if peek() == "(":
advance(); value = parse_expr()
# then expect and consume the matching )
...
return float(advance())因为 parse_factor 可以为一个带括号的分组再次调用 parse_expr,括号就自然地被处理了,包括嵌套的括号。保留一个小的 pos 光标,带有 peek()(查看当前词元)和 advance()(消费它)。格式错误的输入必须抛出 ValueError:一个悬空的运算符,比如 2 +,一个不配对的 (2 + 3,或者剩下的多余词元。要达到的目标:evaluate('2 + 3 * 4') == 14.0,evaluate('(2 + 3) * 4') == 20.0,嵌套括号,以及在 '2 +' 上抛出异常。按 Run 对几个表达式求值。
写 tokenize(expr)(数字作为字符串词元,加上符号 + - * / ( ),跳过空格,拒绝未知字符)和 evaluate(expr),返回一个 float,它让 * / 优先于 + -,并遵守括号(递归下降或调度场算法)。格式错误的输入必须抛出 ValueError。目标:evaluate('2 + 3 * 4') == 14.0、evaluate('(2 + 3) * 4') == 20.0、嵌套括号,以及在 '2 +' 上抛出异常。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。