郑州大学《编译原理》重点考试大纲要求.doc

计算机执行用高级语言编写的程序主要有两种途径：解释和编译 n 编译：专指由高级语言转换为低级语言n 编译和解释的区别： 是否产生目标程序 n 编译程序的五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成 此外还包括: 表格处理和出错处理 n 词法分析器（扫描器）的任务：从源程序中识别出一个个具有独立含义的最小语法单位。 扫描器的输出格式： 二元式序列 （单词种别，单词符号的属性值）n 状态转换图： 结点代表状态，用圆圈表示。 状态之间用箭弧连结，弧上的标记指明在射出弧的结点状态下可能出现的输入字符 初始状态 接受状态n 正规式和有限自动机l 正规式和正规集的转换l 给出正规式，要求写出相应的NFA、DFAl 给出正规集，要求写出相应的NFA、DFA 1、正规式和正规集l 三种运算： “”读为“或”， “ ”读为“连接” “*”读为“闭包” l 转换l 正规式等价： 两个正规式所表示的正规集相同，则 称两个正规式等价令是一个有限字母表，则上的正规式及其表示的集合递归定义如下: 1. 和都是上正规式，它们表示的正规集为 和 2. 若a是上的字符，则a是正规式，它表示的正 规集为a 3. 若r和s都是上的正规式，他们表示的正规集 记为L(r)和L(s)，则 （a） r|s是正规式，表示集合L(r)L(s)， （b） rs是正规式，表示集合L(r)L(s)， （c） r*是正规式，表示集合(L(r)*， （d）(r)是正规式，表示的集合仍然是L(r)。 （加括弧改变优先级、结合性）n 有限自动机 1、确定的有限自动机 M=(S, ，,S0, F) 其中:1. S 有穷状态集2. 输入字母表3. 映射函数(也称状态转换函数) SS (s,a)=S , S, S S, a4. s0 唯一的初始状态 s0 S5. F终止状态集 ZS2、不确定的有限自动机 M= (S, ,S0, F)其中:1. S 有限状态集（非终极符集合）；2. 输入字母表（终极符集合）；3. 转换函数S (e) P(S)， 即S * 到S的幂集(2S)的一种映射；4. S0 唯一的初始状态集合 （非空）S0S5. F终止状态集合 FSn 语法分析器的任务： 按照语言的语法构成规则，识别输入的符号串能否构成一个句子n 语法分析的理论基础 上下文无关文法和下推自动机文法：描述语言语法结构的形式规则。乔姆斯基（Chomsky）对文法的分类： 0型文法 1型文法 2型文法 3型文法文法 G = (VT , VN, S, P) 0型文法：a b，a , b (VN VT)*, | a | 1 1型文法：| a | | b |，但S e可以例外 2型文法：A b，AVN , b (VN VT)* 3型文法：A aB或A a，A, BVN , a VT 短语文法、上下文有关文法、上下文无关文法、正规文法 n 分析树：表示语言的句子结构，推导的图形表示（1）子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。（2）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。（3）短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。 l 简单短语（直接短语）：若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。 （4）句柄：句型中的最左简单短语。 n 自上而下： 消除左递归： 消除直接左递归： P Pa|b 消除后：P bP P aP|e 消除间接左递归：n 自上而下语法分析包括： 递归下降分析程序和预测分析程序 预测分析程序：预测分析表 是一矩阵MA,a，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素MA,a是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。 l 求首符集（First集） 假定a是文法G的一个符号串， a V* ，则 First(a)a| a a,a VT 注：1)若a e,那么e First(a)。 2)First(a)集合是a的所有可能推导出的开头终结符或e所组成的集合。l 求随符集（Follow集） 假定S是文法G的开始符号，对于G的任何非终结符A，Follow(A)a|S Aa,a VT 注：1)若 SA,则规定：# Follow(A)。 2)Follow(A)集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。 n LL(1)文法： 若文法G的预测分析表M中不含有多重定义项，则称G为LL (1)文法。n 自上而下语法分析过程思想： 是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到达到文法的开始符号为止的过程。n LR：自左至右扫描，最右推导的逆过程。n LR分析法寻找可归约句柄的依据 l 历史： 记录在栈内的符号串移进、归约的历 史情况 l 展望： 预测句柄之后可能出现的信息； l 现实： 读头下的符号。l 动作表ACTION ACTIONS,a表示在当前状态S下，面临读头下的符号a所应采取的动作。 n 转向表GOTO GOTOS,X：若X VT ，表示在当前状态下，读入X应转向什么状态；若X VN ，表示当前栈顶句柄归约成X后，应转向什么状态。 n 表中符号的含义： Sj ： Shift j，指将读入符号a移进栈内并转到j状态，栈顶变成（j,a）； rj ： Reduce j,按第j号产生式进行归约； acc ： accept , 分析成功； 空白格 ： 出错标志，若填入相应出错处理程序的编号，便转到相应程序处理。 n 构造LR(0)分析表的基本思想： 只根据历史信息识别呈现于栈顶的句柄。n 构造LR(0)分析表的基本策略： 构造文法G的一个有限自动机，它能识别文法中的所有活前缀。 活前缀的概念： 指规范句型的一个前缀，这种前缀不含句柄之后的任何符号活前缀有两种类型： 1）归态活前缀： 活前缀的尾部正好是句柄之 尾，这时可以进行归约。归约之后又成为另一句型的活前缀。 2）非归态活前缀：句柄尚未形成，需要继续移进若干符号之后才能形成句柄。n 中间代码四种形式l 逆波兰式 l 四元式：最常用的形式l 三元式 l 树形表示法后缀表示式(逆波兰表达式) Operand1 Operand2 Operator四元式形式: (Operato