记一次编译原理实验——词法+语法&语义分析(Python实现)
编译原理是每个CS学子的必修课。编译原理的实验课对提高我们对编译过程的理解很重要。
本文章写于实验结束后，所有代码已上传至Github : https://github.com/kabu1204/compilation。
建议拉到底下点击阅读原文，微信排版不行，表格内的公式加载不出来，而且LATEX的换行符失效。
水平有限，如有问题还望指正。
环境：Python 3.6.9
-
词法分析器
-
语法分析——LR(1)的强大
-
语义分析
文法改写
预先定义的一些东西
真链 假链 回填
语义动作
运行结果
词法分析器
一个编程语言的词法通常用正规文法描述，由正则表达式表示，使用DFA进行识别，三者在描述能力/识别能力上是等价的。
事实上，正则表达式的匹配就是使用DFA作为引擎的，当然也有NFA引擎。
在这一部分，我们要设计并实现SAMPLE语言的词法分析器，自然，设计的重点是其识别工具：DFA.
当然我们也可以直接使用正则表达式进行匹配，但这对我们理解DFA的原理并无裨益，不过我还是用到了RE库来实现源程序文本的切分。
下面介绍一下我实现词法分析器的过程。
预处理
读入的源程序实际上是一个字符串，而词法分析的对象是一个个单词(包括界符)。显然，能将其分为一个一个具有独立意义的单词，更便于我们的处理。
为了实现切分，我们先介绍一个函数re.split()
re.split()
re.split(pattern:AntStr, string:AnyStr)
第一个参数pattern是划分依据的正则表达式，第二个参数string是要进行划分的字符串。
>>> s="var A;B;C:integer;"
>>> re.split(r";",s)
['var A', 'B', 'C:integer', '']
如果字符串最后一个字符是被切分字符，则切分时还会产生一个''字符
>>>re.split(r"[;:]",s)
['var A', 'B', 'C', 'integer', '']
>>>re.split(r"(;)",s)
['var A', ';', 'B', ';', 'C:integer', ';', '']
此时默认保留切分符
>>>re.split(r"(?:;)",s)
['var A', 'B', 'C:integer', '']
>>>re.split(r“(in)",s)
['var A;B;C:', 'in', 'teger;']
>>>re.split(r"(in|er|[A-C]|[;:])",s)
['var ', 'A', '', ';', '', 'B', '', ';', '', 'C', '', ':', '', 'in', 'teg', 'er', '', ';', '']
那么对于源程序，我们切分的依据又是什么呢？
- 首先想到的肯定是各种空白字符：”\n“,"\t","\n"等。由于本实验所分析的文法
对缩进是不敏感的，因此在使用这些空白字符进行划分时，我们无需保留它们。
使用\s匹配所有单个空白字符，等价于[\f\n\r\t\v]
import re
with open(file_path,'r') as f:
raw=f.read()
print(raw)
print(re.split(r"\s",raw))
运行结果
program example2;
var A,B,C:integer;
X,Y:bool;
begin /* this is an example */
A:=B*C+37;
X:='ABC'
end.
['program', 'example2;', 'var', '', 'A,B,C:integer;', '', '', '', '', '', 'X,Y:bool;', 'begin', '', '/*', '', 'this', '', 'is', '', 'an', '', 'example', '', '*/', '', '', 'A:=B*C+37;', '', '', "X:='ABC'", 'end.', '']
可以看到，很多保留字、标识符等还和;，:,:=这些界符黏在一起，我们还要进一步切分
但是请注意，我们不能直接把所有界符当作切分符，因为双界符通常由两个单界符构成，放在一起切分会拆开双界符。
import re
with open(file_path,'r') as f:
raw = f.read()
PreSplit = re.split(r'(<>|<=|>=|:=|/\*.*\*/|\.\.|\s)', raw)
print(PreSplit)
运行结果
['program', ' ', 'example2;', '\n', 'var', ' ', '', ' ', 'A,B,C:integer;', '\n', '', ' ', '', ' ', '', ' ', '', ' ', '', ' ', 'X,Y:bool;', '\n', 'begin', ' ', '', ' ', '', '/* this is an example */', '', '\n', '', ' ', '', ' ', 'A', ':=', 'B*C+37;', '\n', '', ' ', '', ' ', 'X', ':=', "'ABC'", '\n', 'end.', '\n', '']
- 然后我们还可以把一些不参与构成双界符的单界符(如
+,-,(,']'等)也加入：
import re
with open(file_path,'r') as f:
raw = f.read()
PreSplit = re.split(r'(<>|<=|>=|:=|/\*.*\*/|\.\.|[\+\-\(\)\[\];,\s])', raw)
print(PreSplit)
运行结果
['program', ' ', 'example2', ';', '', '\n', 'var', ' ', '', ' ', 'A', ',', 'B', ',', 'C:integer', ';', '', '\n', '', ' ', '', ' ', '', ' ', '', ' ', '', ' ', 'X', ',', 'Y:bool', ';', '', '\n', 'begin', ' ', '', ' ', '', '/* this is an example */', '', '\n', '', ' ', '', ' ', 'A', ':=', 'B*C', '+', '37', ';', '', '\n', '', ' ', '', ' ', 'X', ':=', "'ABC'", '\n'
