编译原理概念期末总结复习

1、编译原理概念期末总结复习 编译原理概念期末总结复习 翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。 解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。编译过程的五个阶段： 1、词法分析任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。 2、语法分析任务：在词法分析的基础上，依据语言规则，把单词符号串分解成各类语法 单位。 3、语义分析和中间代码产生任务：对语法分析所识别出的各类语法范畴，分析其含义， 并进行初步翻译。 4、优化任务：对前段产生的中间代码进行加工变

2、幻，以期在最后阶段能产生出更为高效 的目标代码。 5、目标代码生成任务：把中间代码变幻成特定机器上的低级语言代码。 编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标代码生成器、表格管理和出错处理。 编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。词法规则：指单词符号的形成规则。也就是正规式 语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。空字：不包含任何符号的序列。闭包： 中所有的符号组成的集合。 上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。上下文无关文法的四个组成部分：一组

3、终结符号、一组非终结符号、一个开始符号和一组产生式。 终结符号也就是不可再分的基本符号。 非终结符号是用来代表语法范畴，表示一定符号串的集合。开始符号是语言中我们最感兴趣的语法范畴。产生式是定义语法范畴的书写规则。 句子：文法中从开始符号推导的终结符号串。句型：从开始符号推导的符号串。语言：文法中所有句子的集合。 程序语言的单词符号分为五种：关键字、标识符、常数、运算符和界符。二元式表示：种类，属性 正规式的运算符有三种：或，连接和闭包。优先顺序是：闭包，连接，或。 dfa怎么识别字：假设存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字是a，则称a可为dfa所识别。

4、 dfa怎么识别空字：假设dfa的初态结点同时又是终态结点，则空字可为dfa所识别。nfa怎么识别字：假设存在一条从某一初态结点到终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于a，则称a可为nfa识别。 nfa怎么识别空字：假设m的某些结点即是初态又是终态结点，或者存在一条从某个初态结点到某个终态结点的空通路，那么，空字可为m所识别。语言的语法结构是用上下文无关文法描述的。 语法分析分为两类：自上而下分析法，自下而上分析法。 自上而下分析法面临的问题：1.文法的左递归问题。2.回溯3.成功可能是暂时的，产生虚假匹配。4.难于知道输入串中出错确实切位置。5.效率低，代价高。为什么消

5、除左递归？因为含有左递归的文法将自上而下分析的过程陷入无限循环。为什么消除回溯？因为回溯统一做一大堆无效的工作。 自下而上分析法：从输入串开始，逐步进行归约，知道归约到文法的开始符号。短语：符号串推导过程中某非终结符推导的部分。 直接短语：符号串推导过程中某非终结符一步推导的部分。句柄：一个句型的最左直接短语。最左归约是最有推导的逆过程。 中间语言形式：后缀式，三元式，四元式，间接三元式。中间语言的好处：1.便于进行与机器无关的代码优化工作。2.使编译程序改变目标机更容易。3.使编译程序的结构在逻辑上更为简单，以中间语言为界面，编译前端和后端的借口更清楚。 扩大阅读：编译原理概念整理 翻译程序

6、：能够把某种语言转换成另一种语言，而后者与前者在逻辑上是等价的。 编译过程：词法、语法、语义分析与中间代码、优化、目标代码生成 词法分析：输入源程序，对构成源程序关键字、标识符、常数、运算符、界符含有左递归的文法将使自上而下的分析过程陷入无限循环。 ll(1)分析条件:当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件 ee1orme2:backpatch(e1.f,m.quad); e.t=merge(e1.t,e2.t)e.f=e2.f ee1andme2:backpatch(e1.t,m.quad) e.t=e2.t e.f=merge(e1.f,e2.f) 的字

7、符串进行扫描和分解，识别出一个个单词。 语法分析：在词法分析的基础上，依据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析与中间代码产生：对语义分析所识别出的各类语法范畴，分析其含义并进行初步翻译产生中间代码；优化：优化的任务在于对前段产生的中间代码进行加工变幻，以期在最后阶段能产生出更为高效省时间和空间)的目标代码。 目标代码生成：把中间代码或经优化处理之后变幻成特定存储器上的低级语言代码。 编译程序结构：表格管理、出错处理编译前端：由与源语言有关但与目标语言无关的那些部分组成，包括词法分析、语义分析、语义分析与中间代码产生。 后端：编译程序中与目标语言有关那些部分，优化与目标代码

8、生成。后端不依赖于源语言而仅仅依赖于中间语言。词法规则是指单词符号的形成规则。语言的语法规则规定了如何从单词符号形成更大的结构语法单位。 所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义，这些规则称为语义规则。文法是描述语言的语法结构的形式规则 上下文无关文法：是这样一种文法，它所定义的语法范畴是完全独立于这种范畴可能出现的环境。 上下文无关文法组成：一组终结符号一组非终结符号，一个开始符号以及一组产生式。 开始符号：是一个特别的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子 产生式：是定义语法范畴的一种书写规则。 二义性：如果一个文法存

