语言SUM到栈式计算机STACK的机器语言的翻译

Veröffentlicht am | in | Views:

实验内容

sum.c是用c语言写的从sum语言到栈式计算机STACK的机器语言的编译器（省略了词法语法分析部分）。该程序的基本功能是先构造SUM语言的某句子的抽象语法树，然后将该语法树翻译成STACK的机器语言程序，并按顺序打印出该机器语言程序的指令。程序中有两段内容不完整（在程序中用TODO表示），请读懂并编译通过该程序，再将TODO的部分补充完整，并编译通过。

  1. 读懂程序sum.c并编译通过。（该程序可以使用gcc编译通过，其他编译环境请自行调试）

  2. 用你自己写的程序段替换程序中的TODO部分，使程序功能与实验内容的描述一致。

  3. （此要求为额外要求，供学有余力的同学自行选择。）将程序的输入改为句子1+(2+3)的抽象语法树，尝试程序能否输出正确的结果。

实验参考

  1. SUM语言简介：SUM语言是一种描述简单表达式的语言，该语言只有两种终结符num和+，其中num表示整型数，+表示加法。即该语言能表示整型的加法表达式。加法为左结合。

    语言的文法为：E -> num | E+E

  2. 栈式计算机STACK简介：这种机器有一个栈，能做的操作有两种，第一是向栈中压入一个整型数，第二是将栈顶的两个整型数弹出并做加法，然后将所得结果压入栈中。

    因此，该计算机的机器语言只有两个指令，一为：PUSH n；（将整型数n压入栈中）；另一为：ADD；（无操作数，默认将栈顶的两个整型数弹出栈并相加，再将结果压入栈中）。

  3. sum.c采用的翻译方法：

    SUM语言的句子先写成抽象语法树，然后对抽象语法树进行后续遍历，遍历到整型时就执行PUSH操作，遍历到+时就执行ADD操作。

  4. SUM语言的句子翻译为STACK程序的例子：

    SUM语言的句子： 1+2+3

    对应的抽象语法树:

    1
    2
    3
    4
    5
          +
        /  \
       +   3
     /  \
    1	2

    翻译成的STACK指令：

​ PUSH 1

​ PUSH 2

​ ADD

​ PUSH 3

​ ADD

完整代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include <stdio.h>
#include <stdlib.h>

#define TODO()                                  \
  do{                                                           \
    printf ("\nAdd your code here: file \"%s\", line %d\n",     \
            __FILE__, __LINE__);                                \
  }while(0)

///////////////////////////////////////////////
// Data structures for the Sum language.
enum Exp_Kind_t { EXP_INT, EXP_SUM };
struct Exp_t {
    enum Exp_Kind_t kind;
};

struct Exp_Int {
    enum Exp_Kind_t kind;
    int i;
};

struct Exp_Sum {
    enum Exp_Kind_t kind;
    struct Exp_t *left;
    struct Exp_t *right;
};

// "constructors"
struct Exp_t *Exp_Int_new(int i) {
    struct Exp_Int *p = (struct Exp_Int *)malloc(sizeof(*p));
    p->kind = EXP_INT;
    p->i = i;
    return (struct Exp_t *)p;
}

struct Exp_t *Exp_Sum_new(struct Exp_t *left, struct Exp_t *right) {
    struct Exp_Sum *p = (struct Exp_Sum *)malloc(sizeof(*p));
    p->kind = EXP_SUM;
    p->left = left;
    p->right = right;
    return (struct Exp_t *)p;
}

// "printer"
void Exp_print(struct Exp_t *exp) {
    switch ( exp->kind ) {
    case EXP_INT:
    {
        struct Exp_Int *p = (struct Exp_Int *)exp;
        printf("%d  ", p->i);
        break;
    }
    case EXP_SUM:
    {
        struct Exp_Sum *p = (struct Exp_Sum *)exp;
        Exp_print(p->left);
        printf("+  ");
        Exp_print(p->right);
        break;
    }
    default:
        break;
    }
}

//////////////////////////////////////////////
// Data structures for the Stack language.
enum Stack_Kind_t { STACK_ADD, STACK_PUSH };
struct Stack_t {
    enum Stack_Kind_t kind;
};

struct Stack_Add {
    enum Stack_Kind_t kind;
};

struct Stack_Push {
    enum Stack_Kind_t kind;
    int i;
};
// "printer"
void Stack_print(struct Stack_t *stack) {
    switch ( stack->kind ) {
    case STACK_ADD:
    {
        struct Stack_Add *p = (struct Stack_Add *)stack;
        printf("STACK_ADD\r\n");
        break;
    }
    case STACK_PUSH:
    {
        struct Stack_Push *p = (struct Stack_Push *)stack;
        printf("STACK_PUSH %d\r\n", p->i);       
        break;
    }
    default:
        break;
    }
}

// "constructors"
struct Stack_t *Stack_Add_new() {
    struct Stack_Add *p = (struct Stack_Add *)malloc(sizeof(*p));
    p->kind = STACK_ADD;
    return (struct Stack_t *)p;
}

struct Stack_t *Stack_Push_new(int i) {
    struct Stack_Push *p = (struct Stack_Push *)malloc(sizeof(*p));
    p->kind = STACK_PUSH;
    p->i = i;
    return (struct Stack_t *)p;
}

/// instruction list
struct List_t {
    struct Stack_t *instr;
    struct List_t *next;
};

struct List_t *List_new(struct Stack_t *instr, struct List_t *next) {
    struct List_t *p = (struct List_t *)malloc(sizeof(*p));
    p->instr = instr;
    p->next = next;
    return p;
}


// "printer"
void List_reverse_print(struct List_t *list) {
    
    struct List_t *next = NULL;
    struct List_t *reverse = NULL;

    struct List_t *cur = list;
    while ( cur != NULL ) {        
        next = cur->next;
        cur->next = reverse;
        reverse = cur;
        cur = next;          
    }

    //print    
    printf("\n");
    cur = reverse;
    while ( cur != NULL ) {
        Stack_print(cur->instr);        
        cur = cur->next;
    }
}

//////////////////////////////////////////////////
// a compiler from Sum to Stack
struct List_t *all = 0;

void emit(struct Stack_t *instr) {
    all = List_new(instr, all);
}

// 从抽象语法树 --> 中间语言
void compile(struct Exp_t *exp) {
    switch ( exp->kind ) {
    case EXP_INT:
    {
        struct Exp_Int *p = (struct Exp_Int *)exp;
        emit(Stack_Push_new(p->i));
        break;
    }
    case EXP_SUM:
    {       
        struct Exp_Sum *p = (struct Exp_Sum *)exp;
        compile(p->left);
        compile(p->right);
        emit(Stack_Add_new());
        break;
    }
    default:
        break;
    }
}

//////////////////////////////////////////////////
// program entry
int main() {
    printf("Compile starting\n");
    // build an expression tree:
    //            +
    //           / \
    //          +   4
    //         / \
    //        2   3
    struct Exp_t *exp = Exp_Sum_new(Exp_Sum_new(Exp_Int_new(2)
                                                , Exp_Int_new(3))
                                    , Exp_Int_new(4));
    // print out this tree:
    printf("the expression is:\n");
    Exp_print(exp);
    // compile this tree to Stack machine instructions
    compile(exp);

    // print out the generated Stack instructons:
    List_reverse_print(all);

    printf("\nCompile finished\n");
    return 0;
}
  • List_reverse_print 和 compile的case EXP_SUM为填充部分

实验结果