词法分析器的Python实现

缘由

前两天收到个实验课的文档,要求写一个词法分析器,对类C语言代码进行词法分析。并给了我个CSDN的文章参考,也不知道是本身就有问题还是被她魔改之后该爆了,总之是运行不太正常,我想想反正不限定语言,不如干脆用Python写一个词法分析,再怎么说可读性应该也比C++高多了,说干就干呗。

思路

通常来说,代码都是按一行一个操作(刻意缩行除外),所以我们在读入之后,按每一行进行处理就可以了。

3
1
2
3
for line in code.split("\n"):
# 处理每一行
...

此外,因为我们这个是词法分析器,而不是语法分析器,所以对于语法是否正确并不需要进行判断,只要能准确的进行分词就可以了。
我们所分析的词分为两大类:字与符号;对于字又有三种:保留字、标识符、常数,我们需要分别进行处理。

对字的处理

首先是区分字与符号,这个很简单,只要用in来判断字符是否存在于ascii_lettersascii_digists就可以了。
但是字母往往是不会单独出现的,通常是一个单词(与数字)组成的保留字或标识符,所以我们需要定义一个变量word,来存放我们读到的单词,类似一个“缓冲区”的作用。

3
1
2
3
4
5
6
7
8
9
10
11
12
13
word = "" # 类似缓冲区的作用
flag = False # 标记是否为123这类常数
if letter in string.digits: # 判断当前是否为数字
flag = not bool(word) # 如果word里没有字符,而当前又读到了数字,那么就打上标记
word += letter # 将字符加入缓冲区
continue
elif letter in string.ascii_letters: # 判断当前是否为字母
if flag: # 如果打过了标记, 而此时读到了字母,标识符是不能以数字开头的,所以分开
output(word) # 输出数字
word = "" # 清空缓冲区
flag = False # 取消标记
word += letter # 将当前的字母加入缓冲区
continue

这里的flag是为了应付类似123这类常数的,因为标识符可以数字字母混合,但是只能是字母和下划线开头,不能以数字开头的。考虑3种情况:

  1. 纯字母 abc
  2. 常数 123
  3. 字母+数字混合 abc123

第一种情况,当读到字母时,首先判断是否已经打过标记,如果打过标记,说明之前读到过数字,所以先把数字处理掉,才能继续处理当前的字母
第二种情况,当读到数字时,要对flag进行赋值,not bool(word)word变量不为空的时候为False,意思是当前word变量中已经有字母(考虑到第三种情况)了,只需要继续加入缓冲区即可。反之为True意为当前为纯数字,为第三种情况做准备。
第三种情况,由上面的处理即可完成。

由此我们便对字进行了分离,分离出字之后就存在三种情况:保留字、标识符、常数。
常数我们处理过了,可以直接输出。而保留字我们定义了一个保留字表,只需要用in来判断下它是否存在于表中即可。

对符号的处理

其次是处理符号,符号相对字来说是比较容易处理的。

如果当前字既不是字母,也不是数字,那就只有两种情况:空白字符和符号。对于空白字符直接通过判断即可。

3
1
2
if letter in blank: # 如果当前为空白字符(空格、回车)则跳过
continue

首先先看一下word变量中是不是有东西,既然字中不含有字符,那么就先输出了再说

3
1
2
3
if word: # 判断缓冲区内是否有字符,有则输出
output(word)
word = ""

接下来处理注释,这里只对单行注释进行了处理,多行并不麻烦,但是没做要求我就不写了,各位如果有兴趣可以自己尝试一下。
因为是按行处理的,所以判断下当前符号和下一个字符是不是//,如果是就说明后面的内容全都是注释,直接跳过这一行即可。

3
1
2
if line[index:index + 2] == "//": # 处理掉注释
break # 直接break,跳出行迭代

因为有的符号是两个一组的,所以需要判断下当前字符是不是该行最后一个字符,如果不是,他又是否能和下一个字符组成一组符号。
如果能组成一组符号,那么下一个字符我们需要跳过,给_pass附上True,在循环头做判断即可(见完整代码)。

3
1
2
3
4
5
6
7
# 判断当前字符是否为最后一个以及和下一个字符能否组成一组符号
if index != len(line) - 1 and line[index:index + 2] in signs:
output(line[index:index + 2]) # 输出组合的字符
_pass = True # 跳过下一个字符
else: # 输出单个字符
output(letter)
word = "" # 清空缓冲区

输出

输出就没什么内容了,先假设他是常数,用int()转化下格式,如果真的是一个常数则会正常输出,如果不是常数,会抛出ValueError,用try-except捕捉下错误,再进行判断即可。

