编译原理上机报告

本次实验代码均为本人编写，未经允许禁止抄袭

一、上机题目简介

实现简单函数绘图的语句

循环绘图(for 语句进行绘图)
比例设置(scale 是比例设置)
角度旋转(rot 是旋转的角度)
坐标平移(origin)
注释

关于屏幕的坐标系

左上角为原点
x方向为从左向右
y方向为从下到上

测试语言举例

ORIGIn IS (300+25*(1+1), 220);
rot is 0;
scale is (50, 100);
FOR T FROM 0 TO 2*PI STEP PI/500 DRAW(cos(T),sin(T));
scale is (100, 100);
FOR T FROM 0 TO 2*PI STEP PI/500 DRAW(cos(2*T),sin(T));

二、开发环境配置

环境: Ubuntu 22.04 与 Windows 11

语言: Python 3.11

IDE: Pycharm 专业版

三、解决思路及方案

首先我们将整个大的项目分成三个主要的方面：词法分析器，语法分析器，图形绘画器

1、词法分析器

我们首先要先确定这个token的结构，然后我们才能进行一个操作，我主要借鉴了老师发的课件中的类的结构，我们定义了一个Token类，里面包含了函数的类型，类型的字符串，还有这个Token的数值（可以有也可以没有）。

词法分析器的话就主要是读取项目的结构，这个很简单，我们只需要不断的读取这个字符串的每一个字，然后选择对应的操作，我们会首先判断它的类型，如果是数字的话就进入数字模块进行处理，如果是字母就进入字母的模块进行处理，这样我们就可以得到一系列token。然后将这些token放入到tokens的list中，然后作为返回值返回到之前的函数中，总的来说这一个模块并不难，并没有花费太多的时间，相比于语法分析这个要简单的多。

2、语法分析器

这个是整个实验中最困难的一部分，也是我花费时间最长的一部分，其主要的难度在于如何去计算浮点数的值。项目运行的原理我做成了流程图方便理解。

最下面有例子便于理解

20230526213152

其中关于浮点数计算的函数我是通过层层过滤并递归的方法实现的

去括号

我们先将输入的计算公式给一个一个读入，我们要做的第一步是去掉括号，就是将读入的计算公式中的括号里的内容给计算出来，然后将括号内的内容替换成我们的计算结果，这个实现方法就是我们将读入的tokens进行一个遍历，如果没有遇到括号就把这些读入的token放入到tokens_without _brackets里面，如果遇到括号，将括号内的计算公式给递归调用，还是利用这一个函数。

20230526213316

算乘除

经过上面的计算，我们到这里已经将括号给处理完毕了，现在只需要计算加减乘除就可以了，但是问题是减价的优先级不如乘除，所以我们要先计算乘除。

我们将上面的无括号序列进行遍历，如果遇到的是加减将不做处理，就只把数字和运算符放到两个不同的栈里面，但是如果遇到乘除的话，就要将数字栈弹出一个运算符，然后读取下一个运算符，将最终的运算结果再放回数字栈中，这样我们就可以完成计算了。

20230526213340

算加减

到这一步时，我们的序列就只剩加减了，我们就数值栈弹出一个，运算符号栈弹出一个，这样计算结果，一个一个的计算弹出，我们就可以得到最终的结果，然后将结果返回就可以了。

20230526213531

举例说明

我们就以最简单的1+2*(3+4)为输入tokens

第一步：

我们首先遍历这个tokens，发现有一个括号，然后我们把括号内的给提取出来。也就是把“3+4”给单独拿出来，做一个递归，然后计算出最终的结果，就是7，这样经过第一步处理之后我们的tokens就成了”1+2*7”，已经将括号给清除掉了。

第二步：

我们开始遍历这个tokens，并且将数字和符号分栈存储

:one:开始读取第1个token：

number_stack:1

char_stack:null

:two: 开始读取第2个token：

number_stack: 1

char_stack: +

