复习汇总
一、第一章概述
1.文法与自动机的等价
1)0型文法—图灵机
2)1型文法—线性有界非确定图灵机
3)2型文法—非确定下推自动机
4)3型文法—有限状态自动机
2.编译技术的应用
1)语法制导的结构化编辑器
2)程序格式化工具
3)软件测试工具
4)程序理解工具
5)高级语言的翻译工具
6)等等
3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解）
1)面向机器的语言：机器指令，汇编语言
2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述
语言（正规式,产生式）等等。
4.各语言的分类（结合第二章第9小点理解）
1)过程式语言，面向对象语言：通用程序设计语言。
2)函数语言：面向特点领域的，递归特性。例如LISP语言
3)说明性，非算法式语言：LEX/YACC,SQL。
4)脚本式语言：Shell语言
5.语言之间的转换（李静PPT41）
1)高级语言之间的转换一般称为预处理或转换。
2)高级语言翻译成汇编语言或机器语言称之为编译。
3)把汇编语言翻译成机器语言称之为汇编。
4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之
为交叉汇编。
5)把机器语言翻译成汇编语言称之为反汇编。
6)把汇编语言翻译成高级语言称之为反编译。
6.编译器和解释器
1)编译器
●源程序的翻译和翻译后的程序的运行是两个不同的阶段。
◆编译阶段：用户输入源程序，经过编译器的处理，生成目标
程序。
◆目标程序的运行阶段：根据要求输入数据，得出结果。
2)解释器（凡是可以采用编译器的地方均可以采用解释器）
●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执
行它。这种方式称为解释。
7.解释器的优点（对比与编译器）
1)具有较好的动态特性。
2)具有较好的移植特性。
8.解释器的缺点（对比于编译器）
1)相比于编译器需花费大量的时间。
2)占用更多的内存空间。
9.编译器的工作阶段（结合第二章6小点红色部分理解）
1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器->
代码优化器->目标代码生成器->目标代码
2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。10.编译器各阶段的工作过程（结合第二章6小点红色部分理解）
1)源程序通过词法分析器翻译成记号流，记号流通过语法分析产生语
法树，然后根据语法树来进行适当的语义处理，语义分析产生符号
表和中间代码。
2)符号表的格式：标识符，类型，分配的地址。
3)中间代码的格式：操作符，左操作数，右操作数，结果。
4)中间代码的优化：传值的代码可以省略。
5)目标代码生成：生成汇编指令，格式为：操作数源码目标。
●二元运算：OP source target target := source OP target
●一元运算：MOVE source target tatget = source。
11.各阶段工作归纳
1)词法分析：根据词法规则识别出源程序的各个记号（token），每个
记号代表一类单词（lexeme），记号的分类如下：（第二章第4小点）
●关键字：如var、begin、end等，不做他用，称为保留字。
●标识符：如x、y、z、sort等，在源程序中被用作变量名，过程
名，类型名和标号等所有对象的名称。(用记号代替)
●字面量：如60、Xidian、University等，一般用于表示常数或字
符串常量。（保留原样）
●特殊符号：=、*、+、-、;等运算符，分隔符（保留原样）。
●例：var x,y,z:real ; x:= y+z*60; var
id1,id2,id3:real;id1:=id2+id3*60;
2)语法分析：得到语言结构并以树来表示。
3)语义分析：考察结构正确的句子是否语义合法。
4)中间代码生成。
5)中间代码优化。
6)目标代码生成。
7)符号表管理：合理组织符号，便于各阶段查找，填写等。
8)出错处理：错误的种类—词法错，语法错，静态语义错，动态语义
错。
12.编译器的分析/综合模式。（PPT53）
1)前端（分析）：语言结构的分析。（语法和语义分析）
2)后端（综合）：语言意义的分析与处理。（代码的生成、优化）
3)中间代码：前段与后端的分解。
二、第二章词法分析
1.词法分析：词法分析是编译过程中将字符流转换成为符号流的一个工作
阶段，是编译的第一步操作，其后续工作是语法分析（配合第一章第11
小点理解）。
1)词法分析输入源代码。
2)词法分析输出记号流。
3)词法分析需要识别此发错无，即非法的符号、单词。但不识别语法
错误。
2.词法分析器的作用
1)源程序由单词组成，单词是最小的语义单位。
2)词法分析器的功能：
●扫描源程序字符流。
●按照源程序的语法规则识别出各类单词符号。
●产生用于语法分析的记号序列。
●填写符号表。
3)辅助功能
●跳过源程序的注释和空白。
●把错误信息和源程序联系起来（错误定位）。
●宏预处理。
3.模式（规则）（patten）：将产生和识别单词的规则称为模式（规则）。
4.记号（token）：按照某个模式识别出来的元素称为记号。（第一章和本章
第11小点一同理解）
1)记号= 记号的类别+记号的属性。（用于识别）
2)记号的类别：记号的类别可以用整形编码来表示。
3)记号的属性：根据记号的类别不同，记号的属性可以用不同的表示
方法，如relation(81)的属性值为一个有限的可枚举的集合，可以用
每个属性值在集合中的位置来表示它。（课本P16）。
5.单词（lexeme）：被识别出元素自身的价值。（结合本章第9点理解）
6.词法分析器的作用和工作方式:
1)特征：编译器中唯一与源程序打交道的部分。
2)任务：（与第二章第2点一同理解）
●滤掉源程序中的无用的部分，如注释，空格，回车等。
●处理与具体平台有关的输入。
●识别记号，并交给语法分析器，根据模式识别记号。
●调用符号表管理器或出错管理器，进行相关管理。
3)工作方式
●单独一遍扫描。
●作为语法分析器的子程序。
●并行方式。
4)输入输出结果的分析（结合第一章9、10小点理解）
●源程序->词法分析期->记号流
●源程序->词法分析器->记号流->语法分析器->语法树。
7.输入缓冲区
1)设置缓冲区的必要性：
●超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描
若干个字符。
●方便实现读字符和退字符操作，提高词法分析器的效率。
8.字符串：从词法分析的角度看程序语言设计，他是由几号组成的集合（第
二章第4小点）
1)定义：语言L是有限字母表∑上有限长度字符串的集合。字母表是
组成字符串的所有字符的集合。即字符串中的所有字符取自字母表。
2)两个有限：（有序集合）:因为计算机所能表示的字符个数和字符串
长度是有限的。
●字母表是有限的，即字母表中的元素是有限多个。
●字符串长度是有限的，即字符串中字符的个数是有限多个的。
3)字符串和集合的基本概念：（课本P19）
9.语言概述：（第一章第3、4小点理解）
1)语言——形式化的内容提取：是字和组合字的规则
●语言：满足一定条件的句子集合。
●句子：满足一定规则的单词序列
●单词：满足已定规则的字符。（结合本章第5点理解）
2)程序设计语言——形式化的内容提取：组成程序的所有语句的集合。
●程序：满足语法规则的语句序列。
●语句：满足语法规则的单词序列。
●单词：满足词法规则的字符串。（结合本章第5点理解）
3)描述形式——文法
●语法——语句
◆语句的组成规则
◆描述方法：BNF范式，语法图
●词法——单词（结合本章第5点理解）
◆单词的组成规则。
◆描述方法：BNF范式，正规式。（结合下一小点理解）
10.正规式和正规集
1)正规式：令∑是一个有限字母表，则∑上的正规式及其表示的集合递
归定义为：
●ε是正规式，他表示集合L（ε）=｛ε｝
●若a是∑上的字符，则a是正规式，他表示集合L（a）=｛a｝
●若正规式r和s分别表示集合L（r）和L（s），则
◆r|s是正规式，表示集合L（r）并L（s）。
◆rs是正规式，表示集合L（r）L（s）。
◆r*是正规式，表示集合L（r）*。
◆（r）是正规式，表示的集合仍是L（r）。（加括号改变优先
级，结合性）
2)正规集：可用于正规式描述的语言称为正规语言或正规集。
●正规式计算的优先级（具有左结合的性质）
◆从高到低排列：闭包运算，连接运算，或运算。
●正规式中不必要的括号可以被省略。
3)正规式和正规集之间的关系是多对一的关系。
4)正规式的等价：若正规式P和Q表示了同一个正规集，则称P和Q
是等价的，即为P=Q
5)正规式公理（课本P21）
11.记号的说明（用正规式来描述）（本章第4小点）：正规式可以严格规定
记号的模式，用正规式说明记号的公式为：
1)记号=正规式（记号是正规式）例如：id = a(a|b)可以读作“id定义
为a(a|b)”（简称为正规式）
2)通常在不引起混淆的情况下，也把说明记号的公式简称为正规式，
或者规则。
12.记号的识别——有限自动机
1)模式的描述——正规式
2)记号的识别——有限自动机（确定，不确定）
●不确定的有限自动机
◆定义：NFA是一个五元组：M =（S，∑，move，s0，F）
A.S是有限个状态的集合。
B.∑是有限个输入字符（包括ε）的集合。
C.Move是一个状态转移函数，move（si ，ch）= sj表示，
当前状态si下若遇到输入字符ch，则转移到状态sj。
D.s0是唯一的初态（称为开始状态）
E.F是终态集，他是S的子集，包含了所有的终态。
◆NFA的表示方式
A.状态转换图：用一个有向图直观表示NFA。终态用一个
双圈来表示。
B.状态转换矩阵：用一个二维数组来直观表示NFA。
◆NFA识别记号（课本P24-25 ，PPT29）
A.NFA识别记号存在的问题：
1.只有尝试了全部可能的路径，才能确定一个输入序
列不被接受，而这些路径的条数随着路径长度的增
长而成指数增长。
2.识别过程中存在大量回溯，时间复杂度和输入序列
呈指数级增长。
●确定的有限自动状态机（DFA）
◆定义：DFA是NFA的一个特例
A.没有状态具有ε状态转移，即状态转换图中没有标记ε
的边。
B.对每一个状态s和每一个字符a，最多有一个下一个状
态。
◆DFA的特征：消除了NFA的不确定性。
A.定义move（si，a）函数是一对一的。
B.转换图：从一个节点出发的边上标记均不相同。（没有重
复字符的状态转移）
C.转换矩阵M[si，a]是一个状态。（NFA可以为状态集）
D.字母表不包括ε。
●有限自动机的等价：若有限自动机M和M’识别同意正规集，
则成M和M’是等价的，即为M=M’。
13.简化正规式描述
1)正闭包：若r是表示L（r）的正规式，则r的正闭包是表示（L（r））
的正闭包的正规式；
●r+ = rr* = r*r，，r* = r+|ε。+与*具有相同的运算结合性和优先级
2)可缺省：r？= r|ε
3)字符组：
●枚举：【abc】= a|b|c
●分段
4)非字符组：
●若[r]是一个字符组形式的正规式，则[^r]是表示∑-L（r）的正规
式。
5)串：若r是字符链运算的正规式，则串“r”和r等价。
14.从正规式到词法分析器
1)构造词法分析器的一般方法和步骤：
●用正规式对模式进行描述。
●为每一个正规式构造一个NFA，他识别正规式所表示的正规集。
●将构造出的NFA转化为等价的DFA，这一过程也成为确定化。
●优化DFA，使其状态数最少，这一过程称为最小化。
●从优化的DFA构造词法分析器。
2)从正规式到NFA（thompson算法）。
●对于字母表∑上的r，将其分解为最基本的正规式。
◆对于ε，NFA为s0为初态，f为终态，该NFA接收｛ε｝。
◆对于∑上的任意一个字符a，NFA为s0为初态，f为终态，
NFA接受｛a｝。
◆若正规式N（p）和N（q）是正规式p和q的NFA，则：（课
本P27）。
3)从NFA到DFA
●NFA标识记号的“并行”方法。避免回溯。
◆由于并行的方法在每试探一步时，考虑了所有的下一步状态
转移，因此走的每一步都是确定的。采用并行的方法，核心
思想是将不确定的下一状态确定化。
●确定化的两个步骤：
◆消除ε状态转移；ε的闭包。
◆消除多余一个的下一个状态转移。
●算法（课本P30）
4)DFA最小化（课本35）
三、第三章语法分析
1.词法分析：元素是字母表，组成字符串，线性结构，单词的集合。
2.语法分析：元素是终结符，组成句子，树结构（分析树），句子的集合。
1)语法规则：上下文无关文法（子集——LL文法或LR文法）
2)语法分析：下推自动机（LL或LR分析器），自上而下（预测分析）
和自下而上（移进归约）分析
3.语法错误的处理原则
1)源程序中可能出现的错误：
●词法错误：非法字符或拼写错误的关键字，标识符等。
●语法错误：语法结构错误，缺少分号等。
●静态语义错误：类型不一致，参数不匹配等。
●动态语义错误：逻辑错误，无穷递归，变量为0做处暑等等。
2)语法错误处理的目标
●清楚而准确的报告错误的出现。
●迅速的从每个错误中恢复过来。
●不应使对语法正确源程序的分析速度降低太多。
3)语法错误的基本恢复策略
●紧急方式恢复：抛弃若干输入，直至遇到同步记号。
●短语级回复
●出错产生式
●全局纠正
4.上下文无关文法（CFG）
1)定义：CFG是一个四元组G =（N，T，P，S），其中：
●N是非终结符的有限集合。
●T是终结符的有限集合，且N交T为空集。
●P是产生式的有限集合。
◆A->a，其中A属于N（左部），a属于（N并T）的闭包（右
部），若a = ε，则称A->ε为空的产生式
●S是非终结符
2)由产生式集表示CFG
●前提：若文法正确，第一个产生式的左部是文法开始符号S，则
N是出现在产生式左边符号的集合，T是所有不出现在产生式左
边符号的集合。
3)产生式的一般读法：读作“定义为”，或者“可导出”。
4)终结符与非终结符在读写上的区别。
●大写英文字母A、B、C表示非终结符。
●小写字母表示终结符。
●小写希腊字母表示任意文法符号序列。
5)产生式的缩写形式（产生式以非终结符命名）
5.CFG产生语言的基本方法（PPT9）：通过推导的方法产生语言=>
1)定义3.2（PPT10）：直接推导。
2)强调的两点：推导具有自反性，推导具有传递性。
3)定义3.3（PPT10）：由CFG G所产生的语言L(G)被定义为:
●L(G) = { ω┃S=+>ωand ω∈T* }，
●L(G)称为上下文无关语言（Context Free Language, CFL），ω称
为句子。若S=*>α，α∈(N∪T)*，则称α为G的一个句型。
4)定义3.4：在推导过程中，若每次直接推导均替换句型中最左边的非
终结符，则称为最左推导，由最左推导产生的句型被称为左句型。6.推导，分析树，语法树。
1)分析树的性质（具体语法树）：
●根由开始符号所标记。
●每个叶子都由一个终结符，非终结符，或ε标记。
●每个内部结点由一个非终结符标记。
●若A是某内部节点的标记，且X1，X2，...，Xn是该节点从左到
右所有孩子的标记，则A→X1X2...Xn是一个产生式。若A→ε，
则标记为A的结点可以仅有一个标记为ε的孩子。
2)分析树与语言和文法的关系：
●每一直接推导（每个产生式），对应一颗仅有父子关系的子树，
即产生式左部非终结符“长出”右部的孩子。
●分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结
标记，则构成一个句子。
●最左最右推导的中间过程对应的分析树可能不同，因为句型不同，
但最终的分析树相同，因为最终是同一个句子。
●分析树既反映了产生句型的推导过程，有反映了句型的结构。
3)语法树（抽象语法树）
●定义3.6：对CFG G的句型，表达式的语法树被定义为具有下述
性质的一棵树。
◆根和内部节点由表达式中的操作符标记。
◆叶子由表达式中的操作数标记。
◆用于改变运算优先级和结合性的括弧，被隐含在语法树的结
构中。
7.二义性和二义性的消除
1)二义性：若G对同一句子产生不止一颗分析树，则称G为二义的。
（一个句子多于一颗分析树，与与文法和句子有关，与采用的推导
方法无关）产生的原因是文法中缺少对文法符号优先级和结合性的
规定。
2)二义性的消除：
●改写二义文法为非二义性文法。
◆引入新的非终结符，限制了每一步直接推导均有唯一选择。
◆最终分析树的形状，仅与文法有关，而与推导方法无关。
◆非终结符的引入，增加了推导步骤（分析树增高）。
◆越接近S的文法符号优先级越低。
◆A始终在左边出现，则A产生式具有左结合性质。
●改写步骤：
◆引入一个新的非终结符，增加一个子结构并提高一级优先级。
◆递归非终结符在终极符左边，运算具有左结合性，否则具有
右结合性。
●规定二义性文法中符号的优先级与结合性，使仅产生一颗分析树。
8.正规式到CFG的转换
1)构造正规式的NFA
2)若0为初态，则A0为开始符号。
3)对于move（i，a）=j，引入产生式Ai->aAj。
4)对于move（i，空串）=j，引入产生式Ai->Aj。
5)若i是终态，则引入产生式Ai ->空串。
9.自上而下的语法分析
1)自上而下的方法分析输入序列
●对任何一个输入序列w，从S开始进行最左推导，直到得到一个
合法的句子或发现一个非法结构。
●自上而下，从左到右为输入序列建立分析树
10.自上而下的文法（消除二义性时）可能会产生的问题
1)A产生式的多个候选项的前缀相同，称为公共左因子，会造成虚假
匹配，造成大量回溯。
2)A->Aa的产生式一旦采用该产生式去替换，就会陷入死循环，分析
无法进行，称为直接左递归。
3)改变上述问题方法：
●消除左递归
●提取公共左因子
11.消除左递归
1)消除文法的直接左递归：（PPT3）
2)消除文法的左递归。
12.提取公共左因子
13.构造预测分析表
1)首先构造First和Follow集合。
编译原理期末总结复习 篇一： 一、简答题 1.什么是编译程序？ 答：编译程序是一种将高级语言程序：若源程序是用高级程 序设计语言所写，经翻译程序加工生成目标程 序，则该翻译程序就称为“编译程序”，也可称为编译器。解释程序：是高级语言翻译程序的一种，他将源语言书写的 源程序作为输入，解释一句 后就提交计算机执行一句，并不形成目标程序，就像外语翻 译中的“口译”一样，不产生全文的翻译文本。 运行系统：编译程序和运行系统合称编译系统。 (3) 程序的翻译 除机器语言程序外，用其它语言书写的程序都必须经过翻译 才能被计算机识别。这一过 程由翻译程序来完成。 编译方式是一种分阶段进行的方式，包括翻译和运行两部分。前一阶段：翻译 后一阶段：运行，由运行系统配合完成。 (4) 过程 1、词法分析阶段 这个阶段的任务是从左到右一个字符一个字符地读入源程
序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号TOKEN）。 某源程序片断如下： begin var sum, first, count: real; sum:=first+count*10 end. 保留字begin var real end 标识符sumfirstcountsumfirstcount 界符 . 逗号，逗号,冒号：分号；加号+乘号*赋值号：=整数10 10 2、语法分析阶段 是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，或语法成分，或语法范畴。 语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。 3、语义分析阶段 依据语言的语义规则，对语法分析得到的语法结构分析其含义以及应进行的运算，审查源程序中有无语义错误，为代码生成阶段收集类型信息。 4、中间代码生成
《编译原理》课程复习 五、计算题： 1、考虑下面程序 ………… Var a：integer； Procedure S(X)； Var X：integer； Begin a：＝a＋1； X：＝a＋X End； Begin a：＝5； S(a)； Print(a) End． 试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？ 答：传名：a＝12 传值：a＝6 2、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 逆波兰表示： abc*＋ab＋/d－ 三元式序列： ①(*，b，c) ②(＋，a，①) ③(＋，a，b) ④(/，②，③) ⑤(－，④，d) 3、已知文法G(S) S→a|∧|(T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的句柄。 句型归约规则句柄 ((a，a)，a)S→a a ((S，a)，a)T→S S ((T，a)，a)S→a a ((T，S)，a)T→T，S T，S ((S)，a)T→S S ((T)，a)S→S(T)(T) (S，a)T→S S (T，a)S→a a
(T，S)T→T，S T，S (T)S→(T)(T) S 4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 5、设文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。 解：S→(L)|aS’ S’→S|ε L→SL’ L’→SL’|ε FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)} FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)} FIRST(L)＝{(，a}FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε}FOLLOW(L’)＝{ }} 6、While a＞0 ∨b＜0do Begin X：＝X＋1； if a＞0 then a：＝a－1 else b：＝b＋1 End； 翻译成四元式序列。 解： (1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5) (4) (j，－，－，15) (5) (＋，×，1，T1) (6) (：＝，T1，－，×) (7) (j＞，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1，T3)
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？ 答 编译程序总框架 （1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。 （2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 （3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。 （4）优化器，对中间代码进行优化处理。 （5）目标代码生成器，把中间代码翻译成目标程序。 （6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。 （7）出错管理，把错误信息报告给用户。 编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。 （2）。语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。 （3）语义分析与中间代码产生。任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 （4）优化。任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。 （5）目标代码生成。任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。 2》．重要概念： a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。 b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等 c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。 d. 遍：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
1.编译程序的工作过程一般可包括词法分析、语法分析、语义分析、中间代码产生与优化 和目标代码生成等几个阶段，同时还有表格管理和出错处理。 2.LEX是用于词法分析的工具，Y ACC是用于语法分析的工具。 3.解释程序和编译程序的区别在于是否生成目标代码。 4.任一文法终结符集合和非终结符集合的交集是空集。 5.描述程序设计语言语法的BNF方法中，“：：=”表示定义为，“|”表示或，[W]表示W 可出现0或1次，｛W｝表示W可出现n（n≥0）次。 6.已知文法G[G]: S→aSb|ab|ε，该文法描述的语言L(G)=｛a n b n|n≥0｝。 7.单词的描述工具有正规文法、正规式和有穷自动机，他们之间存在等价性。 8.高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符和界符。 9.正则式中的“|“表示或，“*”表示闭包。 10.自顶向下语法分析方法会遇到的主要问题有回溯，以及左递归带来的无限循环。 11.算符优先分析法每次归约当前句型的最左素短语，规范归约中每次归约的是当前句型的 句柄。 12.对文法G[G]: S→a|b|cTc，T→S|TdS而言，FIRSTVT(T)=｛a,b,c,d｝。 13.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。 14.对文法G[G]: E→E*T|T, T→T+i|i的句子1+2*8+6进行归约后的结果为42（23，42）。 15.在LR(0),SLR(1),LR(1),LALR(1),四种文法中，描述能力最强的是LR(1)。 1.0型文法中每条规则左部至少包含一非终结符（√）。 2.3型文法一定是2型、1型、0型文法（√）。 3.对无二义性文法而言，无论最左推导还是最右推导，同一个句子的语法树是一样的。 4.若一个文法是递归的，则其语言中句子的个数必定是无穷个。（√） 5.文法规则右部的符号一定是终结符。（×） 6.语法树描述的是一个文法。（×） 7.若G是正则文法，则G一定是上下文无关文法。（√） 8.正则文法、正则式和有限自动机三者都是描述正则集的有力工具，它们的描述能力是等价的。（√） 9.LL（1）分析法必须要求原文法不含左公因子和左递归。（√） 10.对于LR(0)文法，我们可直接从它的项目集规范族和活前缀识别自动机的状态转换函数GO构造了LR分析表。（√） 1.BNF是一种广泛采用的描述（文法）的工具。 2.无符号常数的识别和拼数工作通常在（词法分析）阶段完成。 3.“运算符与运算对象类型不匹配”属于（语义错误） 4.将汇编语言程序翻译成机器可以执行的目标程序的工作由（汇编程序）完成。 5.在汇编过程中，汇编程序能够找到的错误包括（全部语法错误和部分语义错位） 6.由“非终结符→符号串”形式的规则构成的文法是（2型文法） 7.关于短语和句柄，正确的叙述为（直接短评才可能是句柄） 8.同正则式a*b*等价的文法是（G3:S→aS|Sb|ε） 9.文法G[S]:S→xSy|y所描述的语言是（x^nyx^n(n>=0)） 10.若G为一文法，Vt是该文法的终结符号集合，L(G)和Vt^*之间的关系是（L(G)是Vt^* 的子集） 11.有限自动机能够识别（正则文法）
复习汇总 一、第一章概述 1.文法与自动机的等价 1)0型文法—图灵机 2)1型文法—线性有界非确定图灵机 3)2型文法—非确定下推自动机 4)3型文法—有限状态自动机 2.编译技术的应用 1)语法制导的结构化编辑器 2)程序格式化工具 3)软件测试工具 4)程序理解工具 5)高级语言的翻译工具 6)等等 3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解） 1)面向机器的语言：机器指令，汇编语言 2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述 语言（正规式,产生式）等等。 4.各语言的分类（结合第二章第9小点理解） 1)过程式语言，面向对象语言：通用程序设计语言。 2)函数语言：面向特点领域的，递归特性。例如LISP语言 3)说明性，非算法式语言：LEX/YACC,SQL。 4)脚本式语言：Shell语言 5.语言之间的转换（李静PPT41） 1)高级语言之间的转换一般称为预处理或转换。 2)高级语言翻译成汇编语言或机器语言称之为编译。 3)把汇编语言翻译成机器语言称之为汇编。 4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之
为交叉汇编。 5)把机器语言翻译成汇编语言称之为反汇编。 6)把汇编语言翻译成高级语言称之为反编译。 6.编译器和解释器 1)编译器 ●源程序的翻译和翻译后的程序的运行是两个不同的阶段。 ◆编译阶段：用户输入源程序，经过编译器的处理，生成目标 程序。 ◆目标程序的运行阶段：根据要求输入数据，得出结果。 2)解释器（凡是可以采用编译器的地方均可以采用解释器） ●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执 行它。这种方式称为解释。 7.解释器的优点（对比与编译器） 1)具有较好的动态特性。 2)具有较好的移植特性。 8.解释器的缺点（对比于编译器） 1)相比于编译器需花费大量的时间。 2)占用更多的内存空间。 9.编译器的工作阶段（结合第二章6小点红色部分理解） 1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器-> 代码优化器->目标代码生成器->目标代码 2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。10.编译器各阶段的工作过程（结合第二章6小点红色部分理解） 1)源程序通过词法分析器翻译成记号流，记号流通过语法分析产生语 法树，然后根据语法树来进行适当的语义处理，语义分析产生符号 表和中间代码。 2)符号表的格式：标识符，类型，分配的地址。 3)中间代码的格式：操作符，左操作数，右操作数，结果。 4)中间代码的优化：传值的代码可以省略。
一、选择 1、构造编译程序应掌握（） A.源程序 B.目标文件 C.编译方法 D.以上三项 2、编译程序绝大多数时间花在（）上 A.出错处理 B.词法分析 C.目标代码生成 D.表格管理 3、编译程序是对（） A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 4、词法分析器的输出结果是（） A.单词的种别编码 B.单词在符号表中的位置 C.单词的种别编码和自身值 D.单词自身值 5、正规式M1和M2等价是指（） A. M1和M2的状态数相等 B. M1和M22的有向变条数相等 C. M1和M2所识别的语言集相等 D. M1和M2状态数和有向边条数 6、DFA M接受的字集为（） A.以0开头的二进制数组成的集合 B.以0结尾的二进制数组成的集合 C.含奇数个0的二进制数组成的集合 D.含偶数个0的二进制数组成的集合 7、文法G[S]:S→xSx|y所识别的语言是（）
A.xyx B.（xyx）* C.x n yx n（n≥0） D.x n yx n 8、如果文法G[S]是无二义的，则它的任何句子α（） A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导，但它们对应的语法树相同 9、采用自顶向下分析，必须（） A.消除左递归 B.消除右递归 C.消除回溯 D.提取公共左因子 10、设a、b、c是文法的终结符，且满足有限关系a〓b和b〓c，则（） A.必有a〓c B.必有c〓a C.必有b〓a D.a~c都不一定成立 11、在规范规约中，用（）开刻画可归约串 A.直接短语 B.句柄 C.最左素短语 D.素短语 12、若a为终结符，则A→α·aβ为（）项目 A.规约 B.移近 C.接受 D.待约 13、若项目集合Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是（） https://www.doczj.com/doc/7d19316852.html,LR文法 B.LR(0)文法 C.LR(1)文法 D.SLR(1)文法 14、同心集合并有可能产生新的（）冲突 A.归约 B.“移进”/“移进” C.“移进”/“归约” D.“归约”/“归约” 15、四元式之间的联系时通过（）实现的 A.指示器 B.临时变量 C.符号表 D.程序变量 16、间接三元式表示法的优点为（）
1、编译程序：是一种程序，它把用高级语言写的源程序作为数据接收，经过翻译转换产生 面向机器的代码作为输出。编译程序产生目标文件。 2、解释程序：是一种语言处理程序,它对源程序逐个语句地进行分析,根据每个语句的含义 执行语句指定的功能。广义上讲,编译程序和解释程序都属于翻译程序,但它们的翻译方式不同,解释程序是边翻译解释边执行不产生目标代码输出源程序的运行结果。而编译程序只负责把源程序翻译成目标程序输出与源程序等价的目标程序,而目标程序的执行任务由操作系统来完成即只翻译不执行。 3、解释程序：是一种程序，它的输入是某种语言的一系列语句，而他的输出则是另一种语 言的一系列语句。 4、源程序：源语言编写的程序称为源程序。 5、目标程序：目标语言书写的程序称为目标程序。 6、编译程序的前端： 机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段。某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。 7、后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目 标代码生成，以及相关出错处理和符号表操作。 8、遍：是对源程序或其等价的中间语言程序从头到尾扫视，并完成规定任务的过程，生成 新的中间结果或目标程序。第一遍：语法分析器处于核心地位。第二遍：局部优化。第三遍：全局优化。第四遍：目标代码生成。 9、一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？ 答案：一个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 10、表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 10、二义性：如果对于某文法的一个句子存在两棵不同的语法树，则该句子是二义性的。而该文法是二义性文法。 11、文法定义：文法G定义为四元组（V N，V T，P，S）。 其中V N 为非终结符集；V T 为终结符；P为产生式集合，产生式左部是V N 和V T 的并集的元素且至少包含一个非终结符，产生式右部也是V N 和V T 并集的元素；V N、V T 和P是非空有
第一章： 编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成， 代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执 行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑 上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 第三章： Chomsky 对文法中的规则施加不同限制，将文法和语言分为四大类： ） 0型文法（PSG ） 0型语言或短语结构语言 文法 Ｇ的每个产生式α→β中：若α∈Ｖ*ＶN Ｖ*, β∈(ＶN ∪ＶT)* ， 则 Ｇ是0型文法，即短语结构文法。 1型文法（CSG ） 1型语言或上下文有关语言 在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外， 则Ｇ是１型文法,即：上下文有关文法 另一种定义： 文法G 的每一个产生式具有下列形式：αA δ→αβδ，其中α、δ∈V*，A ∈VN ，β∈V+； ( 2型文法（CFG ） 2型语言或上下文无关语言 文法Ｇ的每个产生式A →α，若A ∈ＶN ,α∈(ＶN ∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。 3型文法（RG ） 3型语言或正则(正规)语言 若Ａ、Ｂ∈ＶN ，ａ∈ＶT 或 ， ' 右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ 左线性文法：若产生式为 Ａ→Ｂａ或Ａ→ａ 都是３型文法（即：正规文法） 最左（最右）推导 在推导的任何一步α β，其中α、β是句型，都是对α中的最左（右）非终结符 进行替换 规范推导：即最右推导。 规范句型：由规范推导所得的句型。 } 句子的二义性（这里的二义性是指语法结构上的。） 文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性 一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 短语 若S * αA δ且 A +β，则称β是句型αβδ相对于非终结符A 的短语。 简单短语（直接短语） 2型文法 1型文法 0型文法 3型文
《编译原理》复习资料 1、编译程序的总体结构分为、、、和五部分。 2、构造一个编译程序的三要素是：_______________，_________________，____________________。 3、被编译的语言为A语言，编译的最终结果为B语言代码，编写编译程序的语言为C语言。那么，_______语言为源语言，_____语言为宿主语言，_________语言为目标语言。 4、设文法G(S)： S→aS|Sb|a|b，则文法G(S)所识别语言的正规式为_________________________。 5、设有文法G(S)： S→Sab|bR R→S|a G(S)的语言L(G(S))={_____________________}。 6、设文法G[V]： V→aaV|bc 该文法所对应的语言L(G)=_________________。 7、C语言中表达式a + + + + + + + = 1，词法分析后，能识别出的单词个数是_______。 8、设有文法G（S为开始符号）： S→Ap|Bq A→a|cA B→b|dB FIRST(Ap)=｛_____________｝。 9、设有文法G[S]: S→AB|bb|bAC A→ε|b B→ε|aC C→aS|c 则FIRST(S)=｛_____________｝,FOLLOW(A)=｛___________｝。 10、一个LR分析器的逻辑结构包括_______________、________________和 __________________三部分。 11、被编译的程序成为_____________。 12、设字母表A=｛0｝，A*=｛____________________｝。 13、程序设计语言的单词符号一般分为：关键字、___________、___________、______________和界限符等。 14、设有文法G(S)： S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c 则FOLLOW(A)={_____________________},FIRST(S)={_____________}。 15、设文法G[S]： S→Pab|bP P→b|ε
三一 文库 （https://www.doczj.com/doc/7d19316852.html, ）*电大考试* 编译原理名词解释 1.局部优化：局限于基本块范围的优化称。 2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。 3.DISPLAY 表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display 表就是用于登记每个外层过程的最新活动记录起始地址。 5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。 6.语法：一组规则，用它可形成和产生一组合式的程序。 7.文法：描述语言的语法结构的形式规则。 8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。 9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。 10.短语：令G 是一个文法，S 划文法的开始符号，假定αβδ是文法G 的一个句型，如果有S αAδ且A β，则称β是句型αβδ相对非终结符A 的短语。 11.待用信息：如果在一个基本块中，四元式i 对A 定值，四元式j 要引用A 值，而从i 到j 之间没有A 的其它定值，则称j 是四元式i 的变量A 的待用信息。 12.规范句型：由规范推导所得到的句型。 13.扫描器：执行词法分析的程序。 14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。 15.句柄：一个句型的最左直接短语。 16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。 17.规范句型：由规范推导所得到的句型。 18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。 19.语法：是组规则，用它可形成和产生一个合式的程序。 20.语义：定义程序的意义的一组规则。 21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化 21．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 22．LL(1)文法 若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足 这两个条件的文法叫做LL(1)文法，其中 的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 23．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈ V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。 24．LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 25．语言和文法 文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈ V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符 号，且+ ∈T V x }简单的说，文法描述的语言是该文法一切句子的集合。 26．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 27．LL(1)文法 若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 28．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈ V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。 29．LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 30．语言和文法 文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈ V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符 号，且+ ∈T V x }简单的说，文法描述的语言是该文法一切句子的集合。 31.编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 32.解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 33.编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 34.解释程序和编译程序的根本区别：是否生成目标代码 35.句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 36文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 37.LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)第1个L ：从左到右扫描输入串。第2个L ：生成的是最左推导。1 ：向右看1个输入符号便可决定选择哪个产生式 38．某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 39.文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 40.一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G ：上下文无关文法。V ：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。F ：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 41.综合属性:若产生式左部的单非终结符A 的属性值由右部各非终结符的属性值决定,则A 的属性称为综合属。 42.继承属性:若产生式右部符号B 的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B 的属性为继承属性。(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。(2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。在计算时： 综合属性沿属性语法树向上传递（即传递信息的方向是自下而上）；继承属性沿属性语法树向下传递（即传递信息的方向是自上而下）。 43.语法制导翻译：是指在语法分析过程 中，完成附加在所使用的产生式上的语义规则描述的动作。 44.语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 45.中间代码（中间语言）：1、是复杂性介于源程序语言和机器语言的一种表示形式。2、一般，快速编译程序直接生成目标代码。3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 46.何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 47.为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。(2)便于移植，便于修改，便于进行与机器无关的优化。 48.中间代码的几种形式：逆波兰式（后缀式） ，三地址码（三元式、四元式、间接三元式 ） 49.符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word ）。 50.符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据 51.符号的主要属性及作用：1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区） 52.存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式。 53.静态存储分配：1、基本策略：在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）3、静态存储分配的要求：不允许递归调用，不含有可变数组。FORTRAN 程序是段结构，不允许递归，数据名大小、性质固定。 是典型的静态分配 54.动态存储分配 ：1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。2、两种动态存储分配方式：栈式，堆式栈式动态存储分配策略：将整个程序的数据空间设计为一个栈。【例】在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。 55.过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等；另一部分则是用以管理过程活动的记录信息(连接数据)。 56.活动记录（AR ）：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 (块)叫做一个活动记录。构成：1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；5、控制链；6、实参；7、返回地址 57.什么是代码优化 所谓优化，就是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少。 58.优化原则：等价原则：经过优化后不应改变程序运行的结果。
编译原理复习资料 一、填空题. 1.编译程序是一种程序，能够将某一种高级语言编写的源程序改造成另一种低级语言编写 的目标程序，它们在逻辑上等价，完成相同的工作。 2.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是_二义性的__。 3.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单 词符号，并以__单词符号或单词符号表示的源程序_的形式输出。 4.编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、和代码优化目标 代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是表格管理和出错处理。 5.目前，语法分析方法有两大类，分别为自上向下的分析方法和__自下而上_分析方法。 自上而下的分析方法是从___文法的开始符号__出发，根据文法规则正向推导出给定句子的方法。 6.属性文法是编译技术中用来说明程序设计语言的___语义__的工具。 7.若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程 序称为 ____编译程序___。 8.扫描器（程序）的任务是从_字符串__中识别出一个个_单词符号_。 9.一个LR分析器包括三部分：总控程序、_分析表_和分析栈。 10.自顶向下的语法分析方法的基本思想是：从文法的_开始符号_出发，根据给定的输入串 并按照文法的产生式一步一步的向下进行__正向推导_，试图推导出文法的给力句子__，使之与给定的输入串匹配。 11.按Chomsky分类法，文法被分成___4（0~3型文法）__类。 12.局部优化是在__基本块___范围内进行的一种优化。 13.编译程序是一种＿翻译＿程序，它将某一种高级语言编写的源程序改造成另一种低级语 言编写的目标程序，源程序和目标程序在逻辑上等价，完成相同的工作。 14.编译程序与解释程序的根本区别为__解释程序在执行中不产生目标程序_。 15.语法分析的任务是识别给定的终结符号串是否为给定文法的___句子__。 16.编译程序一般划分为＿词法＿分析、语法分析、＿语义＿分析、中间代码生成、＿代码 优化＿和目标代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是＿表格
1.Chomsky把文法分为几种类型？什么是文法的二义性？ 1）分成四种类型，即0型、1型、2型和3型。（1）0型文法：设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。（2）1型文法：若P中的每一个产生式α→β均满足|β|>=|α|，仅仅S->ε除外，则文法G是1型。（3）若P中的每一个产生式α→β满足：α是非终结符，β∈(VN∪VT)*，则此文法称为2型的。（4）若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a∈VT*，则G是3型文法。 2）如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的 2. 简述DFA与NFA的区别：DFA每次输入只对应一个结果，而NFA的依次输入可能对应多个结果，形成一个结果集。 3.什么是算符文法？并举例说明 设有文法G，如果G中没有形如A->…BC…的产生式，其中B,C为非终结符，则称G为算符文法。 例如：对于表达式的二义性文法E->E|E-E|E*E|E/E|E↑E|(E)|i 其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法为算符文法。 4.什么是3型文法？什么是文法的语言？ （1）若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a ∈VT*，则G是3型文法。 （2）文法的语言：文法是用于描述语言的语法结构的形式规则。文法描述的语言是该文法一切句子的集合。一个文法所描述的语言是唯一的。 5. 什么是文法的二义性？给出一个二义性文法实例 （1）如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的 书上：若一个文法中存在某个句子，有两个不同的最左（最右）推导，则该文法是二义的。（2）文法G=（{E},{+, * , i , (,) }, P, E），其中P为：E->i ; E->E+E ; E->E*E ; E->(E) ; 这里的非终结符E表示一类算术表达式，i表示程序设计语言中的变量。该文法定义了由变量，+，*，（和）组成的算术表达式的语法结构。 6.常见的代码优化技术有哪些？依据优化所涉及的范围分为那些级别？ 删除多余运算、代码外提、强度削弱、变换控制条件、合并已知量和复写传播、删除无用赋值。局部优化、循环优化、全局优化
第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例：（B）不是编译程序的组成部分。 A. 词法分析器； B. 设备管理程序 C. 语法分析程序； D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.编译程序与解释程序的区别 例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例：(ab|b)*c 与下面的那些串匹配？（ACD） A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 与后面的那些串匹配？（BC） A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)*与后面的那些串匹配? （ADE） A.ba B.bba C.ababa D.aa E.baa 文法的定义（四元组表示） 文法G定义为四元组（V N，V T，P，S） V N：非终结符集 V T：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） 例：给定文法，A::= bA | cc，下面哪些符号串可由其推导出（①② ⑤）。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例：已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导：i*i+i 推导过程：E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例：假设G一个文法，S是文法的开始符 号，如果S=>*x，则称x是句型。 例：对于文法G，仅含终结符号的句型称 为句子。 ●语言的形式定义 例：设r=(a|b|c)(x|y|z)，则L(r)中元素为9 个。 例：文法G产生式为S→AB，A→aAb|ε， B→cBd|cd，则B∈L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb ●等价文法 例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ●文法的类型 0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系， 例：文法S→abC|c，bC→d是几型文法？0 型 例：文法S→abC，bC→ad是几型文法？1 型 例：文法G[A]：A→ε，A→aB，B→Ab，B→a 是几型文法？2型 例：文法S→a|bC，C→d是几型文法？3 型 ●最左（右）推导