编译原理（二）语法分析

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语。

语法分析

目前语法分析常用的两类方法：

  • 自顶向下
  • 自底向上

本文采用自顶向下的分析方法。

分析原理

分析的目标是构造一个计算机可以识别的模型，在这里，使用语法树作为计算器的识别结构。

图片1

其中，节点的结构如上一篇文章中的定义（包含优先级、类型）。

操作符定义

首先，需要定义所有操作符对应的方法(这里仅提供加、减、乘、除四中运算法方法)，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Opt(object):
    @staticmethod
    def add(self, children):
        return children[0].value + children[1].value

    @staticmethod
    def sub(self, children):
        return children[0].value - children[1].value

    @staticmethod
    def mux(self, children):
        return children[0].value * children[1].value

    @staticmethod
    def div(self, children):
        return children[0].value / children[1].value

在构建语法树的时候，需要把操作符作为根节点来处理，其中加法操作对应的语法树如下,

图片2

节点定义与计算

语法树的节点可以是操作符，也可以是具体的值。但需要注意，所有的值应该是叶子节点，而操作符不可能为叶子节点。

节点定义包含：节点名称、节点优先级、节点类型、当前节点值以及子节点。

需要注意的是在计算当前节点的值时是需要递归计算子树下所有节点的结果的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class ASTNode(object):
    def __init__(self, token):
        self.token = token
        self.children = list()
 
    @property
    def token_name(self):
        return self.token.name

    @property
    def priority(self):
        return self.token.priority

    @property
    def is_opt(self):
        return self.token.type == TOKENTYPE.OPT

    @property
    def is_scp(self):
        return self.token.type == TOKENTYPE.SCP

    def add_child(self, child):
        self.children.append(child)

    def pop_child(self):
        return self.children.pop()

    @property
    def value(self):
        if self.is_opt:
            return calcuate(self) # 递归计算得到该操作符的操作结果
        else:
            return self.token.value

    def __str__(self):
        if not self.is_opt:
            return '(leaf [%s])' % self.token.value
        else:
            return '(%s %s, %s)' % (self.token_name, str(self.children[0]), 
                                    str(self.children[1]))
    __repr__ =  __str__

解析

构造语法树可以使用递归的方式来处理，具体的思想如下：

  1. 从左侧出发，遍历代码片段
  2. 判断操作符类型：值、操作符、停止符（括号）
  3. 比较当前操作符和上一次操作符的优先级，调整语法树结构：优先级小于等于上一次操作符，则把当前操作符作为根节点，原有语法树作为左子树，剩余代码片段作为待处理的右子树；优先级大于上一次操作符，则当前操作符替换上一次值的位置，上一次值作为当前操作符的做节点，剩余代码片段作为待处理的右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def parse(tokens, stop_name=None):
    last_opt = None
    for token in tokens:
        if stop_name and token.name == stop_name:
            return last_opt
        node = ASTNode(token)
        if node.is_opt:
            next_node = ASTNode(tokens.next())
            if next_node.is_scp:
                next_node = parse(tokens, 
                    stop_name=TOKEN_SCP_MATCH.get(next_node.token_name))
            if node.priority <= last_opt.priority:
                node.add_child(last_opt)
                node.add_child(next_node)
                last_opt = node
            else:
                node.add_child(last_opt.pop_child())
                node.add_child(next_node)
                last_opt.add_child(node)
        else:
            last_opt = node
        print last_opt
    return last_opt