编译原理--Ch2.一个简单的语法制导翻译器

字数统计: 7.4k字   |   阅读时长≈ 34分

编译原理–Ch2–一个简单的语法制导翻译器。

《编译原理》龙书Chapter2——一个简单的语法制导翻译器。

编译原理–Ch2.一个简单的语法制导翻译器。

2.1引言

语法（syntax）：描述该语言程序的正确形式

语义（semantics）：定义了程序的含义，即每个程序在运行时该做什么事情。

后缀表达式：运算符置于运算分量之后的一种表示方法。比如中缀表达式9-5+2的后缀形式为95-2+。个人感觉后缀表达式很适合用于基于栈的运算。

编译器前端模型：

1
2
       词法单元           语法分析树              三地址代码
词法分析-------->语法分析器---------->中间代码生成器---------->...

词法分析：处理由多个字符组成的构造，比如标识符。比如这个C语言片段int number = 3;，词法分析用于确定n u m b e r这6个单词会一起组成一个标识符number，表明了一个变量，而不是把这6个单词拆开来考虑。

这样被当作一个单元处理的东西叫做词法单元（token）。

抽象语法树（AST, Abstract Syntax Tree）：也称语法树（Syntax Tree），层次化的表示了源码的语法结构。

2.2语法定义

本章讲述“上下文无关文法（context-free grammar）”，简称“文法”

比如Java中的

2.5.3非终结符号的过程——中缀转后缀

下面代码是Python版本的预测语法分析制导翻译方案，参考的翻译方案是上节，通过对原本的左递归方案改成右递归，从而使得预测语法的可行性。

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
class Translator():
    def __init__(self, input) -> None:
        self.input = input
        self.len = len(self.input)
        self.idx = 0
        self.lookahead = self.input[self.idx]

    def expr(self):
        self.term()
        self.rest()
        
    def rest(self):
        if self.lookahead == "+":
            self._match("+")
            self.term()
            self.print("+")
            self.rest()
        elif self.lookahead == "-":
            self._match("-")
            self.term()
            self.print("-")
            self.rest()
        else:
            pass

    def term(self):
        if self.lookahead in [chr(i+ord('0')) for i in range(10)]:
            t = self.lookahead
            self._match(self.lookahead)
            self.print(t)
        else:
            raise("syntax error")
        
    def _match(self, t):
        if self.lookahead == t:
            self.idx += 1
            if self.idx < self.len:
                self.lookahead = self.input[self.idx]
            else:
                pass
        else:
            raise("syntax error")
        
    def print(self, ch):
        print(ch, end="")
        
if __name__ == "__main__":
    a = "9-5+2"
    t = Translator(a)
    t.expr()
    "95-2+"

需要注意的是语义动作，也就是print所在的位置。放错顺序的话会导致打印出来的式子也是错误的。

解释：注意后缀表达式的特征，在AST中是“左右根”，根一般在这里是运算符+/-，左与右就是运算数字。

取9-5为例子。这是一个expr，然后再右递归的模式下，expr被匹配为term();rest()。因此第一个9直接先被term给匹配了。后面的-5被当成rest进行进一步递归解析。而这个数字9，在AST树中就是左节点。

然后在rest部分，我们处理这颗树的根节点和右子节点。因此先需要对子树的根节点进行匹配，也就是对运算符+/-进行match，所以就有了rest函数中的match("+")这样的操作。但是这里不能急着打印，因为刚刚才打印了左节点，根据“左右根”的规则，需要在右节点打印后，才能打印根节点。

确定是子树后了，lookahead指向下一个字符，调用term，打印右节点。这里是数字5。

然后再打印根节点，也就是print("-")这样的操作。以上，便完成了对一个子树的“左右根”打印，得到结果“95-”。

当然，后面还跟了一个rest。这是递归思想，比如9-5+2中，前面处理完了9-5，那最后这个rest则处理后面的+2，进行了一遍递归，和一开始对-5的处理一样。

注意：9-5+2的AST在正确的形式下应该是左递归的，像下面这样：

1
2
3
4
5
     +
   |   |
  -    2
|   |
9   5

因此后面说起rest处理+2的地方时，我没有继续用AST解释，因为那样的话，实际上对应于AST上，是在从9-5的子树上去找其所在的大树，即<>+2这个玩意。

