山大编译原理整理.docx

第一大题小题概念题，下面会零散分布第二大题正规集、正规式、NFA、DFA、3型文法（正规式跟正规集是一样的，更好描述，更精确）这五个点是等价的，要求可以互相转换（老师原话：最讨厌的是 给正规集，构造正规式或者文法自动机到文法的转换，自己可以看一下）考试要求的是最基本的转换：给正规式，构造它对应的DFA（三个步骤，一个步骤5分）1、先把正规式变化为NFA(规则是死的，有三种规则拆弧或增加弧或增加节点，把字拆的越来越短，最后满足一条弧上要么是一个字符或者是一个空字)（见PPT的3.7 3.8节）2、用子集构造法(-closure)确定化为DFA确定化是对NFA的状态重新组合3、化简词法分析和语法分析都用到的理论基础是形式语言与自动机词法分析用到是自动机（自动机的模型很棒，处理离散问题的一个经典的数学模型，例如电梯控制，密码破译等等）语法分析是重点（两部分）文法的概念：文法是对语言语法结构的一种形式化描述，通过文法的话非常精确。（什么是文法？）（这是老师口述，建议可以再自查校对一下）乔姆斯基定义了四种类型的文法：PPT的chapter4-1语法分析P700型文法 1型文法2型文法（上下文无关文法）3型文法（正规文法）其中，VT：终结符号，是小写符号的集合，例{a,b}VN：非终结符号，是大写符号的集合，例{A,B}S:开始符号P：产生式例：文法G:S→P|aPPbP→ba|bQa Q→abVT：{a,b} Vn:{S,P,Q} 开始符号：S 产生式：以上三行几个简单的定义：句子：文法的语言：给出一个文法，说出这个文法的语言是什么例1：例2：G:S→P|aPPb P→ba|bQa Q→ab求语言，L(G) 此处为正规式的表述：(ba+|aba(ba)+b)求语言一般用语言描述就好，参见例1例3例3：例4：语言：{ambn|m,n=1}集合元素是什么？答：以a开头以b结尾的ab串（只写是ab串是不得分的）{anbn| n=1}给一个语言，把文法描述出来（太难，掌握2型的就好，目测不考）文法的二义性如果问如何证明文法是二义的，参见课本第二章的第九题，文法的改写很重要！通过文法的改写：1 消除了二义性2 消除了左递归3 消除了回溯写文法的题会有语法分析方法两类四种：两类是推导和规约这两种方法的特点：自上而下有四个问题：①回溯问题 ②虚假匹配问题 ③不能左递归 ④错误匹配不准确自下而上只有一个问题：确定这个句子里哪个串是可规约串必须掌握两种方法：第三大题给一个文法，构造一个LL(1)分析表（实际上是构造它的预测分析方法）两种类型的题型：1 给一个文法，问：它是LL(1)文法么这个问题可以直接判定它是或者不是（有左递归就不是LL(1)）2 给一个文法，构造它的LL(1)分析表，判断是不是LL(1)文法这个问题里面可能含有左递归，那第一步需要消除左递归，第二步要消除回溯，然后要求两个集合，FIRST和FOLLOW这两个集合然后构造表，如果里面有冲突的话，就不是，如果没有冲突的话，就是LL(1)文法记住一个定理，递归下降子程序（不考）递归下降方法的特点：自然，容易写要求写编译程序的语言是支持递归的代码长第四大题规约算符优先方法（了解）LR方法：LR(0)SLR(1)二义文法的应用这三个选一个（我猜是后两个选一个）LR方法转换为：给一个文法，构造识别这个文法活前缀的下垂自动机（核心问题）直接话项目集组，看看里面有没有冲突没有冲突就是LR(0)，有冲突看看能不能依靠FOLLOW集去解决，FOLLOW集解决解决不掉就用规范LR(1)文法有二义性时，用硬规定的方式消除掉二义性遇到这种题，把冲突消除的时候，要说明用什么规则消除的，要不然扣分语义分析：（小题）知道什么是属性文法什么是语法制导翻译中间代码生成：小题：什么是中间代码？为什么引用中间代码？尤其注意有四种常见的中间代码形式，会用它表示例：给一个中缀形式，表示成后缀形式，三元式，四元式，间接三元式第五大题大题：给一个句子，要求语法制导翻译成中间代码仅写中间代码的话，不得分（一般采用四元式，看四元式生成的个数对不对）把语法分析生成过程一步步写出来，尽可能简写，或者画出来语法分析树1 把中间代码四元式单独写成一个表2 一定要把语法制导的过程写出来 尽可能简练3 遗留问题符号表管理不考出错管理 概念性知道：1 编译程序能够发现几种类型的错误语法错误（包括语法错误和词法错误）和语义错误（只能发现部分的）2 错误处理方法有几种方式：一个矫正，另一个是局部化优化：重要思想：流图概念性知道：有三种层次的优化：局部优化，循环优化和全局优化局部优化的算法要求掌握 dag 借助无环路有向图实现了局部优化循环优化：代码外提，强度削弱，改变控制变量全局优化基本的目标代码生成算法，必须掌握最后一个大题dag图实现局