文档介绍：2008年东南大学考研辅导班讲义
(计算机)
用中庸拒绝极端,用理智分析情景;
用务实发挥影响,用冷静掌控抉择;
用自觉端正态度,用学****积累经验;
用勇气放弃包袱,用真心追随智慧。
-----李开复
一个人可以失败,但不可以放弃,当要半途而废时,成功已在你咫尺处。
考研路上,只有怀揣比山峰更持久的***去征服山路,才能让自己的头颅比山峰更高!
编译原理
参考书目:《编译原理及编译程序构造》秦振松东南大学出版社
课程基本框架
基础知识:文法
词法分析
理论模型——正规文法与有限自动机
实现——词法分析程序(略过)
语法分析
理论模型:自上而下分析——下推自动机
自下而上分析——优先分析和LR分析
中间代码生成
语法制导翻译
运行时数据区的管理
静态存储管理、栈式存储管理、堆式存储管理(略过)
中间代码优化
局部优化、循环优化(重点)、全局优化
目标代码生成
复****范围
第二章——第九章()
复****方法
认真理解书中的基本概念、基本原理和基本算法。
重点书中的例题和****题(动手做一遍)。
看书理解过程中,一定划出相应的变化过程,注重画图理解法
理解基础上记忆背诵
预测考试题型
三道题简答题;无选择、判断、填空。
各章主要知识点及例题
第二章编译基础知识
1、Chomsky文法
主要掌握上下文无关文法和正则文法及所对应的自动机类型
(1)0型文法(短语文法或无限制文法)
★ P中产生式αàβ,其中α∈V+并至少含有一个非终结符,β∈V*
注:a) 识别0型语言的自动机称为图灵机(TM);
b) 0型文法是对产生式限制最少的文法;
c) 对0型文法产生式做某些限制,可得到其他类型文法的定义。
(2)1型文法(长度增加文法或上下文有关文法)
★ P中的产生式αàβ,除可能有Sàε外均有|β|≥|α|,若有Sàε,规定S不得出现在产生式右部;或者P中的产生式αàβ,除可能有Sàε外有αAβàαγβ,其中α、β∈V*,A∈VN,γ∈V+。
注:a)识别1型文法的自动机称为线形界限自动机(LBA)。b)对非终结符替换时务必考虑上下文,并且一般不允许替换成ε,除非是开始符号产生ε。
(3)2型文法(上下文无关文法)
★ P中产生式具有Aàβ,其中A∈VN,β∈V*。
注:a)产生式左部一定是非终结符,右部可以是VN、VT或ε;非终结符替换不必考虑上下文。b)识别2型文法的自动机称为下推自动机(PDA)。
(4)3型文法(正规文法、右线性文法或左线性文法)
★ P中产生式具有AàαB,Aàα或者AàBα,Aàα。其中A,B∈VN,β∈V*T。
注:a)3型文法中的产生式要么全是右线性产生式,要么全是左线性产生式,不能既含有右线性产生式,又含有左线性产生式。若所有的产生式都是右线性的,叫右线性文法;若所有的产生式都是左线性的,叫左线性文法。b)识别3型文法的自动机称有限状态自动机。C)3型文法扣除正规文法部分,本质上是自嵌套(SàaSb)的。即任何2型文法,如不包括自嵌套的性质,就等价于正规文法。
2、由语言构造文法(包括上下文无关文法和正则文法)
3、根据算法构造无ε产生式的上下文无关文法
4、将上下文无关文法改写成正则文法。
例题:构造一文法,产生任意长的a,b串,使得|a|<=|b|<=2|a|
解答:分析:因为a,b个数要满足|a|<=|b|<=2|a|,故要用递归保证产生任意长的字符串,又要保证递归的过程满足a,b的个数要求。
G[Z]:ZàaAb|bAa|abA|Aab|baA|Aba
AàbZ|Zb|ab|ba|ε|aZb|bZa|abZ|Zab|baZ|Zba
例题:请描述语言L={a2m+1bm+1|m>=0}∪{a2mbm+2>=0}的文法。
解答:将语言句子的描述稍做变形:a2mabbm和a2mbbbm
这样发现规律:前后的a,b的个数有倍数关系。
G[Z]:ZàaaZb|ab|bb
例题:构造一个文法G,它产生的语言L(G)={w|w∈(a|b)*,w中a,b的个数相等}
解答:SàaBS|bAS|ε
Aàa|bAA
Bàb|aBB
例题:已知文法G[S]:SàdAB AàaA|a BàBb|ε,则G[S]产生的语言是什么?能否改写成等价的正则文法?
解答:首先分析产生的语言:L(G[S])={danbm|n>=1,m>=0}
根据语言的特点,a,b的个数n,m没有相互制约关系,所以将分别构造,得到正则文法如下:G[S]:SàdA
AàaA|aB|a
BàbB|ε(BàbB|b行吗?自己考虑)
第三章词法分析
1、NFA的确