编译原理-Week1
·151 words·1 min
Table of Contents
编译器的结构 #
-
词法分析
- 例如给定语句
if x=y then z=1;else z=2;
,则可以分析得到分解树,他的根是if-then-else
;下分predicate
then
else
三个孩子。这三个孩子分别都能解析成三个语句,分别是relation
和两个assign
,他们又分别能分解成 语句前部、后部。 - 可见,这种分析是一种递归的过程。
- 例如给定语句
-
类型转换
-
语义分析
-
计算机很难做到这一点。
-
例如 Jack said Jerry left his homework at home.那么到底是Jack的作业,还是Jerry的作业,还是其他人的作业呢?不知道。
-
这种只有能通过上下文才能得到的分析,就是语义分析。一般情况下,例如变量的类型分析就是这样得来。
-
因此,编程语言一般对可能导致模棱两可的情况进行非常谨慎的处理。例如C++中变量的作用域。
-
int main(){ int test=3; while(true){ int test=4; cout<<test; } } //这里,就是对test变量进行了严格的作用域限制。
-
-
优化
- 一个优化错误的例子:
X=Y*0
和X=0
在浮点的情况下是不等价的。因为纯0代表NaN。这样就导致Y*0=NaN
。
- 一个优化错误的例子:
-
代码生成
词法分析 #
Token Classes和Token #
- 编程语言的Token Classes,也就是一个字符串扮演的角色情况。不同的Token Class就相当于英语中不同的语法成分,例如主谓宾。
- Identifier标识符
- 非数字开头的字符串
- Number数字
- Operator操作符
- Keyword关键词
- 例如if else
- WhiteSpace空格
- 例如空格、换行符
\n
、tab符\t
等。
- 例如空格、换行符
- Identifier标识符
- 词法分析器Lexical Analysis的作用:Tokenize
- 处理各字符串,并分别构成字符串+Token Class的二元组,传递给下一级。其中,这个二元组叫做Token,它携带了这个字符串的内容和他是什么成分这两种信息。
正则语言 - Regular Languages #
- 元素的基本定义
- 字符集 $\sum$:是一些字符构成的集合。可以用其中的字符来构成字符串,从而生成语法。一定要注意它是字符的集合,不是字符串。
- 单字符:例如字符c,就代表了一个表示为
{c}
的字符集。 - 空:记作 $\epsilon$. 代表了一个表示为
{}
的字符串。 - 并(加):例如
A={a}.B={b,c}.则A+B={a,b,c}
. - 连接(积):定义是 $AB={ab|a\in A\and b\in B}$.
- 闭包(迭代):$A^*=\sum A^i(i\in[0,\inf))$.
- 注意,i可以取到0,这就意味着 $A^*=\epsilon+A+A^2+…$.
- 排0闭包: $A^+=AA^*$.
- 可选A,记作 $A?$,表示为 $A?=A^++\epsilon$.
- 范围表示,${0,1,2,3,4,5,6,7,8,9} =[0-9]$.
- 范围补集,${0,1,2,3,4,5,6,7,8,9} $补集=
[^0,9]
.
- 例子
- 设$\sum={0,1}$,则有 $1^*={\epsilon,1,11,111,…}$.
- 此外,有 $(0+1)^={0,1}^=\sum^*=\epsilon+(0+1)+(0+1)^2+…+(0+1)^i$.
- 注意,这就看出递归定义了。因为只要是 $(0+1)$出现的地方,实际上就是 ${0,1}$,也就是它可以由0或1中的任意一个字符代替。所以,它递归定义了这个01字符集上的任意字符串。
- 而且,可以看出,因为 $(0+1)^$和 ${0,1}^$是一个意思,所以同一种grammer的表示方法并不唯一。
语言到语义的映射 #
- 语言到语义是多对一映射。比如2+3和1+4表示的结果是一样的。又比如II和2表达的意思是一样的,又比如 $(0+1)^*={0,1}$.
- 但是注意,不可能存在一对多的情况,否则程序就会出现未定义行为。
使用正则语言表达任意的需要匹配的模式(例) #
- 首先方便起见,定义:
- $digit={0,1,2,3,4,5,6,7,8,9} =[0-9]$.
- $digits=digit^+$.
- $letter={a,b,…,z,A,B,…,Z} =[a-z]+[A-Z]$.
- 表达标识符:要求以字母开头,之后可以是字母或数字。
- $letter\times (digit+letter)^*$.
- 表达电子邮件:要求xxx@xxx.xxx。
- $(letter+digit)^+\times @\times (letter+digit)^+\times . \times letter^+$,简记作 $(letter+digit)^+@ (letter+digit)^+.letter^+$.(即:可以不把乘号写出来。)
- 总结
- 可以空,则用闭包即可生成集合上的任意字符串,**或者可以用除零的闭包加上 $\epsilon$ ;**否则如果要求非空,就要用除零闭包去生成集合上的任意字符串。
- 如果要连接字符串(即模式中的不同组成部分),则用乘法;如果要描述集合的字符组成范围,则用加法。
正则表达式匹配模式的原则 #
- 首先,把这个编程语言所有的正确的模式的正则都进行相加,得到一个大的正则。于是,只要是与这个正则相匹配的输入就必然是没有问题的。
- 接受了输入x1…xn,从左往右扫描,只要其中有x1…xi匹配成功,就把x1…xi从原输入中剔除,并把剩余部分重新作为输入。重复这个过程,直到都匹配完成。这样一来,就完成了词法分析。
- 几个问题
- 遇到非法输入,如何报错?如果存在非法输入,按照上面的规则,不就卡住了吗?因为不可能匹配,所以算法不可能退出。解决方式是:把这个编程语言的所有非法输入也做成一个大的正则,然后把这个正则放到优先级最低的位置。这样,只要前面那些正确的正则没匹配成功,才来匹配这个错误的。于是就匹配成功,就给出报错。
- 如何区分
=
和==
?当有多个模式可以匹配时,采取最长匹配原则。 - 如何区分标识符和关键字?例如
if
为什么不被Tokenize成标识符?解决方式仍然可以采用优先级匹配原则,让关键字的优先级大于标识符即可!