:three: 开始读取第3个token：

number_stack: 1 2

char_stack: +

:four: 开始读取第3个token：

第四个token时，我们遇到了一个乘号，这时候就要进行number弹出一个操作数，然后再读取一个操作数，计算结果为14，然后将14放到number_stack栈中

number_stack: 1 14

char_stack: +

第三步

到这个地方我们就把乘除和括号给清除掉了，现在只剩加减了，加减就不说了，太简单了，两个栈就能操作

这样我们就能算出最终的结果为15

3、图形绘画器

我们通过上面的语义分析可以得到我们需要的数据，比如rot或者origin等，然后我们通过这些数据进行加工，然后使用python中的plt将结果画出来。

我们首先将for处理过的数据点放到x和y的序列中，然后利用数学公式完成旋转，比例变化等操作最后算出结果。

四、关键类以及主要方法

计算浮点数的函数

这个函数我认为是最重要的一个函数，就是把输入的这些字符给转化成一个公式并计算出来,其中主要的计算方法上图已经给出

def get_float(float_tokens):
    tokens_without_bracket = []
    next_tokens = []
    bracket_level = 0  # 这个level的目的是为了匹配括号的数量
    func_token: Token
    function_condition = False
    bracket_condition = False
    for token in float_tokens:
        # 我们的任务是去掉括号，包括函数的，就是要把函数和括号内的给计算出来
        # 当然我们还要考虑没有括号的情况
        if bracket_condition is False:
            if token.tokenType == TokenType.FUNC:
                # 这时我们已经判断出这个输入是一个函数的输入，我们就要进入函数的状态，然后记住是怎么函数
                function_condition = True
                func_token = token  # 现在func_token就是我们运算得到的函数
            elif token.tokenType == TokenType.L_BRACKET:
                # 如果我们发现了一个括号，就要进入括号状态
                bracket_condition = True
                bracket_level = 1  # 这个是判断括号等级的，进行括号匹配的工作
                continue
            else:
                # 这种情况是正常没括号的情况,就是经过上面筛选后发现是正常的情况
                tokens_without_bracket.append(token)  # 将token放进无括号情况中
                # 如果进入了括号状态或者函数状态我们就不进入这个地方了，转而进行下面相应的判断代码块进行处理
                continue

        # 如果这时候我们发现有括号的情况，就要通过相应的代码块进行处理
        if bracket_condition:
            # 这是进入了发现括号的状态
            if bracket_level > 0:
                # 这是括号还没结束的情况,把token传给下一个递归
                next_tokens.append(token)
                if token.tokenType == TokenType.L_BRACKET:
                    bracket_level += 1
                if token.tokenType == TokenType.R_BRACKET:
                    bracket_level -= 1
            if bracket_level == 0:
                next_tokens.pop()  # 把最后一个括号弹出去 ，这样我们就获得了括号内的全部数据

                if function_condition:
                    # 如果这个括号是函数的括号，那我们就要返回的是函数的情况
                    # 我们递归计算出结果，然后作为函数的输入
                    value = func_token.funcPtr(get_float(next_tokens))
                    tokens_without_bracket.append(Token(TokenType.CONST_ID, str(value), value))
                else:
                    # 这是无函数的情况，这样我们就不用利用函数值进行计算
                    value = get_float(next_tokens)
                    tokens_without_bracket.append(Token(TokenType.CONST_ID, str(value), value))
                # 这样之后我们进行最后的处理

                function_condition = False
                bracket_condition = False
                next_tokens = []

    number_stack = []
    char_stack = []
    tokens_without_bracket = tokens_without_bracket[::-1]  # 进行反转，为的是方便进行pop
    while tokens_without_bracket:
        # 到了这个地方就没有括号了，只有加减乘除
        # 我们可以这样，分成两个stack，一个用来放符号，一个用来放数字
        # 如果符号stack里面是要放乘法或者除法，就把数字stack里面的弹出来一个数进行运算
        # 然后把上面的结果放入到数字stack中，这样我们就可以得到一个一个只有加减乘除的符号栈
        # 我们就把这个结果进行计算然后返回就好了
        token = tokens_without_bracket.pop()  # token开始进行pop读取
        if token.tokenType == TokenType.CONST_ID:
            number_stack.append(token.value)
        elif token.tokenType == TokenType.PLUS or token.tokenType == TokenType.MINUS:
            # 如果符号是加减的话，直接加进去
            char_stack.append(token)
        elif token.tokenType == TokenType.MUL or token.tokenType == TokenType.DIV:
            # 如果是乘法或者除法就要开始弹出并进行相应的操作
            param1 = number_stack.pop()  # 参数读取
            this_token = tokens_without_bracket.pop()
            param2 = this_token.value
            if token.tokenType == TokenType.MUL:
                number_stack.append(param1 * param2)
            else:
                number_stack.append(param1 / param2)

    # 到这个地方乘除已经被算完了，只剩下加减线性运算了
    number_stack = number_stack[::-1]
    char_stack = char_stack[::-1]
    result = number_stack.pop()
    while char_stack:
        char_in_stack = char_stack.pop()
        if char_in_stack.tokenType == TokenType.PLUS:
            result += number_stack.pop()
        elif char_in_stack.tokenType == TokenType.MINUS:
            result -= number_stack.pop()
        else:
            print("error!I got ", char_in_stack.tokenType, "while getting result")
    return result

