编译原理 复习编原理 复习.docVIP

编译原理 词法分析 主要内容 词法分析器的任务 单词的种类与机内表示方法 单词的描述: 正规式与正规集：概念，要求会用正规式描述一些不太复杂的单词 有限自动机FA：(确定、非确定)FA概念， FA的状态转换矩阵和状态转换图表示，有限自动机识别的语言L(M) (正规式——NFA——DFA)的转换 词法分析器的设计： 设计方法： 把词法分析当作单独的一遍 (生成单词文件) 语法分析器的子程序 设计技术：有限自动机技术 根据单词定义的种类写出每种单词的正规表达式 由正规表达式导出每种单词的DFA(先导出NFA，再转化为DFA，再DFA最小化) 根据DFA(状态转移图)即可编写识别一种单词的程序段 将识别各种单词的程序段适当组织就形成了该程序设计语言的词法分析程序 本章重点 词法分析器的设计 单词的描述 正规式、NFA、DFA之间的等价性及其相互转换方法 练习题：实验1 (1)包含奇数个1或奇数个0的二进制数串 分析：包含奇数个1的数串由1和重复0-多次的(11)组成，记做1(11)*，若考虑含0的情况，0可有任意多个多个，可插入任意位置，结果包含奇数个1的0,1数字串为0* 1(0* 1 0* 1)* 0* 。 同理包含奇数个0的0,1数字串为1* 0(1*01*0)*1* 。 综合起来可知，题目答案为： 0* 1(0* 1 0* 1)* 0* | 1* 0(1*01*0)*1* (2)书本 2.5 (3)2.7 验证：找几个正规式表示的正规集中的句子，如abaab，看看该句子能否被DFA所识别。 (4)2.9 高级语言及其语法描述 主要内容： 程序语言的语法描述： 基本概念:字母表、符号串、符号串(..集合)的积(连接)、闭包、正则闭包 文法的形式定义及相关概念： 形式定义： G=（Vn，Vt，S,ζ）各部分含义 终结符、非终结符、开始符号、产生式 相关概念： 推导、直接推导、最左(右)推导、规约、句型、句子、语言、规范规约、短语、句柄、语法树 形式语言鸟瞰： 文法分类 重点：文法及其相关概念 文法分类 例：练习题： 由文法开始符号推导出的符号串称为文法的( ) 文法G为:S-a|SA A-b是( )文法 书本3.2 、3.5（1）、3.6 自上而下的语法分析 主要内容 语法分析的任务、分析方法分类 自上而下的分析方法 基本思想 LL(1)文法： LL(1)文法概念：判断一个文法是否LL(1)文法 将一个文法改造为LL(1)(消除回溯) 消公共左因子 消直接(间接)左递归 (消除公共左因子和左递归后的文法不一定即为LL(1)文法，有的文法天生非LL(1)文法) 自上而下的分析方法 一个文法是LL(1)文法，则可用递归下降分析法或预测分析法进行语法分析。 递归下降分析法： 根据LL(1)文法编写递归下降分析程序 预测分析法 预测分析器的3个组成部分(控制程序、栈、分析表) 分析表的构建方法： FIRST集合、FOLLOW集合、表的构建算法 预测分析器的分析过程的实例: 练习题 判断某文法是否LL(1)的 方法： (1)直接观察:含直接左递归的文法非LL(1)文法、含公共左因子的文法非LL(1)文法 (2)对每个产生式A的每个候选式(，计算FIRST(()，如这些FISRT集合的两两间交集非空，文法非LL(1)文法 (3)如(( FISRT(A)，计算FOLLOW(A)，如A的每个候选式( 的FIRST集合和FOLLOW(A)两两间交集非空，文法非LL(1)文法。 否则，文法为LL(1)文法 练习：实验2、书本练习题 3.9,3.10 自下而上分析 主要内容 自下而上分析的基本思想和概念 基本思想：“移入－归约”，直到输入结束，栈中只有文法的开始符号为止，此时分析成功 几个概念： 归约、短语、直接短语、句柄、规范归约 LR分析法 LR分析器的3个组成部分(控制程序、栈、分析表) LR(0)、SLR(1)分析表的构建方法： 前缀、活前缀、LR(0)项目、项目分类、 识别活前缀的NFA、项目集、识别活前缀的DFA LR(0)项目集规范族、GO(I,X)转换函数、识别活前缀的DFA的构造、分析表的构造算法 LR分析器的分析过程的实例: 练习题：——一般要求 书本练习题 3.19 语义分析和中间代码产生 主要内容 属性文法（语法制导定义） 语法制导翻译的一种描述形式。为文法符号配属性，为产生式配上语义规则(计算属性)。 基本概念：属性文法、综合属性、继承属性 语义处理：属性加工的过程 语义规则：属性计算、静态语义检查、符号表操作、代码生成 语法制导翻译：为每一个产生式配一个翻译子程序，在语法分析的同时执行这些子程序，进行语义处理(翻