这里为了使用预测语法分析方案，其翻译方案是右递归的。换句话讲，其生成的翻译树和AST有一定的区别。AST因为这里面加减运算的左结合性，必须使用左递归的这种形式；右递归的形式会导致运算顺序出错。因此这里谈AST只是为了方便理解后缀式。关于生成出来的翻译树，可以看书图2-24。

2.5.4对2.5.3代码的优化

首先，可以把rest的全部实现，直接在expr中写成。这样能够减少一个函数调用。

其次，可以将部分递归调用优化成迭代。比如rest函数中最后还会调用rest，这就叫做**尾递归(tail recursive)**。在尾部自己调用自己，便完全可以直接用while+continue的方式来优化。

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
class Translator():
    def __init__(self, input) -> None:
        self.input = input
        self.len = len(self.input)
        self.idx = 0
        self.lookahead = self.input[self.idx]
    
    def expr(self):
        self.term()
    #     self.rest()
        
    # def rest(self):
        while True:
            if self.lookahead == "+":
                self._match("+")
                self.term()
                self.print("+")
                # self.rest()
                continue
            elif self.lookahead == "-":
                self._match("-")
                self.term()
                self.print("-")
                # self.rest()
                continue
            else:
                break

    def term(self):
        if self.lookahead in [chr(i+ord('0')) for i in range(10)]:
            t = self.lookahead
            self._match(self.lookahead)
            self.print(t)
        else:
            raise("syntax error")
        
    def _match(self, t):
        if self.lookahead == t:
            self.idx += 1
            if self.idx < self.len:
                self.lookahead = self.input[self.idx]
            else:
                # 到达最大长度后lookahead就不在继续下去了
                pass
        else:
            raise("syntax error")
        
    def print(self, ch):
        print(ch, end="")
        
if __name__ == "__main__":
    a = "9-5+2-3+4"
    t = Translator(a)
    t.expr()

2.5.5全部代码

在2.5.3和2.5.4都已经给了。原书用的是Java，但我觉得不够简洁，所以还是用了Python做简单的脚本。

2.6词法分析

本节中，一个词法单元就是一个带有附加信息终结符号

本节的词法分析器允许在表达式中出现数字、标识符、空白（空格，tab和换行）

下面便是扩展后的翻译方案：（**表示加粗，终结符号）

1
2
3
4
5
6
7
8
9
10
11
expr -> expr + term {print("+")}
	| expr - term {print("-")}
	| term
	
term -> term * factor {print("*")}
	| term / factor {print("/")}
	| factor
	
factor -> (expr)
	| **num** {print(**num**.value)}
	| **id** {print(**id**.lexeme)}

num假定有属性value，表示整数值。

id有一个字符串属性lexeme，表示这个id的实际词素。（就是说是这个变量的名称？）

2.6.1跳过空白和注释

下面伪代码用于跳过空白和注释：

1
2
3
4
5
6
7
8
9
for(; ; peek=next char) {
	if(peek is blank or tab) {
		do nothing;
	} else if (peek is a newline) {
		line++;	// 用于记录行数
	} else {
		break;
	}
}

下面给出demo：

1
2
3
4
5
6
7
8
9
10
11
12
def skip_blank(s:str):
    line = 0    # 按理来说应该全局化，这里只是个demo，表明是局部的行数
    for i in range(len(s)):
        if s[i] in [" ", "\t"]:
            continue
        elif s[i] == "\n":
            line += 1
        else:
            break
    return s[i:], line

print(skip_blank("  \n\n\t\n \t\tword"))

2.6.2预读

在语法分析器具体决定某个词法单元时，需要首先预读一些字符。

比如在C中，输入了<后还需要再预读一个字符，如果后面一个字符是=，则共同组成词法单元<=，即大于等于。

可以使用输入缓冲区来实现预读操作。在特殊或者简单情况下可以使用单一变量来实现。

2.6.3常量

在表达式中，词法分析器要能够识别出数字常量。

比如表达式10+35中，需要分别把10和35分别识别成一个独立的单位（即词法单元）；这两个词法单元都分别表示整数值不同的数字常量。

31+28+59通过词法分析，应该得到以下序列：

1
<**num**, 31><+><**num**, 28><+><**num**, 59>

