编译原理复习

《编译原理复习》由会员分享，可在线阅读，更多相关《编译原理复习（49页珍藏版）》请在文档大全上搜索。

1、1编译原理复习编译原理复习考试题型及分值分布：选择题（2分10=20分）简答题（共15分）应用题（10分 2+15分 3=65分）2第第1 1章章 引论引论1 1、编译的各个过程及其作用对象（、编译的各个过程及其作用对象（6 6个过程，个过程，按照逻辑关系排列）按照逻辑关系排列）词法分析词法分析语法分析语法分析语义分析语义分析中间代中间代码生成码生成目标代目标代码生成码生成代码优化代码优化字符流字符流单词单词语法短语语法短语/语法树语法树中间代码中间代码优化了的优化了的中间代码中间代码有语义信有语义信息的语法息的语法树树注意：这注意：这6 6个步骤的顺序不能颠倒！个步骤的顺序不能颠倒！3第第1

2、 1章章 引论引论2 2、理解翻译程序、编译程序、汇编程序分、理解翻译程序、编译程序、汇编程序分别是什么样的程序以及彼此之间的关系别是什么样的程序以及彼此之间的关系 1 1、翻译程序：、翻译程序：2 2、编译程序：、编译程序：3 3、汇编程序：、汇编程序：高级语言程序高级语言程序（ 源 程 序 ）（ 源 程 序 ）编译程序编译程序低级语言程序低级语言程序（目标程序）（目标程序）汇编语言程序汇编语言程序（ 源 程 序 ）（ 源 程 序 ）汇编程序汇编程序机器语言程序机器语言程序（目标程序）（目标程序）一种语言程序一种语言程序（ 源 程 序 ）（ 源 程 序 ）翻译程序翻译程序另一种语言程序另一种

3、语言程序（目标程序）（目标程序）4第第3 3章章 文法和语言文法和语言1 1、几种类型的文法、几种类型的文法四种文法之间的逐级四种文法之间的逐级“包含包含”关系：关系：也就是说，任何文法都是也就是说，任何文法都是0 0型文法。不是型文法。不是0 0型文法型文法的文法，也不是其他类型的文法的文法，也不是其他类型的文法。2型文法型文法1型文法型文法3型文法型文法0型文法型文法5文法类别文法类别产生式形式产生式形式产生的语言产生的语言 说明说明0型文法型文法(短语文法短语文法)VV+ + , ,且至少含一且至少含一个非终结符，个非终结符，VV* *0型语言型语言对产生式对产生式基本无限基本无限制制1

4、型文法型文法(上下文有关文法上下文有关文法)，| |1|1或或A1型语言型语言（上下文有（上下文有关语言）关语言）将将A替换替换成成 时，必时，必须考虑须考虑A的上下文的上下文2型文法型文法(上下文无关文法上下文无关文法)AA，AVAVN N ， VV* *，产生式左部，产生式左部只有一个非终结符只有一个非终结符2型语言型语言（上下文无（上下文无关语言）关语言）无需考虑无需考虑A在上下在上下文中的出文中的出现情况现情况3型文法型文法(正规文法正规文法)AaBAaB或或AaAa，A,BVA,BVN N ，aVaVT T3型语言型语言(正规语言正规语言)产生式全产生式全部是规定部是规定的形式的形式

5、6第第3 3章章 文法和语言文法和语言2 2、规范推导和规范归约的含义、规范推导和规范归约的含义规范推导：最右推导。规范推导：最右推导。规范归约：最左归约。规范归约：最左归约。规范推导和规范归约是逆向的过程。规范推导和规范归约是逆向的过程。7第第3 3章章 文法和语言文法和语言3 3、句型、句子、短语、直接短语、句柄的含义、句型、句子、短语、直接短语、句柄的含义 句型：任何能由开始符号推出的符号串。句型：任何能由开始符号推出的符号串。句子：只含有终结符的句型。句子：只含有终结符的句型。短语：设短语：设是文法是文法GSGS中的一个句型，如果中的一个句型，如果有有S=AS=A且且A=A=，则称，则

