资源描述：
《《编译原理》复习要点.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、考试安排：7月13日（20周周三），15：00-17:00,20208填空10X1分、选择10X2分、简答4X5分、大题5X10分考试大题：循环优化LL(1).定义之类的算符优先算法…自下而上分析法（20分，选择、填空、大题）第一章引论一．编译程序(compiler):把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序二．编译程序的工作的五个阶段:词法分析、语法分析、中间代码产生、优化、目标代码产生1.词法分析Pascal语言任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词
2、符号。依循的原则：构词规则描述工具：有限自动机FORI:=1TO100DO保留字标识符等符整常数保留字整常数保留字2.语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则述工具：上下文无关文法3.语义分析与中间代码产生任务:对各类不同语法范畴按语言的语义进行初步翻译。（变量是否定义、类型是否正确等）依循的原则：语义规则中间代码:三元式，四元式，逆波兰记号，树形结构等。是一种独立于具体硬件的记号系统。例：将Z:=X+0.618*Y翻译成四元式为(1)*0.618YT1(2)+XT
3、1T2(3):=T2_Z4.优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则FORK:=1TO100DOBEGINM:=I+10*K;N:=J+10*K;END1.目标代码产生任务:把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:a)绝对指令代码:可直接运行b)可重新定位指令代码:需要连接装配c)汇编指令代码:需要进行汇编三.编译程序结构u编译程序总框(简答题5分)第二章高级语言及其语法描述2.1.1语法词法规则：单词符号
4、的形成规则。a)单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。b)描述工具：正规式和有限自动机语法规则：语法单位的形成规则。a)语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;c)描述工具：上下文无关文法2.1.2语义语义：一组规则，用它可以定义一个程序的意义。描述方法：a)自然语言描述：隐藏错误、二义性和不完整性b)形式描述：F无二义性F完整性多数语言中，算符的优先顺序如下：u乘幂（**或↑）优先级由高自低u一元负（-）u乘、除u加、减不同的语言对算符优先级的规定有差异，甚
5、至差异很大！u关系符（<,=,>,<=,>=,<>）u非（¬，not）u与(Λ，&，and)u或(˅,
6、,or,)u隐含(或imp)u等值（或epui，或~）2.3程序语言的语法描述1.几个概念:a)考虑一个有穷字母表∑字符集b)其中每一个元素称为一个字符c)∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列d)不包含任何字符的序列称为空字，记为εe)用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}f)∑*的子集U和V的连接（积）定义为UV＝{
7、ab
8、aÎU&bÎV}例如:设：U＝{a,aa},V＝{b,bb}那么：UV={ab,abb,aab,aabb}g)V自身的n次积记为Vn=VV…Vh)规定V0={e}，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记V＋＝VV*，称V+是V的正规闭包。例如:设：U＝{a,aa}那么：U*={e,a,aa,aaa,aaaa,…}U＋={a,aa,aaa,aaaa,…}i)0型(短语文法，图灵机)：产生式形如：a®b其中：aÎ(VTÈVN)*且至少含有一个非终结符；bÎ(VTÈVN)*任何0型语言都是递归可枚举的。j)1型(
9、上下文有关文法，线性界限自动机)：产生式形如：a®b其中：
10、a
11、£
12、b
13、，仅S®e例外。意味着对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成空串e。k)2型(上下文无关文法，非确定下推自动机)：产生式形如：A®b其中：AÎVN；bÎ(VTÈVN)*。非终结符的替换可以不必考虑上下文。l)3型(正规文法，有限自动机)：右线性文法产生式形如：A®aB或A®a其中：aÎVT*；A，BÎVN左线性文法产生式形如：A®Ba或A®a其中：aÎVT*；A，BÎVN正规文法的能力要比上下文无关文法弱得多。四种类型描述能力比较a)上下
14、文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTÇVN=ÆS：文法的开始符号，SÎVNP：产生式集合(有限)，每个产生式形式为P®a，PÎVN，aÎ(VTÈVN)*开始符