其中，每一个<>就是一个词法单元，**num**表示终结符号（加粗的意思），后面跟着的数字就是这个符号的属性值，表示了具体的整形值。（在2.6开头说了num有属性值value表示整形值，就这个玩意）

然后，运算符+因为没有额外的属性，因此这里就是<+>。

以下是伪代码：（这个伪代码只能parse第一个token）

1
2
3
4
5
6
7
8
if(peek is a digit char){
	v = 0;
	do {
		v = v * 10 + int(peek);
		peek = next char;
	} while(peek is a digit char);
	return token<num, v>;
}

下面是Python版代码：

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

class Tokenizer():
    def __init__(self, input) -> None:
        self.input = None
        self.input = input
        # self.idx = 0
        if self.input is not None:
            self.len = len(self.input)
            self.idx = 0
            self.peek = self.input[self.idx]
            
    def peek_next(self):
        if self.idx < self.len - 1:
            self.idx += 1
            self.peek = self.input[self.idx]
        elif self.idx == self.len - 1:
            self.idx += 1
            self.peek = ""  # 结束
            
        
    def reset(self):
        self.idx = 0
        self.peek = self.input[self.idx]
        
    def single_parse(self):
        self.reset()
        
        if self.peek in [chr(ord('0') + i) for i in range(10)]:
            v = 0
            while True:
                v = v*10 + int(self.peek)
                self.peek_next()
                if self.peek not in [chr(ord('0') + i) for i in range(10)]:
                    break
            
            return "<num, {}>".format(v)
        
    def parse(self):
        self.reset()
        
        s = ""

        while self.idx < self.len and self.peek != "":
            if self.peek in [chr(ord('0') + i) for i in range(10)]:
                v = 0
                while True:
                    v = v*10 + int(self.peek)
                    self.peek_next()
                    if self.peek not in [chr(ord('0') + i) for i in range(10)]:
                        break
                
                s += "<num, {}>".format(v)
            elif self.peek == "+":
                s += "<+>"
                self.peek_next()
            elif self.peek == "-":
                s += "<->"
                self.peek_next()
            else:
                pass
            

        return s
        
t = Tokenizer("31+28+59")
print(t.single_parse())
print(t.parse())

2.6.4识别关键字和标识符

关键字就是for，while这种已经有特殊含义的字符串。

除了关键字以外的字符串就被识别为一般的标识符，用来给变量，函数命名。

为了简化语法分析器，一般把标识符当作终结符号处理。

比如在2.6开头提过终结符号id。在处理以下输入时：

1
count = count + increment;

应该得到结果：

1
<**id**, "count"><=><**id**, "count"><+><**id**, "increment"><;>

其中"count"，"increment"这种就是id的lexeme属性。

这里使用一个表来存储字符串，可以解决以下问题：

  • 单一表示：更加高效，不会出现多个实例，浪费空间。
  • 保留字（关键字）：只要在初始化表的时候提前把保留字存储进即可。

下面是伪代码：（图2-31）

1
2
3
4
5
6
7
8
9
10
11
12
words = new Table(); // words就是记录表

if(peek 是个字母或者数字) {
	缓冲区b <-- peek中的字母或者数字
	s = 缓冲区b中的组成的字符串
	w = words.get(s); // 返回相应的词法单元
	if(w is not Null) return w;
	else {
		将键值对(s, <id, s>)加入到words;
		return 词法单元<id, s>;
	}
}

