课程大纲 第 209 课,共 250 课 · 项目:构建真东西
项目:构建真东西

项目:一个小小的解释器

这是一个成长仪式:写一个读取一门语言并运行它的程序。你的语言是算术,但你会用构建真正解释器的方式来构建它,所以 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 +' 上抛出异常。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。