搜索
编译原理复习提纲注：♥为老师划红线的标了重点的；未整理到的会注明“翻书“，或者有相关吐槽点；欢迎使用继J2EE后，第二弹复习材料；来,让我们一起开心、快乐、愉悦的复习吧^_^♥选择，填空，简单(概念),综合(词法分析、自动机、中间代码)(四五六章)，例子，课后习题第一章1.编译原理=形式语言+编译技术2.♥程序设计语言的定义涉及：语法、语义、语用、语境。3.♥汇编程序：把汇编语言程序翻译成等价的机器语言程序（机器指令序列）4.♥编译程序：把高级语言程序翻译成等价的低级语言程序5.♥程序的翻译的两种方式：解释方式和翻译方式解释执行方式：解释程序，逐个语句地模拟执行翻译执行方式：翻译程序，把程序设计语言程序翻译成等价的目标程序6.♥计算机程序的编译过程，一般分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成♥词法分析的任务：扫描源程序的字符串，识别出的具有独立意义的最小语法单位（标识符或无正负号数等）♥语法分析是：语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。在词法分析的基础上的，语法分析不考虑语义。语义分析：是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序代码优化：是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序7.编译划分成前端和后端。♥编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析。♥编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。把编译程序分为前端和后端的优点是：可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。8.编译程序的分类：1.诊断型编译程序（找错）2.优化型编译程序（产生空间小速度快）3.交叉型编译程序（一些设备上的嵌入式应用软件一般是在另外类型的计算机上设计和开发，经过编译、运行、和测试后再经过一次编译产生出在上述设备上可以运行的目标代码这类编译程序称之为交叉型编译程序）4.可变目标型编译程序Lex是通用的词法分析生成器，它的输入是描述单词结构的正规式，输出的就是词法分析程序。9.预处理器：它是在编译程序真正开始翻译源程序之前调用的一个独立的程序，以便加快和简化翻译工作。预处理器可以删除源程序中的注释、空格符等与程序无关的部分，执行宏代换等工作。第二章1.♥符号，字母表，符号串，符号串的长度计算P18，子符号串是假定有一个非空符号串，其中的若干个相继符号组成的部分。符号串的简单运算XY，Xn2.符号串集合的概念：若集合A中的一切元素都是某字母表∑上的符号串，A就为该字母表∑上的符号串集合。符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0={ε}3.重写规则，简称规则：一个重写规则是一个有序对(U,u)。写作：U::=u。其中U是一个符号，u是有穷非空符号串。定义2.10♥非终结符（Vn）：规则左部出现的符号；♥终结符（Vt）：不是非终结符的符号，决不会出现在规则左部。♥右部仅是单个非终结符号的规则构成了特殊的一类，称为单规则。♥文法的概念：文法G[Z]是有穷非空的重写规则集合，其中Z是识别符号，G是文法名。定义2.11P23♥识别符号.P23文法的第一个重写规则的左部符号为识别符号。BNF表示法P6：描述程序设计语言的形式体系，称为元语言。“：：=”“|”元语言连接符或称元符号。♥直接推导和直接规约，广义推导广义规约，P24：设G是一文法，如果对于某些符号串x与y，能写出v=xUy与w=wuy，且U::=u是G中的规则，则说符号串v直接推导到或直接产生符号串w，记作v=w。或者说，w是v的直接推导，w直接规约到v。上述，v、w∈V+，x、y∈V*，可以有x=y=ɛ，这样对文法G的任何规则U::=u，有U=u。总可由左部U直接推导到右部u，或由右部u直接规约到左部U。定义2.13♥最左推导，最右推导P624.♥句型和句子P26定义2.16文法G[Z]，符号串x是从识别符号Z推导所得的，即Z=*xx∈V+，即称符号串x是该文法G的一个句型。如果一个句型x仅由终结符号所组成，即Z=*xx∈VT+，称该句型x为该文法G的一个句子或一个字。♥短语，简单短语定义2.17文法G[Z]，w=xuy是该文法的一个句型，有Z=*xUy,U∈VN，且U=+u，u∈V+。则称u是句型w中相应于U的短语。如果满足Z=*xUy，且U=u，则称u是句型w中相对于U的简单短语。♥句柄P26，P27一个句型的最左简单短语称为该句型的句柄。存在且唯一，特例是仅由识别符号组成的句型。5.语言的定义P31定义2.19文法G[Z]，由该文法描述的语言用L(G[Z])，则L(G[Z])={x|Z=*x，且x∈VT+}。Z=*x，因而x是文法G[Z]的一个句型，其次，x∈VT+，即x全由终结符号所组成。所以x是文法G[Z]的句子。可见由某文法描述的语言是该文法的一切句子的集合，是所有终结符号串所组成集合的一个真子集，即，L(G)VT+。6.♥递归，左递归P32，消除左递归7.文法的形式化定义Ｐ36定义定义2.21Chomsky文法G是一个四元组(VN，VT，P，Z)，其中，VN是非终结符号集，VT是由终结符号组成的字母表，P是有穷非空的重写规则集，Z是识别符号，Z∈VN。从0型到3型，限制越来越大。0型文法，短语结构文法１型文法，上下文有关文法CSG2型文法，上下文无关文法CFG：高级程序语言。3型文法，正则文法RG：词法。3型语言类⊂2型语言类⊂1型语言类⊂0型语言类♥但四种语言本身之间没有必然的包含关系P383型语言的定义：3型语言或正则语言所对应的自动机称为有穷状态自动机。P412型语言下推自动机1型语言线性界限自动机0型语言图灵机8.文法的压缩P50，♥消去规则左递归P51（看例题2.24）（这个绝逼的重要啊小伙伴们）9.♥语法分析树的构造，能根据语法树来寻找短语，直接短语，句柄。(P66习题2第3条)子树的末端结点符号串是相对于子树根的短语。定理2.710.文法的二义性问题P60，文法的二义性是不可判定的。♥某文法的同一个句子存在两个不同的语法分析书，则称该句子是有二义性的。第三章1.♥词法分析的功能P69：读入源程序字符串，识别开具有独立含义的最小语法单位，进行有利于下一阶段分析的工作，预加工处理。2.词法分析器可以有两种实现模式：完全融合模式（大多采用）和相对独立模式。完全独立方式P71：词法分析程序作为单独一遍来实现，从而把词法分析与语法分析工作截然分开。这时词法分析程序读入整个源程序字符串，把它加工成等价的属性字形式的符号串，作为下一遍中语法分析程序的输入。好处：1.符号语法可用简单文法描述，建立有效分析技术；2.独立研究词法与语法两方面的特性；3.就同一个语言，为每种不同机器编写一个词法分析程序；每个词法分析程序产生相同的符号内部表示形式供该语法分析程序使用即可。3.♥有穷状态自动机的概念，如何从正则文法构造有穷状态转换自动机P72(例3.1)♥P116习题6第1题4.♥如何从有穷状态转换自动机构造正则文法P74(自己翻书，哥累了)5.正则文法是无二义性的。6.知道确定有穷状态自动机DFA五元组（K，Σ，M，S，F），五个字母的含义。P757.非确定有穷状态自动机NFA，♥如何将NFA转化为DFAP82（看懂表3-3）♥P117习题6第6题8.♥DFA的化简，P85（例3.7）♥习题6第8题这个也是重点思密达；9.属性字由符号类和符号值组成。特定符号类，一个符号类对应一个符号值：关键字、括号，运算符。非特定符号类：标示符，无符号整数。符号类识别不同类的符号，符号值识别同类的不同符号P90(彩蛋：文档解锁密码是527072163)10.字符表，符号机内表示对照表，标示符表，无符号整数表各自的定义和作用P93词法分析程序的大致思路字符表：列出在源程序中可能出现的一切字符，词法分析程序输入源程序字符串扫描字符时查看此表。字符表中的一切字符构成文法的字母表。符号机内表示对照表：给出源程序中可能出现的一切特定符号及相应的机内表示。识别特定符号时查看此表。未查到，识别出不是合法的符号。标识符表：用来登录源程序中出现的一切标识符。特定的标识符只登录一次，从而使得在属性字符号值处无需填入标识符本身。无正负号整数表：识别出无正负号整数时，登录在无正负号整数表中，以此表的序号作为其属性字符号值。第四章语法分析-自顶向下1.带回溯的自顶向下分析方法P121（一般采用最左或者最右推导）2.无回溯的自顶向下分析方法，必须符合的条件：无左递归性，无回溯性。3.预测分析技术：♥消去文法左递归P51（上面有~）；♥构造first集合和follow集合P138构造预测分析表P139（自己翻书去！）♥输出计算过程本身P1344.LL（1）文法的定义P1405.语法分析树建立的方式可以分为自顶向下与自底向上两大类分析技术。6.♥无回溯的自顶向下的分析技术需要文法满足两个条件：无回溯和无左递归。P125第五章语法分析-自底向上1.规范分析：最右推导被称为规范推导，最左规约被称为规范规约。P1452.分析所需要解决的两个基本问题：找出要被归约的短语u；确定归约到哪个非终结符号U3.一个符号串的前缀是指该串的任一部分。一个规范句型的前缀若不含句柄之后的任何符号就称为活前缀4.基本方法：移入规约法P147四个动作之一：移进、归约、接受、报错5.♥算符优先分析技术：P150定义5.2（你看到这句话时，我已经快扛不住了；）♥构造算符优先关系表P151-154算符优先识别算法Ｐ１５５（翻书！）6.LR(k)分析技术,要知道其中定义:圆点在产生式最右端的项目称为可归约项，如E→E+T·；圆点后面是终结符的项目称为移进项，如E→E·+T；圆点后面是非终结符的项目称为待约项，如E→E+·T。项，项集，项集的闭包特征有穷状态机CFSM.P183。（翻书）CFSM表中无不适定状态的称为LR(0)文法SLR（1）文法：各个简单向前看k集合互不相交P191LALR文法：构造LR（1）项，然后合并同心项，生成LALR规约冲突P199（翻书）LR（k）文法。第六章1.语义分析的基本功能：确定类型；类型检查；识别含义，作相应的语意处理；其他一些静态语义检查。P2152.语义分析以语法分析部分的输出（语法分析树或其他等价内部中间表示）为输入，输出中间表示代码，甚至目标代码。P2153.语义是上下文相关的4.语法制导翻译技术（翻书大概P299）5.♥抽象语法树P297（翻书吧，这个没节操）6.♥逆波兰式P300（同上）7.♥四元组P306（同上上，碎一地）第七章1.代码优化的定义P348，代码优化进行的是等价变换，为优化进行努力是值得的。2.♥基本块的概念：指程序—顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第—个语句，出口就是其中的最后一个语句。对一个基本块来说，执行时只从其入口进入，从其出口退出。基本块可以用源代码、汇编、指令等表示。对基本块的优化：合并常量计算，消除公共子表达式，消减计算强度，删除无用代码。对循环的优化：循环不变表达式外提，归纳变量删除，计算强度消减。3.代码优化的三个过程：P350各自的含义控制流分析—数据流分析—变换控制流分析：识别出循环数据流分析：进行数据流信息的收集；变化：分析中间表示代码。4.代码优化是基于中间表示代码进行的5.窥孔优化定义P395：是对目标代码进行局部改进的技术，只考虑目标代码中很短的指令序列，有可能代之以更短或更快的指令序列。包括：四种