下面是我的实现。把前面的一些思路带进来了，现在完整的代码能够解析关键字，+，-，标识符，数字常量之间组成的表达式：

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
class Tokenizer():
    def __init__(self, input) -> None:
        self.input = input
        self.len = len(self.input)
        self.idx = 0
        self.peek = self.input[self.idx]
        self.curr = ""
        
        self.alpha = [chr(ord('a')+i) for i in range(26)]
        self.Alpha = [chr(ord('A')+i) for i in range(26)]
        self.number = [chr(ord('0')+i) for i in range(10)]
        
        # 字符串表
        # 先初始化一些常见的关键字
        self.table = {
            "for": "<for>",
            "do": "<do>",
            "while": "<while>",
            "if": "<if>",
            "elif": "<elif>",
            "else": "<else>"
        }
        
        
        
    def peek_next(self):
        if self.idx < self.len - 1:
            self.idx += 1
            self.peek = self.input[self.idx]
        elif self.idx == self.len - 1:
            self.idx += 1
            self.peek = ""  # 结束
       
       
    def reset(self):
        self.idx = 0
        self.peek = self.input[self.idx] 
        
    # 返回一个字符串中的第一个标识符
    def label(self):
        b = ""
        
        ori = self.idx  # 用来做回退的
           
        # 由字符或者_开始
        if self.peek in self.alpha + self.Alpha + ["_"]:
            b += self.peek
            self.peek_next()
            
            # 只有一个字符
            if self.peek == "": 
                # 只是一个_，那么报错
                if b == "_":
                    raise "syntax error: invalid variable '_'"
                else:   # 只是一个alpha或者Alpha字母，那也是对的
                    return b
        else:
            return ""
        
        # 后面可以跟数字，字母，_
        while self.idx < self.len and self.peek != "":
            if self.peek in self.alpha + self.Alpha + self.number + ["_"]:
                b += self.peek
                self.peek_next()
            # 如果是空白，那就算是一个标识符的结尾，返回结果
            elif self.peek in [" ", "\n", "\t"]:
                return b
            # 如果是其他特殊字符，报错
            else:   
                # return ""
                raise "syntax error: no special char allowed in a variable"
        
        return b
        
    def skip_blank(self):
        line = 0    # 按理来说应该全局化，这里只是个demo，表明是局部的行数
        # for i in range(len(s)):
        #     if s[i] in [" ", "\t"]:
        #         continue
        #     elif s[i] == "\n":
        #         line += 1
        #     else:
        #         break
        #     return s[i:]
        b = ""
        while self.idx < self.len:
            if self.peek in [" ", "\t"]:
                self.peek_next()
                continue
            elif self.peek == "\n":
                line += 1
                self.peek_next()
                continue
            else:
                break
            
    def single_parse(self):
        self.reset()
        
        self.skip_blank()
        """
        if(peek 是个字母或者数字) {
            缓冲区b <-- peek中的字母或者数字
            s = 缓冲区b中的组成的字符串
        """
        label = self.label()
        word = self.table.get(label)
        if word is not None:
            return word
        else:
            self.table[label] = "<id, {}>".format(label)
            return self.table[label]
        
    # 实现对变量，关键字，数字，+，-表达式的解析
    def parse(self):
        self.reset()
        
        self.skip_blank()
        
        s = ""

        while self.idx < self.len and self.peek != "":
            # 处理标识符
            label = self.label()
            if label != "":
                word = self.table.get(label)
                if word is not None:
                    # return word
                    s += word
                else:
                    self.table[label] = "<id, {}>".format(label)
                    s += self.table[label]
                # return self.table[label]
            # 是数字
            elif self.peek in [chr(ord('0') + i) for i in range(10)]:
                v = 0
                while True:
                    v = v*10 + int(self.peek)
                    self.peek_next()
                    if self.peek not in [chr(ord('0') + i) for i in range(10)]:
                        break
                
                s += "<num, {}>".format(v)
            # +
            elif self.peek == "+":
                s += "<+>"
                self.peek_next()
            # -
            elif self.peek == "-":
                s += "<->"
                self.peek_next()
            else:
                pass
            
            self.skip_blank()
            

        return s
        
        
        
        
t = Tokenizer("__word__1123123    \t\tafsdafad")
print(t.label())

# 测试skip_blank
print(t.input[t.idx:])
t.skip_blank()
print(t.input[t.idx:])

print(t.single_parse())

t = Tokenizer("var + number - 114514")
print(t.parse())

2.6.5词法分析器

这一节就是把之前的功能整合了一下。

我上面在2.6.4的代码已经具有了需要的功能：

  • 跳过空白符
  • 处理数字
  • 处理保留字和标识符

但是模块化实现的还不太行

用上面的代码做一下测试：

1
2
3
4
5
6
7
t = Tokenizer(
"""
var + number - 114514
aaa + 10 - 5"""
)
print(t.parse())
# <id, var><+><id, number><-><num, 114514><id, aaa><+><num, 10><-><num, 5>

每行都能正常解析，不过每行之间没有设置什么终止符。暂时不重要。

2.7符号表

目标：

1
{ int x; char y; { bool y; x; y; } x; y; }

翻译成：

1
{ { x:int; y:bool; } x:int; y:char; }