3
1
2
3
4
5
6
7
8
9
10
11
12
13
# 输出函数
def output(_str):
try: # 尝试是否能通过数字形式输出,如果能即为常数,否则为字符
print(f"{int(_str)}\t26")
except ValueError:
if _str in reserved_words: # 判断是否为保留字
print(f"{_str}\t{reserved_words.index(_str) + 1} 保留字")
word = ""
elif _str in signs: # 判断是否为符号
print(f"{_str}\t{signs[_str]}")
else: # 否则为标识符
print(f"{_str}\t25 标识符")
word = ""

完整代码

3
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
# -*- coding: utf-8 -*-
import string

letters = string.ascii_letters + "_"
# 空白字符
blank = " \n\r\t"
# 保留字数组
reserved_words = ["char", "int", "if", "else", "var", "return", "break", "do",
"while", "for", "double", "float", "short", "scanf", "case", "void"]
# 符号表
signs = {"=": 27, "<=": 28, "<>": 29, "<": 30, ">=": 31, ">": 32, "+": 33, "-": 34,
"*": 35, "==": 53, "/": 36, "//": 37, ":": 38, ";": 39, "(": 40, ")": 41,
"{": 42, "}": 43, "[": 44, "]": 45, "\"": 46, ",": 47, "'": 48, "!=": 49,
"&": 50, "&&": 51, "||": 52, "==": 53, "|": 54, "%": 55, "?": 56}

# 读入文件
with open("test.txt", "r") as file:
code = file.read()


# 输出函数
def output(_str):
try: # 尝试是否能通过数字形式输出,如果能即为常数,否则为字符
print(f"{int(_str)}\t26")
except ValueError:
if _str in reserved_words: # 判断是否为保留字
print(f"{_str}\t{reserved_words.index(_str) + 1} 保留字")
word = ""
elif _str in signs: # 判断是否为符号
print(f"{_str}\t{signs[_str]}")
else: # 否则为标识符
print(f"{_str}\t25 标识符")
word = ""


for line in code.split("\n"): # 按行迭代
word = "" # 类似缓冲区的作用
flag = False # 标记是否为123这类常数
_pass = False # 标记是否跳过这一个字符
for index, letter in enumerate(line):
if _pass: # 判断是否跳过当前字符
_pass = False
continue
if letter in string.digits: # 判断当前是否为数字
flag = not bool(word) # 如果word里没有字符,而当前又读到了数字,那么就打上标记
word += letter # 将字符加入缓冲区
continue
elif letter in letters: # 判断当前是否为字母
if flag: # 如果打过了标记, 而此时读到了字母,标识符是不能以数字开头的,所以分开
output(word) # 输出数字
word = "" # 清空缓冲区
flag = False # 取消标记
word += letter # 将当前的字母加入缓冲区
continue
else: # 此时当前字符既不是数字也不是字母,为符号或空白字符
if word: # 判断缓冲区内是否有字符,有则输出
output(word)
word = ""
if letter in blank: # 如果当前为空白字符(空格、回车)则跳过
continue
if line[index:index + 2] == "//": # 处理掉注释
break # 直接break,跳出行迭代
# 判断当前字符是否为最后一个以及和下一个字符能否组成一组符号
if index != len(line) - 1 and line[index:index + 2] in signs:
output(line[index:index + 2]) # 输出组合的字符
_pass = True # 跳过下一个字符
else: # 输出单个字符
output(letter)
word = "" # 清空缓冲区

测试所用代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
int maxs = max(a, max(b, c));
printf("%d", maxs);
}

int max(int x,int y)
{
int t;
t = x > y ? x : y;
return t;
}

输出

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
int     2 保留字 
main 25 标识符
( 40
) 41
{ 42
int 2 保留字
a 25 标识符
, 47
b 25 标识符
, 47
c 25 标识符
; 39
scanf 14 保留字
( 40
" 46
% 55
d 25 标识符
% 55
d 25 标识符
% 55
d 25 标识符
" 46
, 47
& 50
a 25 标识符
, 47
& 50
b 25 标识符
, 47
& 50
c 25 标识符
) 41
; 39
int 2 保留字
maxs 25 标识符
= 27
max 25 标识符
( 40
a 25 标识符
, 47
max 25 标识符
( 40
b 25 标识符
, 47
c 25 标识符
) 41
) 41
; 39
printf 25 标识符
( 40
" 46
% 55
d 25 标识符
" 46
, 47
maxs 25 标识符
) 41
; 39
} 43
int 2 保留字
max 25 标识符
( 40
int 2 保留字
x 25 标识符
, 47
int 2 保留字
y 25 标识符
) 41
{ 42
int 2 保留字
t 25 标识符
; 39
t 25 标识符
= 27
x 25 标识符
> 32
y 25 标识符
? 56
x 25 标识符
: 38
y 25 标识符
; 39
return 6 保留字
t 25 标识符
; 39
} 43

总结

词法分析器不是什么难的东西,只要理清思路很容易就能写出来,对于Python新手锻炼自己的编程能力也是一个很好的练手项目。