1. 编译的五个阶段
词法分析, 语法分析, 语义分析和中间代码生成, 代码优化, 目标代码生成
2. 文法的定义
语言的文法是一组规则,包含词法规则(==单词==构成)和语法规则(==语法单位==构成).
形式化定义:G[S] = (Vn, Vt, P, S)
Vn:非终结符, Vt:终结符, P:产生式, S:开始符号
3. 文法的分类
(1). 0型文法
无限制文法
(2). 1型文法
上下文有关文法
左部符号的个数不能多于符号的个数.
上下文有关体现在产生式的一般形式为: a1 A b1 -> a1 B b1
(3). 2型文法
上下文无关文法
推导中只对单个的非终结符进行替换
(4). 3型文法
正则文法
左线性和右线性
4. 句型和句子
推导过程中的每一行都叫做句型,最后一行叫做句子.(句子同时也是句型)
5. 短语,直接短语,句柄,素短语
短语:经过任意步规约为一个非终结符的符号串.
直接短语:在短语的基础上,只能进行一步规约.
句柄:最左直接短语(产生式中最左侧的能进行规约的第一个产生式)
素短语:一个短语,至少包含一个终结符,不包含其他素短语(与直接短语的区别,直接短语不一定包含终结符)
6. 正则式 -> NFA -> DFA
(1). 正则式 -> NFA
(2). NFA -> DFA
NFA中每一个状态都是单独的,而在DFA中,将每一个节点看做一个状态集.
取得每一个状态集的方法是将节点状态集中的状态取出,假设此时计算经过a后的节点也就是状态集.计算状态经过a弧所到达的所有节点,然后将所有ε弧连接的节点页接纳进来,对状态集中的所有节点做这样的操作,就可以得到新的节点.
Ia = ε-closure(move(I, a))
7. NFA和DFA的区别
NFA对某一输入可以有0-多个到达状态
NFA可以有ε边
NFA可以有多个开始状态
8. 自上而下语法分析
(1). 消除左递归
A->βααααααα...... ===> A -> βA' 其中 A'->αααααα....
多个式子产生的左递归需要将式子带入,然后再消除.
(2). FIRST集的构造
FIRST(A)指A经过任意步推导中,所有出现在第一个的终结符的集合.(A等价的所有串的首字符)
(3). FOLLOW集的构造
FOLLOW(A)是指任何一个可能出现在A后面的非终结符的集合.
(4). SELECT集的构造
SELECT(A->β)是指可以选用该产生式进行推导时对应的输入符号集合.
一般情况下SELECT(A->β) = FIRST(β),当FIRST(β)中包含空串时,还需要加上FOLLOW(A)
(5). 预测分析表
行表示输入符号和#结束符(a),列表示非终结符(A).每一项表示当前非终结符遇到输入符号时可以使用的产生式.
构造方法就是在A作为左部的所有SELECT集中将对应元素列的位置填入产生式.
使用时,先给分析栈中压入开始符号,然后根据输入符号进行推导
9. 自下而上语法分析
(1). 算符优先文法分析
1). FIRSTVT集和LASTVT集
FIRSTVT(A)是指在A为左部的产生式中(可以有等价的产生式),右部中出现的第一个终结符的集合.
LASTVT(A)同理,最后一个非终结符.
2). 算符优先关系表
如果有...aA...,那么有a<·FIRSTVT(A);
如果有...Aa...,那么有LASTVT(A)·>a;
3). 最左素短语
将句型中的所有运算符从左到右排列,找到第一个<· * ·> 这样的终结符*(中间可以有相等),连同左右的非终结符一起作为最左素短语.进行规约
[图片上传失败...(image-55803e-1582269347002)]
(2). 移进规约分析
将每一个产生式按照点(·)划分为不同的项目.点的右边如果是非终结符,那么以这个非终结符的移进态项目是等价项目.
按照接收符号,构造DFA,
1). LR(0)语法分析
按照上面的DFA,构造预测分析表:
[图片上传失败...(image-686c8b-1582269347002)]
2). SLR(1)语法分析
当一个等价项目中同时包含移进项目和规约项目,那么规约项目的rx的填写只能填写产生式左部的FOLLOW集中的字符对应的位置.
3). LR(1)语法分析
当待规约非终结符的FOLLOW集和移进符号有相交时,不能使用SLR(1)分析.
LR(1)分析中构造DFA时,节点中的非终结符的等价项目要记录原项目该非终结符后面的符号作为预测.
构造预测分析表时,在规约时,只在之前新增的预测符号处填写rx.
10. 三地址代码
(1). 常见形式
四元式:(运算符, 操作数1, 操作数2, 保存到结果)
三元式: (序号) (运算符, 操作数1, 操作数2) 后面需要使用当前表达式的结果时,使用序号代替
间接三元式:执行表+三元式,通过赋值操作和执行表重复执行代替一些操作
(2). 单目算符的表示
变址取数:
a = x[i] 表示为 (100) (=[], x, i)
(101) (assign, a, (100))
x[i] = a 表示为 (100) ([]=, x, i)
(101) (assign, (100), a)
(3). 数组元素的表示
多维数组计算出一维下标,然后直接取.
(4). 条件语句
1). 无条件跳转
(100) (j, _, _, 101)
(101) ...........
2). 条件跳转
(100) (j>, a, b, 101)
(101) ...........
(5). 循环语句
空值条件跳转完成