2.7.1为每一个作用域设置一个符号表

C语言中，块是可以嵌套的，就像上文那样。

下面的语法规则可以生成嵌套的块：

1
block --> "{" decls stmts "}"

其中，一个block就是所谓的”块“，在C语言中一般是用大括号括起来的区域。这些块影响了”标识符的作用域（scope）“，即标识符起作用的程序部分。

decls（declarations）生成一个”声明“序列，也就是类似int x;这种定义变量的代码。

stmts（statements）生成一个”语句“序列，也就是对变量进行操作的代码片段，比如对变量进行加减乘除运算，z=x+y;；在这个简单的例子里面，单纯的引用变量也被算作statements，比如x;，y;（上面的例子里面给到了）

至于大括号要加引号，"{"，这是为了和”语义动作“的大括号相互区分（语义动作的大括号没有被引号标注）

块的符号表优化：

块的符号表实现可以利用作用域的”最近嵌套“规则。嵌套结构可以确保可应用的符号表形成一个”栈“。这样方便配置与释放。

有些编译器还维护了”散列表“来访问条目。

最近嵌套规则（most-closely）：一个标识符x在最近的x声明的作用域中。也就是说，从x出现的块开始，由内向外检查各个块时找到的第一个对x的声明。

比如说：

1
2
3
4
5
6
7
{
	int x;
	{
		char x;
		x;
	}
}

看到语句x;时，从内向外，找到第一个对x的声明，也就是char x;。

符号表链：

一个链表，每个链记录了一个块上的符号表。最顶部的初始节点B0一般记录的是全局变量，然后子节点就记录了更加内层的块。

给个书上的例子：

1
2
3
4
5
6
7
8
9
int w;
{
	int x; int y;
	{
		int w; bool y; int z;
		w; x; y; z;
	}
	w; x; y;
}

转化成符号表链后就是：

1
2
3
4
5
6
7
8
9
B0:
	- w:int;
B1:
	- x:int;
	- y:int;
B2:
	- w:int;
	- y:bool;
	- z:int;

下面给出Python代码实现：

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
# 生成链接符号表

# 这是单个链表节点，是一个块的符号表，这里取名为Env
class Env:
    def __init__(self) -> None:
        self.table = dict()
        self.prev = None    # 用于指向上一个Env的
        
    def __init__(self, prev_env):
        if type(prev_env) != Env:
            raise "error: wrong type, need class Env"
        
        self.table = dict()
        self.prev = prev_env   # 用于指向上一个Env的
        
    def put(self, s:str, symbol:Symbol):
        self.table[s] = symbol
        
    def get(self, s:str) -> Symbol:
        e = self.prev
        while e != None:
            found_sym = e.table.get(s)
            if found_sym != None:
                return found_sym
            
            e = e.prev
        return None

其中的Symbol类表示一个符号。具体实现是什么还没说，但是根据上图对符号链表的具体描述，应该就是int，char这类玩意。

PS：在下文有利用方法，暂时只发现了其中的type成员，表示的是类型的字符串名，比如“int”，“char”。

因此给出可能的样子：

1
2
3
class Symbol:
    def __init__(self, s:str) -> None:
        self.type = s

2.7.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
program -> block			{ 	top = null; }

block -> "{"				{ 	saved = top; 
								top = new Env(top); 
								print("{"); }
								
block -> decls stmts "}" 	{	top = saved; 
								print("}"); }
								
decls -> decls decl
	| ε
	
decl -> **type** **id*** ;	{	s = new Symbol;
								s.type = **type**.lexeme;
								top.put(**id**.lexeme, s); }

stmts -> stmts stmt
	| ε
	
stmt -> block
	| factor ;				{ 	print("; "); }
	
factor -> **id**			{ 	s = top.get(**id**.lexeme); 
								print(**id**.lexeme); 
								print(";");
								print(s.type); }

我的理解：

1
program -> block			{ 	top = null; }

即程序遇到了一个块（block），可以是大括号括起来的那种，或者是全局默认的一个大block，此时将临时变量top初始化为null，准备开始解析。

1
2
3
block -> "{"				{ 	saved = top; 
								top = new Env(top); 
								print("{"); }