关于计算for坐标的函数

我们如果想要画出点，就要知道这些点的位置，我的计算方法是这样，我们读取T的计算公式，然后遍历这个T（T给了起始点和截至点），我们将这个T的计算公式中的T这个token在每一次遍历中给换成当前T的一个值，然后将这个计算公式放到上文中的get_float（）函数中，最后计算出结果，我们举个例子：

假如T是0到5，步幅是1，然后横坐标的计算公式是sin(T)，我们将T从0开始，第一个循环时T是0.我们就得到了计算公式“sin(0)”，然后我们把这个计算公式给放到get_float()中，就可以得到结果，我们就可以得到横坐标为0。

然后循环第二次，这一次T为2，我们就利用公式得到”sin(2)”,然后再把这个给放到get_float()中，就能计算出结果了。

如此循环多次，我们就能得到所有的x坐标，然后同理我们可以得到所有的y坐标，到此为止我们就可以计算好初始的全部坐标点了

def for_statement(TOKENS):
    # 老逼登握拳，大的要来了
    global start
    global step
    global end
    global x
    global y

    token: Token
    token = get_token(TOKENS)
    if token.tokenType != TokenType.T:
        print("Error:except 'T' but get", token.tokenType)
        exit()

    token = get_token(TOKENS)
    if token.tokenType != TokenType.FROM:
        print("Error:except 'from' but get", token.tokenType)
        exit()

    # 这时就要开始循环读取了遇到逗号时停止读取
    flag = False
    float_tokens = []
    while flag is False:
        token = get_token(TOKENS)
        if token.tokenType == TokenType.TO:
            # 如果遇到TO就说明结束读入了
            flag = True
            start = get_float(float_tokens)
        else:
            float_tokens.append(token)

    flag = False
    float_tokens = []
    while flag is False:
        token = get_token(TOKENS)
        if token.tokenType == TokenType.STEP:
            # 如果遇到STEP就说明结束读入了
            flag = True
            end = get_float(float_tokens)
        else:
            float_tokens.append(token)
    flag = False
    float_tokens = []
    while flag is False:
        token = get_token(TOKENS)
        if token.tokenType == TokenType.DRAW:
            # 如果遇到DRAW就说明结束读入了
            flag = True
            step = get_float(float_tokens)
        else:
            float_tokens.append(token)

    token = get_token(TOKENS)
    if token.tokenType != TokenType.L_BRACKET:
        print("Error:except '(' but get", token.tokenType)
        exit()

    # 到这里我们就得到了之前所有的数据，但是现在我们要开始计算，横坐标和纵坐标的值了
    flag = False
    x_tokens = []  # 用来存储计算x的tokens
    while flag is False:
        token = get_token(TOKENS)
        if token.tokenType == TokenType.COMMA:
            # 如果遇到,就说明结束读入了
            flag = True
        else:
            x_tokens.append(token)

    flag = False
    y_tokens = []  # 用来存储计算y的tokens
    while flag is False:
        token = get_token(TOKENS)
        if token.tokenType == TokenType.SEMICO:
            # 如果遇到;就说明结束读入了，然后弹出上一个括号
            flag = True
        else:
            y_tokens.append(token)

    y_tokens.pop()


    # 现在我们都获得了x和y的计算方式，现在就要开始计算这些东西
    # 首先计算x的各种值
    x_start = start
    caculate_tokens = []
    while x_start < end:
        for token in x_tokens:
            if token.tokenType == TokenType.T:
                caculate_tokens.append(Token(TokenType.CONST_ID, str(x_start), x_start))
            else:
                caculate_tokens.append(token)
        x.append(get_float(caculate_tokens))
        caculate_tokens = []
        x_start += step

    # 然后计算y的各种值
    y_start = start
    caculate_tokens = []
    while y_start < end:
        for token in y_tokens:
            if token.tokenType == TokenType.T:
                caculate_tokens.append(Token(TokenType.CONST_ID, str(y_start), y_start))
            else:
                caculate_tokens.append(token)
        y.append(get_float(caculate_tokens))
        caculate_tokens = []
        y_start += step

    # 到这里我们就把y计算完成了，下一步就要去画图了
    print("x is")
    print(x)
    print("y is")
    print(y)
    print("x,y length is ",len(x),len(y))

