编译原理

抽象语法树

AST

image-20230504220248773

class definition

数据成员

对于一个ast对象，其具备三个子树根节点，以及当前节点的字符串类型符号，另外，再保存一个bool类型变量，指示当前节点是否为叶子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* AST */
class AST
{
private:
    const string val{};
    AST * left_child{};
    AST * mid_child{};
    AST * right_child{};
    bool is_leaf{};
public:
    AST()=default;
    explicit AST(const string & token) : val(token) , is_leaf(isTerminate(token)) {}
    explicit AST(string && token) : val(std::move(token)) {}
};

定义两个全局函数，用于判断符号是否为终结符号，以及是否为运算符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool isTerminate(const string & str)
{
    return !isupper(str[0]);
}

bool isOp(const string & str)
{
    switch (str[0])
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '%':
            return true;
        default:return str == "minus";
    }
}

方法

除了默认构造函数以及两个接收string类型（左值和右值）的构造函数外，我们在定义两个成员方法和一个静态方法：

  • built_ast：接受一个istream类型的参数，读取输入的ast文本表示信息，构建ast对象，该方法与特定的ast对象无关，因此用static修饰。
  • post_traverse：接收一个ast类型参数，打印其四元式序列，本质为后序遍历。
  • check：递归检查该ast的各层节点之间的“父子关系”，用于调试使用。

首先实现逻辑较为简单的check，我们一次打印出当前节点的符号以及子树的符号即可，如果某一个子树为空，则用#替代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void AST::check() const
{
    cout << val << ": ";
    if (!is_leaf)
    {
        cout << (left_child ? left_child->val : "#") << "\t" << (mid_child ? mid_child->val : "#") << "\t" << (right_child ? right_child->val : "#") << endl;
        if (left_child)
            left_child->check();
        if (mid_child)
            mid_child->check();
        if (right_child)
            right_child->check();
    }
    else
        cout << endl;
}

再开post_traverse，

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

void AST::post_traverse() const
{
    if (!is_leaf)
    {
        if (left_child && !left_child->is_leaf)
            left_child->post_traverse();
        if (mid_child && !mid_child->is_leaf)
            mid_child->post_traverse();
        if (right_child && !right_child->is_leaf)
            right_child->post_traverse();

        string operand1, op, operand2;
        // case 1. 一个左孩子，且为叶子节点
        if (left_child && !mid_child && !right_child)
        {
            operand1 = left_child->val;
            operand2 = "-";
            op = ":=";
        }
        else if (mid_child && right_child && isOp(mid_child->val))
        {
            operand1 = left_child ? left_child->val : right_child->val;
            operand2 = left_child ? right_child->val : "-";
            op = mid_child->val;
        }
        else if (left_child && right_child && left_child->val == "(")
        {
            operand1 = mid_child->val;
            operand2 = "-";
            op = ":=";
        }
        cout << op << "," << operand1 << "," << operand2 << "," << val << endl;
    }
}

build_ast的实现源码为：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 AST *  AST::build_AST(istream & in)
{
    string line;
    stack<pair<uint32_t , AST*>> stk;
    while (getline(in, line))
    {
        line.push_back(' ');
        // adjust idx to the first
        uint32_t idx = 0;
        uint32_t next_idx;
        while (idx < line.length() && line[idx] == ' ')
            ++idx;
        while (idx < line.length())
        {
            next_idx = line.find(' ', idx);
            string token = line.substr(idx, next_idx - idx);
            AST *node = new AST(token);
            while (!stk.empty() && stk.top().first >= idx)
                stk.pop();
            // 设置栈顶的节点的孩子节点
            if (!stk.empty())
            {
                auto &dad = stk.top().second;

                // token 是左右括号
                if (token == "(")
                {
                    assert(dad->left_child == nullptr);
                    dad->left_child = node;
                }
                else if (token == ")")
                {
                    assert(dad->right_child == nullptr);
                    dad->right_child = node;
                }
                else
                {
                    if (isOp(token) || (dad->left_child && dad->left_child->val == "("))
                        dad->mid_child = node;
                    else
                    {
                        if (!dad->mid_child)
                            dad->left_child = node;
                        else
                            dad->right_child = node;
                    }
                }
            }
            stk.emplace(idx, node);

            idx = next_idx + 1;
        }
    }
    while (stk.size() > 1)
        stk.pop();

    return stk.top().second;
}

测试

测试文件：

1
2
3
4
5
6
7
8
9
10
11
12
E minus
  T1 T0 K num
        /
        20
     *
     F (
       P M x
           %
           6
         +
         j0
       )

编写main函数，使用测试文件测试ast：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    ifstream fin("tree.txt");
    if (!fin.is_open())
    {
        cerr << "Fail to open file\n";
        exit(1);
    }
    auto *ast = AST::build_AST(fin);
    fin.close();

    ast->post_traverse();
    cout << "--------------------\n";
    ast->check();

    return 0;
}

输出如下：

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
:=,num,-,K
/,K,20,T0
%,x,6,M
+,M,j0,P
:=,P,-,F
*,T0,F,T1
minus,T1,-,E
--------------------
E: #    minus   T1
minus: 
T1: T0  *       F
T0: K   /       20
K: num  #       #
num:
/:
20:
*:
F: (    P       )
(:
P: M    +       j0
M: x    %       6
x:
%:
6:
+:
j0:
):