遇到block的左括号了，那么说明要离开现在的Env，进入链表节点的下一个子节点了，所以用临时变量saved保存现在的top，在top处创建一个新的Env，并执行打印”{“的动作。

1
2
block -> decls stmts "}" 	{	top = saved; 
								print("}"); }

即遇到了一个block的终结符号”}”，马上要离开现在的Env，返回到父节点了。因此将saved中保存的上位节点还原回来，并打印”}”。

1
2
decls -> decls decl
	| ε

这个就是说declarations可以是空，也可以由多个declaration组成。

1
2
3
decl -> **type** **id*** ;	{	s = new Symbol;
								s.type = **type**.lexeme;
								top.put(**id**.lexeme, s); }

而这一句给出了单个declaration的格式：用**包裹的都表明是终结符。type就是类型，对应int，char这种东西；id指的应该就是变量名标识符了，比如int x;中的x。

遇到一个这样的变量定义式后，会初始化一个Symbol类s，然后将s的type成员设置为**type**.lexeme。lexeme就是语素的意思，这里可以直接理解为type的字符串表示形式。比如说遇到int x;，那么s.type = **type**.lexeme = "int"。

id.lexeme同理，也就是变量x的字符串表示，也就是”x”这个变量名。

之后把(**id**.lexeme, s)作为一个键值对放入符号表里面。

值得注意的是，翻译器在遇到decl的时候，确实创建了符号表Symbol，但是并没有打印任何东西！

1
2
stmts -> stmts stmt
	| ε

和上面的declarations一样。

1
2
stmt -> block
	| factor ;				{ 	print("; "); }

这里对statement进行了定义。这里是简化了的版本，除了嵌套block以外，只有factor ;这样的利用方式，也就是x;，y;这样；这种在程序中没有实质意义，但是C语言里面，或者Java里面都是支持的。

话说回嵌套block，就是说stmt -> block这个就表明了，一个子块也被当成了一个statement。

由于这只是个符号表解析器，因此statements的一切行为都没什么用处，所以这里也只是在遇到factor ;的时候单纯的打印了一下分号，表示结束。而遇到block的时候，什么行为也没有。

1
2
3
4
factor -> **id**			{ 	s = top.get(**id**.lexeme); 
								print(**id**.lexeme); 
								print(":");
								print(s.type); }

这个就是对factor的一个解释。这里只有一种最简单的终结子**id**作为factor，而遇到的时候，会从符号表里获取相应的Symbol，然后打印id的lexeme，打印分号，打印type。

举例：

比如说前面声明了一个int x;，那么符号表里就会生成(x, int)这样类似的一个键值对，然后现在这里有个x;，那么就会从符号表中获取这个Symbol，然后打印lexeme “x”，打印“:”，打印”int”；

同时，这里还与上面的stmt -> factor ;匹配，因此还会打印一个分号“;”作为终结。

最后就得到了x:int;这样的表现形式。

下面进行编程实现。

编程实现

这里需要稍微复习一下翻译器的编写方式，参考2-25。

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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
# 生成链接符号表

    
class Symbol:
    def __init__(self, s:str) -> None:
        self.type = s
        
# 这是单个链表节点，是一个块的符号表，这里取名为Env
class Env:
    # def __init__(self) -> None:
    #     self.table = dict()
    #     self.prev = None    # 用于指向上一个Env的
        
    def __init__(self, prev_env=None):
        if prev_env != None and type(prev_env) != Env:
            raise "error: wrong type, need class Env"
        
        self.table = dict()
        self.prev = prev_env   # 用于指向上一个Env的
        
    def put(self, s:str, symbol:Symbol):
        self.table[s] = symbol
        
    def get(self, s:str) -> Symbol:
        # e = self.prev
        e = self
        while e != None:
            found_sym = e.table.get(s)
            if found_sym != None:
                return found_sym
            
            e = e.prev
        return None

