?
预处理器编译器汇编器装配连接编辑骨架程序源程序目标汇编程序可重定位机器代码绝对机器码可重定位目标文件库语言处理过程编译逻辑过程
词法分析
语法分析
语义分析
中间代码生成
中间代码优化
目标代码生成
目标代码优化出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理认知层次代码优化目标程序运行时的存储组织和代码生成语法制导翻译和中间代码生成符号表和静态语义分析自底向上分析程序自顶向下分析程序语法分析程序词法分析程序
PL/0编译程序剖析课程目标
基本理论正规式，有穷自动机上下文无关文法及其句型分析属性文法
基本知识程序设计语言有关概念 (作用域，类型）
如何设计编译器（前后端，中间语言，分遍）
基本技能
（使用工具）实现编译器
进一步研究的基础代码优化编译器后端的设计和实现正规式，有穷自动机
正规式－正规集的描述机制字母表?上的正规表达式 R的文法,终结符是 { |,*,a }.
0) R –>? 2) R –> RR 4) R –> a
1） R –> R | R 3) R –> R*
有穷自动机－正规集的识别机制程序设计语言的单词都能用正规式 来定义,
例 3.1
令?={l,d},则?上的正规式 r=l(l?d)?定义的正规集为,{l,ll,ld,ldd,…… },其中 l代表字母,d代表数字,正规式 即是 字母 (字母 |数字 )?,它表示的正规集中的每个元素的模式是,字母打头的字母数字串,,就是 Pascal和 多数程序设计语言允许的的标识符的词法规则,
例 3.2
={d,?,e,+,-},
则?上的正规式 d?(?dd )(e(+?-)dd)
表示的是无符号数的集合。其中 d为 0~9的数字。
有穷自动机确定的有穷自动机 DFA
不确定的有穷自动机 NFA
NFA的确定化
DFA的最小化文法和语言如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。
识别方式 （自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）
定义文法 G定义为四元组 (VN,VT,P,S )其中
VN:非终结符号 (或语法实体，或变量 )集；
VT:终结符号集；
P:产生式 (也称规则 )的集合；
VN,VT和 P是 非空有穷集。
S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。
VN和 VT不含公共的元素，即 VN ∩ VT = φ
用 V表示 VN ∪ VT,称为文法 G的字母表或字汇表规则,也称 重写规则,产生式 或 生成式,是形如
→?或?∷ =?的 (?,?)有序对，其中?是字母表 V
的正闭包 V+中的一个符号,?是 V*中的一个符号。
称为规则的左部,? 称作规则的右部。
文法，语言的定义由文法 G生成的语言记为 L(G),它是文法 G
的一切句子的集合,
L(G)={x|S =>* x，其中 S为文法的开始符号，且 x ∈V T*}
例,G,S→ 0S1,S→ 01
L(G)={0n1n|n≥ 1}
文法的类型通过对产生式施加不同的限制,Chomsky将文法分为四种类型：
0型文法：对任一产生式 α → β,都有
α ∈(V N∪V T)+,β ∈(V N∪V T)*
1型文法,对任一产生式 α → β,都有 |β |≥| α |，
仅仅 S→ ε 除外
2型文法,对任一产生式 α → β,都有 α ∈V N
3型文法,任一产生式 α → β 的形式都为 A→aB 或
A→a,其中 A∈V N,B∈V N,a∈V T *
上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树 ---句型推导 的 直观表示语法树 ---句型推导 的 直观表示给定文法 G=(VN,VT,P,S)，对于 G的任何句型都能构造与之关联的语法树 (推导树 )
定理：
G为上下文无关文法，
对于 α ≠ ε,有 S =>* α,当且仅当文法 G有以 α 为结果的一棵语法树 (推导树 )
句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型,是某个 推导 的构造过程。
在语言的编译实现中，把 完成句型分析 的 程序 称为 分析程序 或 识别程序 。分析算法又称 识别算法 。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
句型的分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,反复使用文法的产生式,寻找 与 输入符号串 匹配 的 推导 。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
句型分析的有关问题
1）在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？
2）在自下而上的分析方法中 如何 识别可归约的串？
在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为,可归约串,
自下而上的分析方法
OPG
LR分析器及其自动构造自上而下
LL(1)分析器及其自动构造预测分析程序 Predictive parser无回溯的自顶向下分析程序特征 ——根据下一个输入符号为当前要处理的非终结符选择产生式要求 ——文法是 LL(1)的第一个 L 从左到右扫描输入串第二个 L 生成的是最左推导
1 向前看一个输入符号（ lookahead)
预测分析程序的实现技术
1 递归下降子程序
2 表驱动分析程序表驱动 予测分析程序模型
Input
#
总控程序预测分析表
stack
一个文法 G是 LL（ 1）的，当且仅当对于 G的每一个非终结符Ａ的任何两个不同产生式Ａ? α?β,
下面的条件成立：
１,FIRST（ α ） ∩FIRST( β )=?,也就是 α?和 β 推导不出以同一个终结符 a为首的符号串；它们不应该都能推出空字?．
２,假若 β =>*?，那么，
FIRST（ α )∩FOLLOW （ A）＝?,也就是，
若 β =>*?.则 α 所能推出的串的首符号不应在
FOLLOW(A）中．
．
ＬＲ分析特定的一种 shift-reduce实现技术能力强几乎所有 CFG的语言结构都能用 LR分析不需要对文法附加条件难点几乎不可能用手工编写 LR分析器现实有 LR分析器的生成器
ＬＲ分析 器模型
L 从左到右扫描输入串 R 构造最右推导总控程序 output
Input$(#)
…
栈
ACTION GOTO
LR分析表产生式表
ＬＲ 分析特征
栈顶状态为 S,当前输入符号是 a时做什麽 ---?有穷狀态自动机
规范推导例 6.1G[S]为,
S?a A c B e
A?b
A?Ab
B?d
1)构造识别活前缀的 DFA
2)构造它的 LR(0)分析表。
3)分别给出对输入 符号串 abbcde和
Abbbce的 LR(0)分析步骤。
G[S]拓广 为,
S’? S
S?a A c B e
A?b
A?Ab
B?d
I0,S’ S
S a A c B e
I1,S’? S? I2,S? a?A c B eA b
A Ab
I3,S? a A? c B e
A? A? b
I4,A? b?
I5,S? a A c? B e
B d I7,S? a A c B? e
I8,B? d? I9,S? a A c B e?
I6,A? A b?
S a
A
b b
c
B
ed
G[L]= ab+ cde
例 6,1 G[S]的 LR(0)分析表
AC T I O N GO T O
a c e b d # S A B
0 S
2
1
1 a cc
2 S
4
3
3 S
5
S
6
4 r
2
r
2
r
2
r
2
r
2
r
2
5 S
8
7
6 r
3
r
3
r
3
r
3
r
3
r
3
7 S
9
8 r
4
r
4
r
4
r
4
r
4
r
4
9 r
1
r
1
r
1
r
1
r
1
r
1
SLR(1)技术
如果 LR(0) 项目集规范族中某个项目集 IK含 移进 /归约 归约 /归约 冲突：
IK,{,..A→ α,bβ,P? ω,,Q,,… }
若 FOLLOW(Q)? FOLLOW(P) =?
FOLLOW(P)? { b } =?
FOLLOW(Q)? { b} =?
则解决冲突的 SLR(1)技术：
action [ k,b ] = 移进对 a?FOLLOW (P) 则 action [ k,a ] =用 P? ω 归约对 c?FOLLOW (Q) 则 action [ k,c ] =用 Q 归约
能用 SLR(1)技术 解决冲突的文法称为 SLR(1)文法。
SLR(1)文法是无二义的。
SLR（ 1）的局限在 SLR 分析中,若项目集 Ik含有项目 A →?.
,那么在相应的状态下,只要当前输入符号 a?follow(A) 集,就确定采用 A→?进行归约,但在某些情况下,当状态 k呈现于栈顶时,栈内的串所构成的活前缀未必允许把?归约为 A,.因为可能没有一个右句型含有前缀?Aa.即在这种情况下,用 A →?
归约未必有效,
.所以需要扩充状态以包含更多的信息,follow 集的哪些部分才是进到该状态最恰当的归约依据,
重新定义项目,
LR（ 1）方法若 A,B I
则 B?, I
（ B 是一产生式）
把 FIRST（?）中的符号作为用 B 归约的搜索符,向前搜索符,
LR（ 1）项目 ( 配置）的一般形式
– [ A,?,a ]
意味着处在栈顶是?的相应状态，期望相应?在栈顶的状态，
然后只有当 跟在?后的 token是终结符 a时进行归约 。 a
称作该 项目 ( 配置） 的向前搜索符（ lookahead ）
向前搜索符（ lookahead ）只对圆点在最后的项目起作用
A –>,a
.意味着处在栈中是的相应状态，但 只有当下一个输入符是 a时才能进行归约,a 要么是一个终结符，要么是输入结束标记 #
有多个 向前搜索符，比如 a,b,c时，可写作 A –> u?,a/b/c
二义文法例,G‘[E]:
E → i
E → E+E
E → E*E
E → (E)
E
E + E
E * E i
i i
E
E * E
i E + E
i i
句型 i*i+i 的两个不同的最左推导：
推导 1,E? E+E? E*E+E? i*E+E? i*i+E? i*i+i
推导 2,E? E*E? i*E? i*E+E? i*i+E?i*i+i
一棵语法树表示了一个句型的种种可能的
(但未必是所有的 )不同推导过程，包括最左 (最右 )推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左 (最右 )推导呢?
二义文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义 的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是 二义 的判定任给的一个上下文无关文法是否二义，
或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，
但可以为无二义性寻找一组充分条件应用二义文法的不同途径二义文法
1 OPG分析
2 LR分析
3 LL分析重写文法,得到等价无二义文法
1 OPG分析
2 LR分析
3 LL分析二义文法途径 1 根据算符优先性和结合性重写文法
G([E]),
E –> E + E | E * E | (E) | id 重写
E? E+T |T T? T*F|F F?(E) | id
G([S]):
S? if Expr then Stmt else Stmt | if Expr then
Stmt | Other…
brevity as:
S –> iSeS | iS | a
重写
S –> M | U
M –> iMeM | a
U–> iS | iMeS
LR方法 应用二义文法 E –> E + E | E * E | (E) | id
Parsing input,id + id * id
E? E + E
id + E
id + E * E
id + id * E
id + id * id
E? E * E
E + E * E
id + E * E
id + id * E
id + id * id
I 0,E' –>?E
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 1,E' –> E?
E –> E? + E
E –> E? * E
I 2,E –> (?E)
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 5,E –> E*?E
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 6,E –> (E?)
E –> E? + E
E –> E? * E
I 7,E –> E + E?
E –> E? + E
E –> E? * E
I 3,E –>id?
I 4,E –> E+?E
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 8,E –> E * E?
E –> E? + E
E –> E? * E
I 9,E –> (E)?
.
二义性文法在ＬＲ分析中的应用
例表达式文法：
E’?E
E?E+E
E?E*E
E?(E)
E?i
二义性文法不是 LR文法，
但是对某些二义性文法,人为地给出优先性和结合性可能构造出更有效的 LR分析器如,规定在表达式文法中
i的 优先性最高
‘ *’ ·＞ ‘＋’
‘ *’和 ‘＋’ 都 服从左结合不用重写文法利用 precedence rules和 left(right)associativity.
解决 I1,I7,I8中 存在移进 -归 约冲突
I1,E’?E?
E?E?+E
E?E?*E
I7,E?E+E?
E?E?+E
E?E?*E
I8,E?E*E?
E?E?+E
E?E?*E
I1,移进 和 接受 无 冲突
I7,I8用 优先关系 和 结合性 解决冲突。
规定：‘ *’ 优先于‘ +’，
都服从 左 结合
I7,遇‘ *’ 移进遇‘ +’ 归 约
I8,遇‘ +’，‘ *’ 都 归 约
0 S2 S3 1
1 S4 S5 acc
2 S2 S2 6
3 r4 r4 r4 r4
4 S2 S3 7
5 S2 S3 8
6 S4 S5 S9
7 r1 S5 r1 r1
8 r2 r2 r2 r1
9 r3 r3 r3 r3
ACTION GOTO
+ * ( ) i # E
状态二义性表达式文法的 LR分析表
LL(1)方法
消除左递归和提左公因子并不一定都能将 非 LL(1)文法改造 为 LL(1)
的
S → if C t S |
if C t S e S
C →b
提左因子
S → if C t S A
A→ e S |?
First集 Follow集
S if #,e
A e,? #,e
C b t
M[A,e]={A→ e S
A→? }
属性文法属性文法 (attribute grammar)是一个三元组,A=(G,V,F),其中
G:是一个上下文无关文法
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等,属性与变量一样，可以进行计算和传递。
属性加工的过程即是语义处理的过程。
F:关于属性的属性断言或一组属性的计算规则 (称为语义规则 ),断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性,
属性有两种 继承的和综合的属性属性通常分为两类：综合属性和继承属性 。 简单地说,综合属性用于,自下而上,传递信息,而继承属性用于
,自上而下,传递信息 。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由属性计算器的参数提供 。
A?X1 X2 … Xn
A的综合属性,计算 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性,计算 T(Xj):=f(I(A),..,I(Xn))
1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,
2)终结符只有综合属性,它们由词法程序提供,
继承属性
一个结点的继承属性值是由此结点的父结点和 /或兄弟结点的某些属性来决定的。
例 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
D
L.in= real
L.in= real
L.in= real
T.type=real
real
id2
id1
id3
.
Real id1,id2,id3
每个 L结点都带有继承属性的语法树
，
，
P –> DS
D –> var V; D |?
S –> V,= e; S |?
V –> x | y | z
现在使用两个属性,name和 dl，每当一个新的变量声明时，就把它的 name
属性附给它,name属性是综合属性。
将所声明的变量都放到一个变量名字清单中（用语义函数 addlist实现），用属性 dl综合声明块中声明的所有变量。然后这个 dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中
P –> DS {S.dl,= D.dl}
D1 –> var V; D2 |? {D1.dl,= addlist(V.name,D2.dl)} | {D1.dl,= NULL}
S1 –> V,= e; S2 |? {check(V.name,S1.dl); S2.dl,= S1.dl}
V –> x | y | z {V.name,= 'x'} | {V.name,= 'y'} | {V.name,= 'z'}
var x； var y； y:=E；
P
D dl={x,y} S dl={x,y}
var V ； D dl={y} V,= E ； S
x var V ； D dl={ } y?
y?
Yacc或 bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号 $$表示产生式左端的属性，
$n表示存取产生式右端第 n个文法符号相联的属性如上例作为 Yacc的输入，可写成：
P → DS {$2.dl=$1.dl}
D1 → var V ； D{$$.dl=addlist($2.name,$4.dl)}
| {$$.dl=null}
S1 → V:=e ； S{check($1.name,$$.dl)；
$5.dl=$$.dl}
|
V → x {$$.name= ’x’}
|y {$$.name=’y’}
|z {$$.name=’z’}
语法制导的翻译
一个 翻译 是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。
各个编译阶段都定义一个翻译，
词法分析,（字符串，单词串）
语法分析,（单词串，语法树）
语义分析,（语法树，语法树）
中间代码生成 （语法树，中间代码）
目标代码生成 （中间代码，汇编语言）
语法制导的翻译 －在语法分析的同时完成翻译工作扩展ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 符号
ACTION GOTO
LR分析表产生式表
Vm
V1
-
语义
…
S0
目标程序运行时的存储组织代码生成前如何安排目标机资源运行时组织的几个问题数据表示 -如何在目标机中表示每个源语言类型的值表达式求值 -如何组织表达式的计算存储分配 -如何组织不同作用域变量的存储过程实现 -如何以例程实现过程，函数，参数传递任务：编译程序对目标程序运行时的组织（设计运行环境和分配存储） 如 通常存储区布局可为：
目标代码区静态数据区
Stack
heap
栈式分配方案过程 (嵌套和不嵌套 )的语言主要特点,
过程的 AR
过程嵌套
（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。
（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。
关键技术：解决对非局部量的引用（存取）。
设法跟踪每个外层过程的最新活动记录
AR的位置。
跟踪办法：
用静态链（如 PL/0的 SL）
用 Diplay表参数传递
(1)procedure exchangel(i,j:integer);
(2) var x:integer;
(3) begin;
(4) x:=a[i]; a[i]:=a[j]; a[j]:=x
(5) end;
带有非局部变量和形参的 PASCAL过程非局变量 a[i]和 a[j]的 值进行交换,i,j为形参（在这里是传值）
传值 的实现
1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。
2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。
3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。
传地址 的实现
（ call- by- reference )(call-by-address)(call-by-
location)
把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：
1实在参数是一个名字，或具有左值的表达式 ----
传递左值
2实在参数是无左值的表达式 ----计算值，放入一存储单元，传此存储单元地址
3目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用堆式动态存储分配
需求：
– 一个程序语言允许用户自由地申请数据空间和退还数据空间，或者不仅有过程而且有进程（ process）
的程序结构，
操作：
– 堆提供两个操作，分配操作和释放操作
情况,
– 经一段运行时间之后，这个大空间就必定被分划成许多块块，有些占用，有些无用（空闲） --碎片问题程序语言允许用户自由地申请数据空间和退还数据空间
C++语言中 new操作符施加在一个类型标识符上 （ 包括类名 ）
Pascal语言中,标准过程 new能够动态建立存储空间并相应地置上指针 。 标准过程 dispose是释放空间,new与 dispose不断改变着堆存储器的使用情况 。
C语言中有这些操作的若干个版本,但最基本的是 malloc和 free,它们都是标准库 （ stdlib）
的一部分实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征
（属性和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。
另外一种方法是在执行时将类结构的一个完整的描述保存在每个类的存储中，并由超类指针维护继承性（有时这也称作继承图
（ inheritance graph））。每个对象保持一个指向其定义类的指针，
作为一个附加的域和它的实例变量放在一起，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针
（在类结构中），而且对于每个对象并不将其复制到存储器中。
由于是通过类继承的搜索方法的，所以该机制还实现继承性与动态联编。其缺点在于：虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这是对于诸如
Smalltalk的高度动态语言的合理的结构，因为类结构可以在执行中改变。
折衷方法将整个类结构保存在存储中,计算出每个类的可用方法的代码指针列表 (称为方法索引表,
如,C++的 virtual function table） 。 它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量,而且也不再需要用一系列表查询遍历类的层次结构 。 现在每个对象不仅包括实例变量还包括了一个相应的方法索引表的指针而不是类结构的指针 （ 当然,这个指针的位置必须也有可预测的偏移量 ） 。
class A { int m1; void f1(){…} }
class B extends A {void f2(){…} }
class C entends B {void f2(){…} }
class D extends C{bool m2; void f1(){…}}
class A a; class B b; class C c; class D d1,d2;
m1 m1
m2
对象 c 对象 d1 对象 d2
m1
m2
m1
对象 b
m1
对象 a
A_f1
类 A
B_f2
A_f1
类 B
C_f2
A_f1
类 C
C_f2
D_f1
类 D
某个单继承 O-O语言的对象存储示意某个 O-O语言的程序例子
string day;
class Fruit
{
int price;
string name;
void init(int p,string s){price=p;
name=s;}
void print(){
Print("On ",day,",the price of
",name,
" is ",price,"\n");}
}
class Apple extends Fruit
{
string color;
void setcolor(string c){color=c;}
void print(){
Print("On ",day,",the price of
",color,
" ",name," is ",price,"\n");}
}
void foo()
{
class Apple a;
a=New (Apple);
a.init(100,"apple");
a.setcolor("red");
day="Tuesday";
a.print();
}
它的运行时存储组织临时变量局部变量控制链 (EBP)
返回地址 (EIP)
实参
……
Apple的实例
……
……
Vtable of Fruit
Vtable of Apple
……
vtable
int price(100)
string name
string color
……
Fruit.init
Fruit.print
Fruit.init
Apple.print
Apple.setcolor
……
栈区 堆区试题比例
1 正规式，有穷自动机 10%
2 文法概念及语法分析 45%
4 属性文法,语法制导翻译 (中间代码生成,符号表,静态语义分析 )及 Flex和 bison的使用
20%
5目标程序运行时的存储组织 10%
6 代码优化 10%
8 其它 5%
预处理器编译器汇编器装配连接编辑骨架程序源程序目标汇编程序可重定位机器代码绝对机器码可重定位目标文件库语言处理过程编译逻辑过程
词法分析
语法分析
语义分析
中间代码生成
中间代码优化
目标代码生成
目标代码优化出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理认知层次代码优化目标程序运行时的存储组织和代码生成语法制导翻译和中间代码生成符号表和静态语义分析自底向上分析程序自顶向下分析程序语法分析程序词法分析程序
PL/0编译程序剖析课程目标
基本理论正规式，有穷自动机上下文无关文法及其句型分析属性文法
基本知识程序设计语言有关概念 (作用域，类型）
如何设计编译器（前后端，中间语言，分遍）
基本技能
（使用工具）实现编译器
进一步研究的基础代码优化编译器后端的设计和实现正规式，有穷自动机
正规式－正规集的描述机制字母表?上的正规表达式 R的文法,终结符是 { |,*,a }.
0) R –>? 2) R –> RR 4) R –> a
1） R –> R | R 3) R –> R*
有穷自动机－正规集的识别机制程序设计语言的单词都能用正规式 来定义,
例 3.1
令?={l,d},则?上的正规式 r=l(l?d)?定义的正规集为,{l,ll,ld,ldd,…… },其中 l代表字母,d代表数字,正规式 即是 字母 (字母 |数字 )?,它表示的正规集中的每个元素的模式是,字母打头的字母数字串,,就是 Pascal和 多数程序设计语言允许的的标识符的词法规则,
例 3.2
={d,?,e,+,-},
则?上的正规式 d?(?dd )(e(+?-)dd)
表示的是无符号数的集合。其中 d为 0~9的数字。
有穷自动机确定的有穷自动机 DFA
不确定的有穷自动机 NFA
NFA的确定化
DFA的最小化文法和语言如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。
识别方式 （自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）
定义文法 G定义为四元组 (VN,VT,P,S )其中
VN:非终结符号 (或语法实体，或变量 )集；
VT:终结符号集；
P:产生式 (也称规则 )的集合；
VN,VT和 P是 非空有穷集。
S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。
VN和 VT不含公共的元素，即 VN ∩ VT = φ
用 V表示 VN ∪ VT,称为文法 G的字母表或字汇表规则,也称 重写规则,产生式 或 生成式,是形如
→?或?∷ =?的 (?,?)有序对，其中?是字母表 V
的正闭包 V+中的一个符号,?是 V*中的一个符号。
称为规则的左部,? 称作规则的右部。
文法，语言的定义由文法 G生成的语言记为 L(G),它是文法 G
的一切句子的集合,
L(G)={x|S =>* x，其中 S为文法的开始符号，且 x ∈V T*}
例,G,S→ 0S1,S→ 01
L(G)={0n1n|n≥ 1}
文法的类型通过对产生式施加不同的限制,Chomsky将文法分为四种类型：
0型文法：对任一产生式 α → β,都有
α ∈(V N∪V T)+,β ∈(V N∪V T)*
1型文法,对任一产生式 α → β,都有 |β |≥| α |，
仅仅 S→ ε 除外
2型文法,对任一产生式 α → β,都有 α ∈V N
3型文法,任一产生式 α → β 的形式都为 A→aB 或
A→a,其中 A∈V N,B∈V N,a∈V T *
上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树 ---句型推导 的 直观表示语法树 ---句型推导 的 直观表示给定文法 G=(VN,VT,P,S)，对于 G的任何句型都能构造与之关联的语法树 (推导树 )
定理：
G为上下文无关文法，
对于 α ≠ ε,有 S =>* α,当且仅当文法 G有以 α 为结果的一棵语法树 (推导树 )
句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型,是某个 推导 的构造过程。
在语言的编译实现中，把 完成句型分析 的 程序 称为 分析程序 或 识别程序 。分析算法又称 识别算法 。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
句型的分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,反复使用文法的产生式,寻找 与 输入符号串 匹配 的 推导 。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
句型分析的有关问题
1）在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？
2）在自下而上的分析方法中 如何 识别可归约的串？
在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为,可归约串,
自下而上的分析方法
OPG
LR分析器及其自动构造自上而下
LL(1)分析器及其自动构造预测分析程序 Predictive parser无回溯的自顶向下分析程序特征 ——根据下一个输入符号为当前要处理的非终结符选择产生式要求 ——文法是 LL(1)的第一个 L 从左到右扫描输入串第二个 L 生成的是最左推导
1 向前看一个输入符号（ lookahead)
预测分析程序的实现技术
1 递归下降子程序
2 表驱动分析程序表驱动 予测分析程序模型
Input
#
总控程序预测分析表
stack
一个文法 G是 LL（ 1）的，当且仅当对于 G的每一个非终结符Ａ的任何两个不同产生式Ａ? α?β,
下面的条件成立：
１,FIRST（ α ） ∩FIRST( β )=?,也就是 α?和 β 推导不出以同一个终结符 a为首的符号串；它们不应该都能推出空字?．
２,假若 β =>*?，那么，
FIRST（ α )∩FOLLOW （ A）＝?,也就是，
若 β =>*?.则 α 所能推出的串的首符号不应在
FOLLOW(A）中．
．
ＬＲ分析特定的一种 shift-reduce实现技术能力强几乎所有 CFG的语言结构都能用 LR分析不需要对文法附加条件难点几乎不可能用手工编写 LR分析器现实有 LR分析器的生成器
ＬＲ分析 器模型
L 从左到右扫描输入串 R 构造最右推导总控程序 output
Input$(#)
…
栈
ACTION GOTO
LR分析表产生式表
ＬＲ 分析特征
栈顶状态为 S,当前输入符号是 a时做什麽 ---?有穷狀态自动机
规范推导例 6.1G[S]为,
S?a A c B e
A?b
A?Ab
B?d
1)构造识别活前缀的 DFA
2)构造它的 LR(0)分析表。
3)分别给出对输入 符号串 abbcde和
Abbbce的 LR(0)分析步骤。
G[S]拓广 为,
S’? S
S?a A c B e
A?b
A?Ab
B?d
I0,S’ S
S a A c B e
I1,S’? S? I2,S? a?A c B eA b
A Ab
I3,S? a A? c B e
A? A? b
I4,A? b?
I5,S? a A c? B e
B d I7,S? a A c B? e
I8,B? d? I9,S? a A c B e?
I6,A? A b?
S a
A
b b
c
B
ed
G[L]= ab+ cde
例 6,1 G[S]的 LR(0)分析表
AC T I O N GO T O
a c e b d # S A B
0 S
2
1
1 a cc
2 S
4
3
3 S
5
S
6
4 r
2
r
2
r
2
r
2
r
2
r
2
5 S
8
7
6 r
3
r
3
r
3
r
3
r
3
r
3
7 S
9
8 r
4
r
4
r
4
r
4
r
4
r
4
9 r
1
r
1
r
1
r
1
r
1
r
1
SLR(1)技术
如果 LR(0) 项目集规范族中某个项目集 IK含 移进 /归约 归约 /归约 冲突：
IK,{,..A→ α,bβ,P? ω,,Q,,… }
若 FOLLOW(Q)? FOLLOW(P) =?
FOLLOW(P)? { b } =?
FOLLOW(Q)? { b} =?
则解决冲突的 SLR(1)技术：
action [ k,b ] = 移进对 a?FOLLOW (P) 则 action [ k,a ] =用 P? ω 归约对 c?FOLLOW (Q) 则 action [ k,c ] =用 Q 归约
能用 SLR(1)技术 解决冲突的文法称为 SLR(1)文法。
SLR(1)文法是无二义的。
SLR（ 1）的局限在 SLR 分析中,若项目集 Ik含有项目 A →?.
,那么在相应的状态下,只要当前输入符号 a?follow(A) 集,就确定采用 A→?进行归约,但在某些情况下,当状态 k呈现于栈顶时,栈内的串所构成的活前缀未必允许把?归约为 A,.因为可能没有一个右句型含有前缀?Aa.即在这种情况下,用 A →?
归约未必有效,
.所以需要扩充状态以包含更多的信息,follow 集的哪些部分才是进到该状态最恰当的归约依据,
重新定义项目,
LR（ 1）方法若 A,B I
则 B?, I
（ B 是一产生式）
把 FIRST（?）中的符号作为用 B 归约的搜索符,向前搜索符,
LR（ 1）项目 ( 配置）的一般形式
– [ A,?,a ]
意味着处在栈顶是?的相应状态，期望相应?在栈顶的状态，
然后只有当 跟在?后的 token是终结符 a时进行归约 。 a
称作该 项目 ( 配置） 的向前搜索符（ lookahead ）
向前搜索符（ lookahead ）只对圆点在最后的项目起作用
A –>,a
.意味着处在栈中是的相应状态，但 只有当下一个输入符是 a时才能进行归约,a 要么是一个终结符，要么是输入结束标记 #
有多个 向前搜索符，比如 a,b,c时，可写作 A –> u?,a/b/c
二义文法例,G‘[E]:
E → i
E → E+E
E → E*E
E → (E)
E
E + E
E * E i
i i
E
E * E
i E + E
i i
句型 i*i+i 的两个不同的最左推导：
推导 1,E? E+E? E*E+E? i*E+E? i*i+E? i*i+i
推导 2,E? E*E? i*E? i*E+E? i*i+E?i*i+i
一棵语法树表示了一个句型的种种可能的
(但未必是所有的 )不同推导过程，包括最左 (最右 )推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左 (最右 )推导呢?
二义文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义 的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是 二义 的判定任给的一个上下文无关文法是否二义，
或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，
但可以为无二义性寻找一组充分条件应用二义文法的不同途径二义文法
1 OPG分析
2 LR分析
3 LL分析重写文法,得到等价无二义文法
1 OPG分析
2 LR分析
3 LL分析二义文法途径 1 根据算符优先性和结合性重写文法
G([E]),
E –> E + E | E * E | (E) | id 重写
E? E+T |T T? T*F|F F?(E) | id
G([S]):
S? if Expr then Stmt else Stmt | if Expr then
Stmt | Other…
brevity as:
S –> iSeS | iS | a
重写
S –> M | U
M –> iMeM | a
U–> iS | iMeS
LR方法 应用二义文法 E –> E + E | E * E | (E) | id
Parsing input,id + id * id
E? E + E
id + E
id + E * E
id + id * E
id + id * id
E? E * E
E + E * E
id + E * E
id + id * E
id + id * id
I 0,E' –>?E
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 1,E' –> E?
E –> E? + E
E –> E? * E
I 2,E –> (?E)
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 5,E –> E*?E
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 6,E –> (E?)
E –> E? + E
E –> E? * E
I 7,E –> E + E?
E –> E? + E
E –> E? * E
I 3,E –>id?
I 4,E –> E+?E
E –>?E + E
E –>?E * E
E –>?(E)
E –>?id
I 8,E –> E * E?
E –> E? + E
E –> E? * E
I 9,E –> (E)?
.
二义性文法在ＬＲ分析中的应用
例表达式文法：
E’?E
E?E+E
E?E*E
E?(E)
E?i
二义性文法不是 LR文法，
但是对某些二义性文法,人为地给出优先性和结合性可能构造出更有效的 LR分析器如,规定在表达式文法中
i的 优先性最高
‘ *’ ·＞ ‘＋’
‘ *’和 ‘＋’ 都 服从左结合不用重写文法利用 precedence rules和 left(right)associativity.
解决 I1,I7,I8中 存在移进 -归 约冲突
I1,E’?E?
E?E?+E
E?E?*E
I7,E?E+E?
E?E?+E
E?E?*E
I8,E?E*E?
E?E?+E
E?E?*E
I1,移进 和 接受 无 冲突
I7,I8用 优先关系 和 结合性 解决冲突。
规定：‘ *’ 优先于‘ +’，
都服从 左 结合
I7,遇‘ *’ 移进遇‘ +’ 归 约
I8,遇‘ +’，‘ *’ 都 归 约
0 S2 S3 1
1 S4 S5 acc
2 S2 S2 6
3 r4 r4 r4 r4
4 S2 S3 7
5 S2 S3 8
6 S4 S5 S9
7 r1 S5 r1 r1
8 r2 r2 r2 r1
9 r3 r3 r3 r3
ACTION GOTO
+ * ( ) i # E
状态二义性表达式文法的 LR分析表
LL(1)方法
消除左递归和提左公因子并不一定都能将 非 LL(1)文法改造 为 LL(1)
的
S → if C t S |
if C t S e S
C →b
提左因子
S → if C t S A
A→ e S |?
First集 Follow集
S if #,e
A e,? #,e
C b t
M[A,e]={A→ e S
A→? }
属性文法属性文法 (attribute grammar)是一个三元组,A=(G,V,F),其中
G:是一个上下文无关文法
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等,属性与变量一样，可以进行计算和传递。
属性加工的过程即是语义处理的过程。
F:关于属性的属性断言或一组属性的计算规则 (称为语义规则 ),断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性,
属性有两种 继承的和综合的属性属性通常分为两类：综合属性和继承属性 。 简单地说,综合属性用于,自下而上,传递信息,而继承属性用于
,自上而下,传递信息 。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由属性计算器的参数提供 。
A?X1 X2 … Xn
A的综合属性,计算 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性,计算 T(Xj):=f(I(A),..,I(Xn))
1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,
2)终结符只有综合属性,它们由词法程序提供,
继承属性
一个结点的继承属性值是由此结点的父结点和 /或兄弟结点的某些属性来决定的。
例 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
D
L.in= real
L.in= real
L.in= real
T.type=real
real
id2
id1
id3
.
Real id1,id2,id3
每个 L结点都带有继承属性的语法树
，
，
P –> DS
D –> var V; D |?
S –> V,= e; S |?
V –> x | y | z
现在使用两个属性,name和 dl，每当一个新的变量声明时，就把它的 name
属性附给它,name属性是综合属性。
将所声明的变量都放到一个变量名字清单中（用语义函数 addlist实现），用属性 dl综合声明块中声明的所有变量。然后这个 dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中
P –> DS {S.dl,= D.dl}
D1 –> var V; D2 |? {D1.dl,= addlist(V.name,D2.dl)} | {D1.dl,= NULL}
S1 –> V,= e; S2 |? {check(V.name,S1.dl); S2.dl,= S1.dl}
V –> x | y | z {V.name,= 'x'} | {V.name,= 'y'} | {V.name,= 'z'}
var x； var y； y:=E；
P
D dl={x,y} S dl={x,y}
var V ； D dl={y} V,= E ； S
x var V ； D dl={ } y?
y?
Yacc或 bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号 $$表示产生式左端的属性，
$n表示存取产生式右端第 n个文法符号相联的属性如上例作为 Yacc的输入，可写成：
P → DS {$2.dl=$1.dl}
D1 → var V ； D{$$.dl=addlist($2.name,$4.dl)}
| {$$.dl=null}
S1 → V:=e ； S{check($1.name,$$.dl)；
$5.dl=$$.dl}
|
V → x {$$.name= ’x’}
|y {$$.name=’y’}
|z {$$.name=’z’}
语法制导的翻译
一个 翻译 是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。
各个编译阶段都定义一个翻译，
词法分析,（字符串，单词串）
语法分析,（单词串，语法树）
语义分析,（语法树，语法树）
中间代码生成 （语法树，中间代码）
目标代码生成 （中间代码，汇编语言）
语法制导的翻译 －在语法分析的同时完成翻译工作扩展ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 符号
ACTION GOTO
LR分析表产生式表
Vm
V1
-
语义
…
S0
目标程序运行时的存储组织代码生成前如何安排目标机资源运行时组织的几个问题数据表示 -如何在目标机中表示每个源语言类型的值表达式求值 -如何组织表达式的计算存储分配 -如何组织不同作用域变量的存储过程实现 -如何以例程实现过程，函数，参数传递任务：编译程序对目标程序运行时的组织（设计运行环境和分配存储） 如 通常存储区布局可为：
目标代码区静态数据区
Stack
heap
栈式分配方案过程 (嵌套和不嵌套 )的语言主要特点,
过程的 AR
过程嵌套
（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。
（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。
关键技术：解决对非局部量的引用（存取）。
设法跟踪每个外层过程的最新活动记录
AR的位置。
跟踪办法：
用静态链（如 PL/0的 SL）
用 Diplay表参数传递
(1)procedure exchangel(i,j:integer);
(2) var x:integer;
(3) begin;
(4) x:=a[i]; a[i]:=a[j]; a[j]:=x
(5) end;
带有非局部变量和形参的 PASCAL过程非局变量 a[i]和 a[j]的 值进行交换,i,j为形参（在这里是传值）
传值 的实现
1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。
2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。
3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。
传地址 的实现
（ call- by- reference )(call-by-address)(call-by-
location)
把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：
1实在参数是一个名字，或具有左值的表达式 ----
传递左值
2实在参数是无左值的表达式 ----计算值，放入一存储单元，传此存储单元地址
3目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用堆式动态存储分配
需求：
– 一个程序语言允许用户自由地申请数据空间和退还数据空间，或者不仅有过程而且有进程（ process）
的程序结构，
操作：
– 堆提供两个操作，分配操作和释放操作
情况,
– 经一段运行时间之后，这个大空间就必定被分划成许多块块，有些占用，有些无用（空闲） --碎片问题程序语言允许用户自由地申请数据空间和退还数据空间
C++语言中 new操作符施加在一个类型标识符上 （ 包括类名 ）
Pascal语言中,标准过程 new能够动态建立存储空间并相应地置上指针 。 标准过程 dispose是释放空间,new与 dispose不断改变着堆存储器的使用情况 。
C语言中有这些操作的若干个版本,但最基本的是 malloc和 free,它们都是标准库 （ stdlib）
的一部分实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征
（属性和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。
另外一种方法是在执行时将类结构的一个完整的描述保存在每个类的存储中，并由超类指针维护继承性（有时这也称作继承图
（ inheritance graph））。每个对象保持一个指向其定义类的指针，
作为一个附加的域和它的实例变量放在一起，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针
（在类结构中），而且对于每个对象并不将其复制到存储器中。
由于是通过类继承的搜索方法的，所以该机制还实现继承性与动态联编。其缺点在于：虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这是对于诸如
Smalltalk的高度动态语言的合理的结构，因为类结构可以在执行中改变。
折衷方法将整个类结构保存在存储中,计算出每个类的可用方法的代码指针列表 (称为方法索引表,
如,C++的 virtual function table） 。 它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量,而且也不再需要用一系列表查询遍历类的层次结构 。 现在每个对象不仅包括实例变量还包括了一个相应的方法索引表的指针而不是类结构的指针 （ 当然,这个指针的位置必须也有可预测的偏移量 ） 。
class A { int m1; void f1(){…} }
class B extends A {void f2(){…} }
class C entends B {void f2(){…} }
class D extends C{bool m2; void f1(){…}}
class A a; class B b; class C c; class D d1,d2;
m1 m1
m2
对象 c 对象 d1 对象 d2
m1
m2
m1
对象 b
m1
对象 a
A_f1
类 A
B_f2
A_f1
类 B
C_f2
A_f1
类 C
C_f2
D_f1
类 D
某个单继承 O-O语言的对象存储示意某个 O-O语言的程序例子
string day;
class Fruit
{
int price;
string name;
void init(int p,string s){price=p;
name=s;}
void print(){
Print("On ",day,",the price of
",name,
" is ",price,"\n");}
}
class Apple extends Fruit
{
string color;
void setcolor(string c){color=c;}
void print(){
Print("On ",day,",the price of
",color,
" ",name," is ",price,"\n");}
}
void foo()
{
class Apple a;
a=New (Apple);
a.init(100,"apple");
a.setcolor("red");
day="Tuesday";
a.print();
}
它的运行时存储组织临时变量局部变量控制链 (EBP)
返回地址 (EIP)
实参
……
Apple的实例
……
……
Vtable of Fruit
Vtable of Apple
……
vtable
int price(100)
string name
string color
……
Fruit.init
Fruit.print
Fruit.init
Apple.print
Apple.setcolor
……
栈区 堆区试题比例
1 正规式，有穷自动机 10%
2 文法概念及语法分析 45%
4 属性文法,语法制导翻译 (中间代码生成,符号表,静态语义分析 )及 Flex和 bison的使用
20%
5目标程序运行时的存储组织 10%
6 代码优化 10%
8 其它 5%