6、称 是句型是句型相对于非相对于非终结符终结符A A的的短语。短语。直接短语：特别的如有直接短语：特别的如有A=A=，则称，则称 是句型是句型相对于规则相对于规则AA的的直接短语（简单短语）。直接短语（简单短语）。句柄：一个句型的最左直接短语称为该句型的句柄：一个句型的最左直接短语称为该句型的句柄。句柄就是句柄。句柄就是“可归约串可归约串”。+ +* *8第第3 3章章 文法和语言文法和语言3 3、句型、句子、短语、直接短语、句柄的含义、句型、句子、短语、直接短语、句柄的含义 表现在语法树中：表现在语法树中：句型就是树中任意深度的叶子串；句型就是树中任意深度的叶子串；句子就是句型中只含终结符的叶

7、子串；句子就是句型中只含终结符的叶子串；短语：每棵子树对应一个短语；短语：每棵子树对应一个短语；直接短语：只有直接短语：只有2 2层的子树所对应的短语；层的子树所对应的短语；句柄：最左的直接短语。句柄：最左的直接短语。所以，要求短语、直接短语和句柄，就可以根所以，要求短语、直接短语和句柄，就可以根据语法树来求。（考试当中若求短语、直接短语据语法树来求。（考试当中若求短语、直接短语和句柄，则和句柄，则必须画出相应的语法树必须画出相应的语法树！）！）9第第3 3章章 文法和语言文法和语言4 4、画出句型的树，找出句型相应的短语、直接、画出句型的树，找出句型相应的短语、直接短语和句柄。短语和句柄。例

8、：文法例：文法GE: EE+T|TGE: EE+T|T，TTTTF|FF|F，FF（E E）| i| i的一个句型是的一个句型是 T TF+iF+i，相应的语法树见右图：，相应的语法树见右图：EET+TTFFi对于句型对于句型T T F+i F+i来说：来说： 五棵子树对应五个五棵子树对应五个短语短语（其中（其中2 2个重个重复）复）:T :T F F，i i，T T F+i F+i 两层子树的末端结点构成直接短语，两两层子树的末端结点构成直接短语，两棵两层子树对应两个棵两层子树对应两个直接短语直接短语：T TF F，i i 位于最左边的两层子树的末端结点构成位于最左边的两层子树的末端结点构成

9、句柄句柄：T TF F 10第第3 3章章 文法和语言文法和语言5 5、证明某个句型是规范句型。、证明某个句型是规范句型。由规范推导得到的句型称为规范句型。由规范推导得到的句型称为规范句型。因此，只需要从开始符号出发，根据产生式进因此，只需要从开始符号出发，根据产生式进行规范推导（即最右推导），最后能到达该句型，行规范推导（即最右推导），最后能到达该句型，则证明完成。则证明完成。 例：例：文法文法GE: EE+T|TGE: EE+T|T，TTTTF|FF|F，FF（E E）| i| i，证明，证明T TF+iF+i是规范句型。是规范句型。EE+TE+FE+iT+iTF+i注意：一定要进行规范推

10、导（最右推导）！注意：一定要进行规范推导（最右推导）！11第第3 3章章 文法和语言文法和语言6 6、理解两种句型分析方法：、理解两种句型分析方法：自上而下分析方法：自上而下分析方法：从文法的开始符号从文法的开始符号出发，出发，反复使用文法的产生式，寻找与输入符号串反复使用文法的产生式，寻找与输入符号串匹配的匹配的推导推导。自下而上分析方法自下而上分析方法：从输入符号串开始从输入符号串开始，逐，逐步进行步进行归约归约，直至归约到文法的开始符号。，直至归约到文法的开始符号。12第第4 4章章 词法分析词法分析1 1、DFADFA、NFANFA五元组的具体含义，理解五元组的具体含义，理解DFADF

11、A和和NFANFA的区别的区别DFA M=DFA M=（K, , f, S, ZK, , f, S, Z） NFA M=(K,f,S,Z)NFA M=(K,f,S,Z)K K：有限状态集；：有限状态集； K K：有限状态集；：有限状态集； ：有穷字母表；：有穷字母表； ：有穷字母表；：有穷字母表；f f：单值单值映射函数；映射函数； f f：多值多值映射函数；映射函数；S S：唯一的初态；：唯一的初态； S S ：非空初态集；非空初态集；Z Z：终态集。终态集。 Z Z ：终态集。：终态集。所以，在所以，在DFADFA中没有初始状态集！中没有初始状态集！13第第4 4章章 词法分析词法分析2