class SymAnalyzer:
    def __init__(self, input:str) -> None:
        self.input = input
        self.len = len(self.input)
        self.idx = 0
        self.peek = self.input[self.idx]
        self.curr = ""
        
        self.alpha = [chr(ord('a')+i) for i in range(26)]
        self.Alpha = [chr(ord('A')+i) for i in range(26)]
        self.number = [chr(ord('0')+i) for i in range(10)]
        
        self.sym_table = {}
        
    def peek_next(self):
        if self.idx < self.len - 1:
            self.idx += 1
            self.peek = self.input[self.idx]
        elif self.idx == self.len - 1:
            self.idx += 1
            self.peek = ""  # 结束
  
    def reset(self):
        self.idx = 0
        self.peek = self.input[self.idx] 
    
    # 返回一个字符串中的第一个标识符
    def label(self):
        b = ""
        
        ori = self.idx  # 用来做回退的
           
        # 由字符或者_开始
        if self.peek in self.alpha + self.Alpha + ["_"]:
            b += self.peek
            self.peek_next()
            
            # 只有一个字符
            if self.peek == "": 
                # 只是一个_，那么报错
                if b == "_":
                    raise "syntax error: invalid variable '_'"
                else:   # 只是一个alpha或者Alpha字母，那也是对的
                    return b
        else:
            return ""
        
        # 后面可以跟数字，字母，_
        while self.idx < self.len and self.peek != "":
            if self.peek in self.alpha + self.Alpha + self.number + ["_"]:
                b += self.peek
                self.peek_next()
            # 如果是空白，那就算是一个标识符的结尾，返回结果
            elif self.peek in [" ", "\n", "\t", ";", "{", "}"]:
                return b
            # 如果是其他特殊字符，报错
            else:   
                # return ""
                print(self.peek)
                raise "syntax error: no special char allowed in a variable"
        
        return b
          
    def skip_blank(self):
        line = 0    # 按理来说应该全局化，这里只是个demo，表明是局部的行数
        # for i in range(len(s)):
        #     if s[i] in [" ", "\t"]:
        #         continue
        #     elif s[i] == "\n":
        #         line += 1
        #     else:
        #         break
        #     return s[i:]
        b = ""
        while self.idx < self.len:
            if self.peek in [" ", "\t"]:
                self.peek_next()
                continue
            elif self.peek == "\n":
                line += 1
                self.peek_next()
                continue
            else:
                break
              
    # 判断从现在开始的子字符串是不是一个block
    # 判断方法：需要有完整的{}，而且还得考虑嵌套block的可能
    def is_block(self):
        curr_idx = self.idx
        jde = False
        self.skip_blank()
        # 一开始就得是一个{}包裹的字符串
        if self.peek != "{":
            jde = False
        
        balance = 1
        self.peek_next()
        while self.idx < self.len:
            if self.peek == "{":
                balance += 1
            elif self.peek == "}":
                balance -= 1
                
            self.peek_next()
            
        if balance == 0:
            jde = True
        
        self.idx = curr_idx
        self.peek = self.input[self.idx]
        return jde
      
    """
    block -> '{' decls stmts '}' 
    这里我也考虑了空白符
    """
    def block(self):
        self.skip_blank()
        
        if self._match("{") == False:
            return False
        # self.saved = self.top
        self.top = Env(self.top)
        self.print("{ ")
        
        self.skip_blank()
        self.decls()    # decls和stmts可以是空串，所以这里就不判断了
        self.stmts()
        self.skip_blank()
        
        if self._match("}") == False:
            return False
        
        # self.top = self.saved
        self.top = self.top.prev
        self.print("} ")
        return True
    
    # decls -> decls decl | ε
    # !TODO: 这玩意像是左递归的，能写出来嘛？
    # 尝试转换成右递归：
    # delcs -> decl decls | ε
    def decls(self):
        self.skip_blank()
        
        self.save()
        if self.decl() == False: # 对应的ε空串，作为返回条件
            self.load()
            return
        
        self.decls()

    def decl(self):
        self.skip_blank()
        # 啥也没有
        if self.peek in ["{", "}"]:
            return False
        
        # self.type()
        # type是终结子，就不再单独搞个函数了,不然不好实现语义动作
        lab = self.label()
        if lab == "":
            return False
        
        if lab in ["int", "char", "bool", "float", "double"]:
            s = Symbol(lab)
        else:
            # raise "error syntax: no *type* found"
            return False
        
        self.skip_blank()
        
        # self.id()
        lab = self.label()
        if lab == "":
            return False
        
        if lab not in ["int", "char", "bool" "float", "double"]:
            self.top.put(lab, s)
        else:
            # raise "error syntax: id"
            return False
        
        self.skip_blank()
        
        if self._match(";") == False:
            return False
        
        return True 
    
    def stmts(self):
        self.skip_blank()
        
        # self.save()
        if self.stmt() == False:
            # self.load()
            return
        
        self.stmts()
        
    def stmt(self):
        self.skip_blank()
        
        # 判断是不是block：是就递归match下去了，不是就要rollback
        self.save()
        if self.block() == False:
            self.load()
        else:
            # 是block
            return True
        
        # 不是block，则匹配factor ;
        if self.factor() == False:
            return False
        
        self.skip_blank()
        
        if self._match(";") == False:
            return False 
        self.print("; ")
        
        return True
        
    def factor(self):
        self.skip_blank()
        
        lab = self.label()
        if lab == "":
            return False
        
        if lab not in ["int", "char", "bool" "float", "double"]:
            s = self.top.get(lab)
            self.print(lab)
            self.print(":")
            self.print(s.type)
        else:
            # raise "error syntax: id"
            return False
        
    
    def save(self):
        self.save_idx = self.idx
        self.save_peek = self.peek
        
    def load(self):
        self.idx = self.save_idx
        self.peek = self.save_peek
     
        
    def _match(self, t):
        if self.peek == t:
            self.idx += 1
            if self.idx < self.len:
                self.peek = self.input[self.idx]
            else:
                # 到达最大长度后peek就不在继续下去了
                pass
            return True
        else:
            # raise("syntax error")
            return False

    def print(self, s):
        print(s, end="")
               
    def gen_symtable(self):
        self.reset()
        
        # program -> block
        self.top = None
        self.block()
        print("")
        
        
        # # program -> block
        # # 这是最开始的初始化，top设置为None
        # if self.is_block():
        #     top = None                
        # else:
        #     return False
        
        # while self.idx < self.len:
        #     # block -> "{"
        #     # 由于block嵌套，应该考虑递归什么的
        #     if self.peek == "{":
        #         saved = top
        #         top = Env(top)
        #         print("{")
        #     # block -> decls stmts "}"
        #     # !TODO: 这里应该只需要判断"}"就好了吧？
        #     elif self.peek == "}":
        #         top = saved
        #         print("}")
        #     # decls -> decls decl
            
        
        #     self.peek_next()
   
        
