JustSong Archive Link About
Projects
Categories
Others

Let's Build A Simple Interpreter 学习笔记(Part 1 ~ Part 6)

Tag: interpreter 学习笔记 Posted on 2020-03-14 16:32:45 Edited on 2020-04-12 19:12:33 Views: 116

概述

原教程地址:Let's Build A Simple Interpreter(构建一个简单的解释器)

前六部分主要在做一个计算器,重点在于 Lexer 与 Parser 的构建。

Token 对象

Token 对象只有两个属性,类型和值,同时实现了 __str__ 函数,便于调试。

词法分析部分

Lexer 用途为处理源程序,将其转换为 Token 序列,便于后续处理。

Lexer 对外暴露的接口只有 get_next_token(),其返回值为下一个 token 对象,get_next_token() 函数内部逻辑主要为一个循环体,其一个接一个地读取源程序中的字符,并根据这些字符产生出相应的 Token 对象。

对于单字符的 Token,例如 +,- 等运算符,只取出一个字符即可;然而对于数字类型的 Token,我们需要一个工具函数 integer() 协助处理。

class Lexer(object):
    def __init__(self, text):
        self.text = text  # 存储源程序
        self.pos = 0  # 记录当前已经处理到的位置
        self.current_char = self.text[self.pos]  # 当前正在处理的字符

    def error(self):
        raise Exception('Invalid character')

    def advance(self):  # 该函数用于加载下一个字符(维护 pos 和 current_char 变量)
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None  # Indicates end of input
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):  # 跳过空白字符 
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):  # 将数字字符拼接成数字
        result = ''
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        return int(result)

    def get_next_token(self):  # 供外界调用,按照顺序每次生成一个 Token 提高给调用者
        while self.current_char is not None:  # 内部的主循环,循环自然结束意味着源文件读取完毕,返回 EOF
            if self.current_char.isspace():
                self.skip_whitespace()
                continue

            if self.current_char.isdigit():  # 根据当前字符判断出要生成的 token 类型
                return Token(INTEGER, self.integer())

            if self.current_char == '+':
                self.advance()
                return Token(PLUS, '+')

            if self.current_char == '-':
                self.advance()
                return Token(MINUS, '-')

            if self.current_char == '*':
                self.advance()
                return Token(MUL, '*')

            if self.current_char == '/':
                self.advance()
                return Token(DIV, '/')

            if self.current_char == '(':
                self.advance()
                return Token(LPAREN, '(')

            if self.current_char == ')':
                self.advance()
                return Token(RPAREN, ')')

            self.error()  # 程序执行到这里意味着出现了 unexpected character
        return Token(EOF, None)  # 源文件读取完毕,返回 EOF 

语法分析部分

该部分以之前词法分析产生的 Token 流为输入,输出即算术表达式的值。

具体实现上即 Interpreter 对象,其内置一个 lexer 对象用以提供输入,此外有一个 eat(token_type) 的工具函数,其用于检测当前 token 的类型是否满足期望,若满足则更新 current_token,否则报 unexpected token 的错误。

之后我们根据上下文无关文法构造相应的函数即可。在这个计算器的例子中,文法为:

factor -> INTEGER | LPAREN expr RPAREN
term -> factor ((MUL | DIV) factor)*
expr -> term ((PLUS | MINUS) term)

具体要怎么构建函数呢?以第二行为例:

def term(self):
    """term -> factor ((MUL | DIV) factor)*"""
    result = self.factor()  # 箭头右边的第一个元素为一个 factor,我们就调用之前写的 factor 函数

    while self.current_token.type in (MUL, DIV):  # 随后是 (pattern)*,因此我们需要一个循环
        token = self.current_token
        if token.type == MUL:
            self.eat(MUL)  # 更新当前 token
            result = result * self.factor()  # 下一个 token 为一个 factor,因此我们调用之前写的 factor 函数
        elif token.type == DIV:
            self.eat(DIV)
            result = result // self.factor()

    return result

未经允许,禁止转载,本文源站链接:https://iamazing.cn/