关于最终结果的变换与画图

最终我们得到所有的rot，origin，scale之后，当然还有x,y，我们就可以开始计算变换后的情况了。然后将最后变化完的点给计算出来。

def print_pictures(origin_x: float, origin_y: float, rot: float, scale_x: float, scale_y: float, start: float,
                   end: float, step: float, x: list, y: list):
    # 我们把这些全部传到这个函数里面开始进行画图
    for i in range(len(x)):
        # 比例变换
        x[i], y[i] = x[i] * scale_x, y[i] * scale_y
        # 旋转变换
        x[i], y[i] = x[i] * math.cos(rot) + y[i] * math.sin(rot), y[i] * math.cos(rot) - x[i] * math.sin(rot)
        # 平移变化
        x[i], y[i] = x[i] + origin_x, y[i] + origin_y
    print("after change")
    print(x)
    print(y)
    plt.plot(x,y)
    plt.show()

五、测试结果

测试一

测试数据：

注：输入的数据是带括号的，所以验证成功

ORIGIn IS (300+25*(1+1), 220);
rot is 0;
scale is (50, 100);
FOR T FROM 0 TO 2*PI STEP PI/500 DRAW(cos(T),sin(T));
scale is (100, 100);
FOR T FROM 0 TO 2*PI STEP PI/500 DRAW(cos(2*T),sin(T));

输出结果：

20230526213557

测试二

测试数据:

ORIGIN IS (200, 500);
SCALE IS (100, 100/3);
ROT IS PI/2;
FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T), sin(T));

输出结果：

20230526213606

六、实验体会

这门课程让我了解了编译器的运行原理，通过这门课我了解到了编译器的工作原理，让我对底层的架构有了新的了解，而且自己手动构建一个编译器是十分有成就感的，而且幸运的是我并没有花费太多的时间去做这个东西，因为我发现如果一边写代码一边写注释并不会减缓代码的进度，相反它会加速项目的进度，因为这样能让你对项目代码变得更清晰，这次代码我再写完后经过两次调试就取得了成功，这也是我认为我本次实验最大的收获。