编译原理复习要点打印版

翻译程序：有这样的一个程序，它把用汇编语言或高级语言编写的程序转换成等价的机器语言程序，我们把这种执行转换功能的程序统称为翻译程序。编译：高级语言的翻译程序称为编译程序。编译程序的输入对象称为源程序，输出对象称为目标程序。编译程序支持的源程序的执行分为两个阶段：编译阶段，运行阶段。编译阶段：对整个源程序进行分析，翻译成等价的目标程序，翻译的同时做语法检查和语义检查，凡是有错误的源程序均指出其错误。运行阶段在运行子程序的支持下执行目标程序。运行子程序是为了支持目标程序的运行而开发的程序。编译程序的功能结构：词法分析：扫描程序的ASCII码序列，识别出一个个具有独立意义的最小语法单位，并把每个单词的ASCII码序列替换为所谓的token形式。语法分析：根据程序设计语言的语法规则，把词法分析的结果分解陈各种语法单位，同时检查程序中的语法错误。语义分析：对语法分析所识别出的各类语法范畴，分析其含义，并进行静态语义检查。中间代码生成：上述过程后，有些编译程序将程序变成一种内部表示形式，这种表示形式叫做中间代码中间代码优化：对前阶段产生的中间代码在不改变源程序的前提下进行加工变化，使生成的代码更高效，缩短运行时间或节省存储空间。目标代码生成：把中间代码变换成特定机器上的机器指令代码或汇编指令代码。表格管理：编译程序在对源程序的分析过程中，需要创建和管理一系列的表格，以登记源程序的各类信息和编译各阶段的进展情况。错误处理：一个编译程序不仅能对书写正确的程序进行翻译，而且能对出现在源程序中的错误进行处理。文法：是用有限的规则表示无穷字符串集的一种方法O型文法:也称为短语文法，其产生式具有形式:→，其中,(VTVN)*，并且至少含一个非终极符;1型文法:也称为上下文有关文法。它是0型文法的特例。其产生式具有形式:（1）A→,AVN,为非空串.或（2）||||(S是开始符,S→除外，且S不出现在任何产生式的右部)2型文法:也称为上下文无关文法。它是1型文法的特例。其产生式具有形式:A→,AVN,为非空串.即要求产生式左部是一个非终极符.3型文法:也称为正则文法。它是2型文法的特例。其产生式的右部至多有两个符号，而且具有下面形式之一:A→a，A→aB,其中A,BVN，aVT文法描述能力O型文法1型文法2型文法3型文法文法对应自动机O型文法(短语文法):图灵机1型文法（上下文有关文法）:线性有界自动机2型文法（上下文无关文法）:下推自动机3型文法（正则文法）:有限自动机句型:如果有S*,S是文法的开始符,∈(VTVN)*，则称是G的句型句子:如果有S+,S是文法的开始符,∈VT*，则称是G的句子短语：一个句型形如,如果存在一个句型A,而且A+,则称为句型的短语;一个句型形如,如果存在一个句型A,而且A,则称为句型的简单短语;句柄:一个句型的简单短语可能有多个，称最左简单短语为句柄规范推导：最右推导每个句子一定有最右(规范)推导，每个句型不一定有最右(规范)推导二义性文法：如果文法的一个句子有两棵或两棵以上不同的语法分析树，则称该文法为二义性文法。消除文法二义性的常用方法：1、规定符号的优先级2、规定符号的结合性文法变换：有些语法分析方法要求被分析的文法满足一定的约束条件，当被分析的文法不满足这些条件时，常常要进行文法变换。文法变换必须保证变换前后的两个文法G1和G2是等价的，即L(G1)=L(G2)消除公共前缀A1|…|n|1|…|m提取公因子AA’|1|…|m，A’1|…|n消除左递归AA1|…|An|1|…|m消除:A1A’|…|mA’，A’1A’|…|nA’|自动机：是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。NFA到DFA的转化思想：将NFA的状态集当作DFA的状态，同时确保转化后的DFA与原NFA等价DFA化简思想：等价状态：对于DFA中的两个状态s1和s2，如果分别将s1和s2当作开始状态，它们接受的字符串集合相同，则称s1和s2是等价状态;DFA化简的两种方式:合并等价状态;(状态合并法)分离不等价状态;（状态分离法）DFA和NFA的不同：DFANFA初始状态一个初始状态初始状态集合边不允许允许f(S,a)S’or⊥{S1,…,Sn}or⊥实现容易有不确定性自顶向下语法分析主要思想：是从文法的开始符号出发，试图为输入串建立一个最左推到，或者为输入串构造一个语法树。自顶向下语法分析条件：对任意非终极符A，A的任意两条产生式predict(A→k)predict(A→j)=，kj不满足LL(1)文法条件的情形：文法的产生式存在左递归或公共前缀。递归下降语法的做法：对文法中每个非终极符U都编写一个子程序，以完成该非终极符所对应的语法成分的分析和识别任务。某个非终极符的语法分析子程序的功能：用该非终极符的规则的右部符号串去匹配输入串。递归下降法优点：程序结构和层次清晰明了，易于手工实现，就语义加工来说，这种方法是十分灵活的。缺点：对文法的限制太严格，频繁调用子程序，分析效率低LL(1的主要思想：LL的含义是从左到右扫描输入串，采用最左推导分析句子。数字1表示分析句子时需向前看一个输入符号。LL(1)方法和递归下降法属于同一级别的自顶向下分析法(分析条件相同)。LL(1)文法的特性：无二义性，无左递归，对于一个非终极符来讲,最多只有一个空产生式递归下降法与LL(1)的相同点：同属于自顶向下分析法，分析条件相同。不同点：递归下降法对每个非终极符产生子程序，而LL(1)方法则产生LL分析表；递归下降法能判断每个产生式的结束，而LL(1)方法则不能；递归下降法分析法不用符号栈，而LL(1)方法则用符号栈。自底向上分析主要思想：从输入串出发;尽可能地找到可归约子串并将其归约成一个非终极符;直到归约成文法的开始符或发现语法错误;规范推导：最右推导规范句型：最右推导导出的句型规范前缀:若有规范句型αη，且η是终极符串或空串，则称α为规范前缀。规范活前缀:若规范前缀α不含句柄或含一个句柄并且句柄在α的最右端，则称规范前缀α为规范活前缀。规约规范活前缀:活前缀α是含句柄的活前缀，并且句柄在α的最右端，则称活前缀α为规约规范活前缀。LR方法主要思想：从左至右读入输入串;每次找到句柄(归约规范活前缀)来进行归约;归约直到得到开始符或报告语法错误;LR(0)项目:带圆点的产生式,圆点只能出现在产生式的右部符号串的任意位置;LR(0)分析的局限：LR(0)文法仅凭符号栈里的内容来确定可归约活前缀,非常容易产生冲突;LR(0)文法易于产生冲突的原因在于在确定分析动作时没有考虑输入串信息。LR(1)分析基本思想:对于非终极符的每个不同出现求其后继终极符(follow),称为展望符;一个非终极符的一个出现的所有后继终极符构成的集合称为展望符集;展望符集的作用:对于移入型项目,不起作用,但是需要保存;对于归约型项目,表示只有当下一个输入符是其中一个展望符时,才可以进行归约动作LR(1)分析存在的问题：为消除冲突，引入太多的状态，构造分析表的工作量及所占存储空间较大;LALR(1)分析主要思想：合并文法G的LR(1)自动机中的同心状态，得到的自动机称为LALR(1)自动机；若这个得到的LALR(1)自动机没有冲突，则称文法G是LALR(1)文法。分析能力:LR(1)LALR(1)SLR(1)LR(0)状态数:LR(1)LALR(1)=SLR(1)=LR(0)语法：是描述一个合法定义的程序结构的规则语义：说明一个合法定义的程序的含义词法分析和语法分析是对源程序形式上的识别和处理，而语义分析是对源程序的语义做相应的处理工作。静态语义：编译时可以检查的语义动态语义：目标程序运行时才能检查的语义静态语义检查内容：各种条件表达式的类型是不是Boolean型，运算符的分量的类型是否相容，赋值语句的左右部的类型是否相容，形参和实参的类型是否相容，下表表达式的类型是否为所允许的类型等。符号表：可看作是从标识符名字到它的属性的映射;用于存储程序中声明的标识符及其属性;为什么在语义分析时需要符号表?从标识符的Token定义，我们仅仅知道了标识符的名字，对于其它属性，例如类型，种类等没有记录，对于标识符的更多信息需要进行语义分析，从而检查语义错误;为表示标识符的属性，我们需要建立：标识符的内部表示，类型的内部表示，值的内部表示。为什么需要类型的内部表示?类型是标识符的重要属性;类型检查是语义分析的重要部分;类型的结构对类型检查很重要;标识符声明：查找符号表检查标识符是否已经被声明过;如果是，则重复声明错；如果不是，则建立标识符的内部表示，将其放入符号表;标识符使用：查找符号表检查标识符是否有声明；如果是，则取出标识符的属性进行语义分析；如果不是，则未声明错；声明的语义分析:收集被声明的标识符的属性;建立被声明标识符的内部表示;检查重复声明错误;将被声明标识符的内部表示插入符号表;中间代码生成方法：语法制导的翻译方法：属性文法和动作文法,基于Token序列,基于抽象语法树运行时间环境:是指目标计算机的寄存器和内存结构，该结构用于管理内存和维护目标程序执行时需要的信息.过程活动记录:每当过程/函数被调用时，为其分配的局部空间的一种统一结构。存放在栈区的一段连续的存储单元中，由目标程序进行管理。是过程一次活动的一个现场记录。过程调用的时候进行填写，过程返回的时候释放。活动记录通用结构：临时变量局部变量形参返回返回地址控制信息动态链：如果每个AR是等长的则用sp减去这个长度就可以了，但实际上每个AR的长度不一定相同，所以在每个AR中要保存其前一个AR的始地址，于是栈上的AR被连起来了，这样连起来的AR结构称之为动态链。目标代码生成器主要任务:给变量分配实际地址,寄存器分配,生成管理AR的指令和其他指令。寄存器分配应遵循的原则：寄存器优先原则：即变量的值尽可能的存放在寄存器中。寄存器活跃原则：即变量的值至少有下一次的引用时才分配寄存器。寄存器多载原则：即一个寄存器中可能存放多个变量的值。典型的例子是通过赋值操作的结果。源变量和被赋值的变量共用一个寄存器表达式四元式生成算法(1)初始化:S1和S2为空;(2)读token:tk=ReadOne();(3)Switchtkof(i)#:if(S1为空)exit;elsewhile(S1不为空){op=pop(S1);(a,b)=pop(2);t=NewTemp(dir);GenIR(op,b,a,t);push(S2,t);}(ii)操作数:push(tk,S2);goto(2);(iii)操作符:if(S1为空||tk优先级大于Top(S1)){push(tk,S1);goto(2);}else{while(tk小于等于Top(S1)&&S1不为空)){op=pop(S1);(a,b)=pop(2);t=NewTemp(dir);GenIR(op,b,a,t);push(S2,t);}push(tk,S1);goto(2);}带括号表达式四元式生成算法:(1)初始化:S1和S2为空;(2)读token:tk=ReadOne();(3)Switchtkof(i)#:if(S1为空)exit;elsewhile(S1不为空){op=pop(S1);(a,b)=pop(2);t=NewTemp(dir);GenIR(op,b,a,t);push(S2,t);}(ii)操作数:push(tk,S2);goto(2);‘(’：push(tk,s1);goto(2);(iii)操作符:if(S1为空||tk优先级大于Top(S1)){push(tk,S1);goto(2)}else{while(tk小于等于Top(S1)&&Top(S1)≠‘(’&&S1不为空))){op=pop(S1);(a,b)=pop(2);t=NewTemp(dir);GenIR(o