9、在某个句子对应两棵不同的语法树，则称这个文法是二义的。ll(1)的含义:第一个l表示从左到右扫最左规约=规范规约：a描输入串，第二个l表示最左推导，1最右推导=规范推导：b 表示分析时每一步只需向前查看一个符号 自上而下分析的问题:文法含有左递归时，分析过程会陷入无限循环回溯浪费分析时间某一非终结符用某一候选式匹配成功时，可能是暂时的分析不成功时，难以找到出错位置 自下而上分析的问题:怎样判断栈顶的短语:每棵子树对应一个短语 符号串的可归约性，以及如何归约。直接短语:只有两层的子树对应的短语一个句型的最左直接短语称为该句型句柄:最左直接短语的句柄。 ete在形式语言中最右推导常被称为规范pro

10、ceduree推导，由规范推导所得的句型称为规范begint;e句型，如果文法无二义的，那么规范推end导最右推导的逆过程必是规范归约 最左归约) e+te|属性分为两类：综合属性，继承属性，proceduree综合属性用于“自下而上传递信息，ifsym=+then begin 继承属性用于“自上而下传递信息。advancet;e在上下文无关文法的基础上，为每个文end法符号终结符或非终结符配备假设干相关的“值称为属性 f(e)|iproceduref 语义规则：文法每个产生式都配备了一ifsym=ithenadvance组属性的计算规则。 elseifsym=(then 语法治导翻译：由源程

11、序的语法结构所begin advancee 驱动的处理办法。 ifsym=)thenadvance输入串-语法树-依赖图-语elseerror义规则计算次序 end静态检查和中间代码产生的地位：elseerror-语法分析器-静态检查器-中间代码产生器-优化器- 属性文法:关于文法的每个产生式都配备了一组属性的计算规则，在上下文无关文法的基础上，为每个符号都配备了假设干相关属性。中间语言形式：后缀式，三地址代码包括三元式，四元式、间接三元式，dag图表示 后缀式表示法逆法兰表示法：把运算量操作数写在前面，把算符写在后面后缀 四元式:(oparg1arg2result)三元式:(oparg1ar

12、g2) 翻译程序：能够把某种语言转换成另一种语言，而后者与前者在逻辑上是等价的。 编译过程：词法、语法、语义分析与中间代码、优化、目标代码生成 词法分析：输入源程序，对构成源程序二义的。 关键字、标识符、常数、运算符、界符含有左递归的文法将使自上而下的分析过程陷入无限循环。 ll(1)分析条件:当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件 三元式:(oparg1arg2) ee1orme2:backpatch(e1.f,m.quad); e.t=merge(e1.t,e2.t)e.f=e2.f ee1andme2:backpatch(e1.t,m.quad) e.

13、t=e2.t e.f=merge(e.f,e.f) 的字符串进行扫描和分解，识别出一个个单词。 语法分析：在词法分析的基础上，依据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析与中间代码产生：对语义分析所识别出的各类语法范畴，分析其含义并进行初步翻译产生中间代码；优化：优化的任务在于对前段产生的中间代码进行加工变幻，以期在最后阶段能产生出更为高效省时间和空间)的目标代码。 目标代码生成：把中间代码或经优化处理之后变幻成特定存储器上的低级语言代码。 编译程序结构：表格管理、出错处理编译前端：由与源语言有关但与目标语言无关的那些部分组成，包括词法分析、语义分析、语义分析与中间代码产生。

14、 后端：编译程序中与目标语言有关那些部分，优化与目标代码生成。后端不依赖于源语言而仅仅依赖于中间语言。词法规则是指单词符号的形成规则。语言的语法规则规定了如何从单词符号形成更大的结构语法单位。 所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义，这些规则称为语义规则。文法是描述语言的语法结构的形式规则 上下文无关文法：是这样一种文法，它所定义的语法范畴是完全独立于这种范畴可能出现的环境。 上下文无关文法组成：一组终结符号一组非终结符号，一个开始符号以及一组产生式。 开始符号：是一个特别的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子 产生式

15、：是定义语法范畴的一种书写规则。 二义性：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 12ll(1)的含义:第一个l表示从左到右扫最左规约=规范规约：a描输入串，第二个l表示最左推导，1最右推导=规范推导：b 表示分析时每一步只需向前查看一个符号 自上而下分析的问题:文法含有左递归时，分析过程会陷入无限循环回溯浪费分析时间某一非终结符用某一候选式匹配成功时，可能是暂时的分析不成功时，难以找到出错位置 自下而上分析的问题:怎样判断栈顶的短语:每棵子树对应一个短语 符号串的可归约性，以及如何归约。直接短语:只有两层的子树对应的短语一个句型的最左直接短语称为该句型句柄:最左直接短语

16、的句柄。 ete在形式语言中最右推导常被称为规范proceduree推导，由规范推导所得的句型称为规范begint;e句型，如果文法无二义的，那么规范推end导最右推导的逆过程必是规范归约 最左归约) e+te|属性分为两类：综合属性，继承属性，proceduree综合属性用于“自下而上传递信息，ifsym=+then begin 继承属性用于“自上而下传递信息。advancet;e在上下文无关文法的基础上，为每个文end法符号终结符或非终结符配备假设干相关的“值称为属性 f(e)|iproceduref 语义规则：文法每个产生式都配备了一ifsym=ithenadvance组属性的计算规则。 elseifsym=(then 语法治导翻译：由源程序的语法结构所begin advancee 驱动的处理办法。 ifsym=)thenadvance输入串-语法树-依赖图-语elseerror义规则计算次序 end静态检查和中间代码产生的地位：elseerror -语法分析器-静态