if __name__ == "__main__":
    t = SymAnalyzer("{ int x; char y; { bool y; x; y; } x; y; }")
    t.gen_symtable()
    
    t = SymAnalyzer("{ int x; int w; char y; { bool y; x; y; } x; y; w; }")
    t.gen_symtable()
    # print(t.is_block())

实现起来真麻烦。这里有要稍微吐槽一下了，上面的翻译法则，我个人觉得有点小小的问题。像2-25里面的语义动作是具体放在某个匹配的后面的，而这里为了整洁规矩，统一把语义动作放在了最后，这样实现绝对会出问题的。

然后就是，这个代码似乎已经不是预测语法分析器了，里面有一些rollback的操作在里面，有一种猜测的意味。

然后里面的什么用saved来保存父节点的操作我个人觉得也是有问题的，这样做似乎只能弹出临近的2个父子节点；应该使用Env里面的prev成员来获取父节点。

然后还有stmts和decls的递归问题。stmts -> stmts stmt的左侧永远都会一直递归下去，根本没法实现。应该改成右递归方案才能成功。

下面是修改后的翻译方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
program -> { top = null; } block			

block -> "{"				{ top = new Env(top); 
							print("{"); }
								
block -> decls stmts "}" 	{	top = top.prev; 
								print("}"); }
								
decls -> decl decls
	| ε
	
decl -> **type** { s = Symbol(type.lexeme); } **id*** ;	
								{ top.put(**id**.lexeme, s); }

stmts -> stmt stmts
	| ε
	
stmt -> block
	| factor ;				{ 	print("; "); }
	
factor -> **id**			{ 	s = top.get(**id**.lexeme); 
								print(**id**.lexeme); 
								print(";");
								print(s.type); }

待处理

  • 补全2.6之前的章节
  • 为2.6及其之前章节书上的Java代码进行研读，参考并改进Python实现
  • 完成前面的章节作业

参考

想初步了解编译原理？看这篇文章就够了 - 知乎 (zhihu.com)

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

A junior undergraduate
studying in the college of cyber science and engineering
in Sichuan University
in Sichuan , China.
Pronouns:He/him.
A core member of 0x401 CTF team
majorly focus on Reverse Engineering chanllenges.