编译原理文字总结
1.高级程序设计语言的翻译主要有两种方式：编译和解释。2.编译过程概述：
(1)词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的
单词（亦称单词符号或符号）如基本字，标识符，常数，算符和界符。
(2)语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类
语法单位（语法范畴），如短语，子句，句子，程序段和程序等
(3)语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并
进行初步翻译（产生中间代码）。包括静态语义检查和中间代码的翻译。(4)优化：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省
时间和空间）的目标代码。
(5)目标代码生成：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代
码。
编译程序结构框图
3．文法是表述语言的语法结构的形式规则。
4.所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。
5.形式上说，一个上下文无关文法G是一个四元式（VT,VN,S,＆）其中VT是一个非空有
限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=；S是一个非终结符号，称为开始符号；&是一个产生式集合，每个产生式的形式是P→a，其中P属于VN，a属于（VT∪VN）*。开始符号S至少必须在某个产生式的左部出现一次。
6.推导每前进一步总是引用一条规则（产生式）。7.假定G是一个文法，S是它的开始符号。如果Sa，则称a是一个句型（0步或若干步）。
仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。L(G)=｛a|Sa&a∈VT*｝例如终结符号串（i*i+i）是文法（2.1）的一个句子。8.从一个句型到另一个句型的推导过程往往不是唯一的。所谓最左推导是指任何一步ab都是对a中最左非终结符进行替换的。同样可定义最右推导。9.一颗语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最
右）推导。这样的一颗语法树是这些不同推导过程的共性抽象，是它们的代表。一个句型不一定只对应唯一的一棵语法树，也就是不一定只有唯一的一个最左（最右）推导。
+10.某文法如果存在某个句子对应两棵不同的语法树（证明一个文法是二义的），则说这个
文法是二义性文法。或者说，若一个文法中存在某个句子，有两个不同的最左推导或最右推导，则该文法是二义的。
11.文法的二义性和语言的二义性是两个不同的概念。
12.二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切的判定一个文
法是否为二义的。
13.形式语言鸟瞰：文法分为4种：0型，1型，2性和3型
（1）0型文法也称短语文法，0型文法的能力相当于图灵机，任何0型语言就是递归可枚举的
（2）1型文法也成为上下文有关文法。对非终结符进行替换的时务必考虑上下文，并且一般不允许替换成空串e
（3）2型文法也称上下文无关文法，非终结符的替换可以不必考虑上下文。
（4）3型文法也称正规文法，包括右线性文法（非终结符在右边）和左线性文法。14．一个确定有限自动机（DFA）M是一个五元式，M=(S,,,S0,F)，
S：有限状态集，它的每个元素称为一个状态。
：有穷字母表，它的每个元素称为一个输入字符。
：状态转换函数，SS{}是单值全映射函数；S0：唯一的初态，S0SF：终态集（可空），FS
15.一个DFA可以用一个矩阵表示，行表示状态，列表示输入字符，矩阵元素表示（s,a）
的值。这个矩阵称为状态转换矩阵。
16.一个DFA也可表示成一张确定的状态转换图。对于*中的任何字a，若存在一条从
初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于a，则称a可为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字e可为M所识别。DFAM所能识别的字的全体记为L(M)。17.一个非确定有限自动机（NFA）M是一个五元式，M=(S,,,S0,F)，
S：有限状态集，它的每个元素称为一个状态。
：有穷字母表，它的每个元素称为一个输入字符。：一个从S到S的子集的映照，SS0：非空初态集，S0SF：终态集（可空），FS
18.有限自动机中若有e则为NFA。状态图中若某一状态输入某字符转换至多个状态
则为NFA。DFA是NFA的特例。对于每个NFAM存在一个DFAM”，使L（M）=L(M”)。NFA确定化为DFA的方法：子集法（P49-50）（必定在有限步内完成）19.所谓自上而下语法分析，是从文法的开始符号出发，反复使用各产生式，寻找“匹配”
于输入符号串的推导。从语法树的角度来看，自上而下方法是从文法符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。这种方法是带回溯的，是一个推导+匹配的过程。面临的问题：
1.文法的左递归问题2.回溯
3.匹配成功可能是暂时的(虚假匹配)4.当匹配不成功时不知道出错位置5.效率太低,代价极高20.直接左递归的消除：将P->Pa|b改写为P->bP’P’->aP’|e
21.如果文法G不含以e为右部的产生式并且不存在P=+>P，下述算法消除左递归
1）对文法G中所有状态进行排序，任意顺序均可，得P1P2P3...Pn2)fori=1tonbegin
forj=1toi-1beginif存在Pi-->PjY
将之改写为Pi-->a1Y|a2Y|a3Y...PmY//其中，Pj-->a1|a2...|am是关于Pj的所有规则endend采用算法一消除Ai产生式的左递归end
22.为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。（不能是虚假匹配）要求是非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选ai和ajFIRST(ai)∩FIRST(aj)=空。
23.为达到上述目的，办法是提取公共左因子：假定关于A的规则是A->b1|b2||bn|r1|r2|r3|…|rm其中每个r不以开头，那么将之改写成A->A’|r1|r2|r3||rmA’->b1|b2|b3||bn。
24.LL(1)文法：第一个L表示从左导游扫描输入串,第二个L表示最左推导,1表示分析时每一步只需向前查看一个符号文法满足以下条件
（1）文法不含左递归
（2）对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即若A->a1|a2||an则FIRST(ai)∩FIRST(aj)=空（i!=j）
（3）对文法中的每个非终结符A，若它存在某个候选首符集包括e，则FIRST(A)∩FOLLOW（A）=空25.实现LL（1）的一种有效方法是使用一张分析表和一个栈进行联合控制：预测分析程序。26.对每个文法符号XVT∪VN，构造FIRST(X)的方法：（1）若XVT，则FIRST（X）=｛X｝。（2）若XVN，且有产生式X->a…，则把a加入到FIRST（X）中，若X->e也是一条产生式，则把e也加到FIRST（X）中。（3）若X->Y…是一个产生式，且YVN，则把FIRST（Y）中的所有非e-元素都加入到FIRST（X）中；若X->Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且FIRST（Yj）（1aB是一个产生式，或A->aBb是一个产生式且B=>e,则把FOLLOW（A）加至FOLLOW（B）中。
28.构造预测分析表M的算法是：以文法G的终结符为表头，以产生式左部为列头（1）对文法G的每个产生式A->E执行第二步和第三步（2）对每个终结符aFIRST(E),把A->E加至M[A,a]中；（3）若eFIRST（E），则对任何bFOLLOW（A）把A->E加至M[A,b]中（4）把所有无定义的M[A,a]标上“出错标志”。29.我们所讨论的自下而上分析法是一种移进-归法法。这种方法的大意是用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。
30.在算符优先分析中，规范对象（可归约串）：最左素短语，在“规范归约”分析中，规范对象（可归约串）：句柄（最左直接短语）。
31．短语，直接短语，一个句型的最左直接短语称为该句型的句柄。32.最右推导通常成为规范推导,由规范推导所得的句型成为规范句型如果文法G是无二义的,则规范推导(最右推导)的逆过程必须是规范规约。
规范归约步骤表：表头：1.步骤（标号，从0开始）2.符号栈（步骤0时为#）3.输入串（步骤0时为输入串+#）4.动作（步骤0时为预备，分为进和归，归包括所用产生式）
最后一行4列值分别为步骤号#和文法开始符号#接受33.算符优先分析法1.不是一种规范规约法2.算符优先就是寻早可能相继出现的终结符a和b的优先关系3.任意产生式右部不能都不含有2个相继的非终结符4.终结符优先级只有一种5.特别有利于表达式分析，宜于手工实现。
34.算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归约步骤，这既是它的优点，同时也是它的缺点。因为忽略非终结符在归约过程中的作用，存在某种危险性，可能导致把原本不成句子的输入串误认为是句子。这种缺陷容易从技术上弥补。
35.一个文法，若它的任一产生式的右部都不含2个相继（并列）的非终结符，则为算符文法。
36.算符优先表：表头和列均为终结符号，表元素为终结符的优先关系<>=
37.属性文法(属性翻译文法)在上下文无关文法的基础上,为每个文法符号配备若干相关的’值’（称为属性）.这些属性代表与文法相关的信息。属性的分类:综合属性(自下而上)和继承属性(自上而下)
38.语法制导翻译：给文法每个产生式制造一个相应的语义子程序,完成对应的翻译工作,分析过程中每当语法用一个产生式进行规约或推导,驱动对应的语义子程序工作。
39.中间语言的形式:后缀式（又称逆波兰表示法）三地址代码(三元式,四元式)DAG图表示后缀式举例：（a+b）*(c+d)ab+cd+*后缀式不使用括号，不论从哪一端进行扫描，都能对它正确进行唯一分解。40.赋值语句的翻译：未完成
41.参数传递:形参实参途径:传地址传值传名
42.存储分配策略：静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，反释放者退回给堆。
43.活动记录:是一个连续存储块,存储了管理过程在一次执行中所需要的信息,使用一个连续的存储块。C的过程包括：过程调用，过程进入，数组空间分配和过程返回。44.优化:对程序进行等价变换,使得从变换后的程序出发,能生成更有效的目标代码原则:1.等价原则:经过优化后不应改变程序的运行结果2.有效原则:使优化后的目标代码运行时间较短,占用的存储空间较少3.合算原则:应尽可能以较低的代价取得叫好的优化效果分类:局部优化:删除公共子表达式删除无用代码合并已知量循环优化:代码外提强度削弱删除归纳变量全局优化:常用优化技术：删除公共子表达式强度削弱复写传播删除归纳变量删除无用代码合并已知量代码外提部分概念：基本块:程序中顺序执行的语句序列,其中只有一个入口和出口,入口就是其中的第一个语句,出口就是最后一个语句
流图:将控制流的信息增加到基本块的集合上来表示某个程序45.目标代码形式:3种1.能够立即执行的机器语言代码,所有地址已定位2.待装配的机器语言模块,当需要执行时,由连接装入程序把他们和某些运行程序连接起来转换成能执行的机器语言代码3.汇编语言代码:尚需经过汇编程序汇编,转换成机器语言可执行的机器语言代码
扩展阅读：编译原理大总结
《编译原理》期末复习指导
本课程是计算机专业的重要专业课之一，主要介绍程序设计语言编译构造的基本原理和基本实现方法。本课程主要讲授形式语言、有限状态自动机和词法分
析、自顶而下和自底而上的语法分析、中间代码生成、存储器的动态分配与管理、符号表的组织与管理、代码生成、出错恢复等内容。通过本课程学习，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。
一、通过本课程的学习，应使学生达到以下基本要求：
1、正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任务；熟悉编译程序总框；了解编译程序的生成过程和构造工具。
2、理解程序语言词法、语法和语义等概念；熟悉高级程序语言一般结构和主要共同特征。正确理解上下文无关文法基本概念，包括：文法的定义、编写、句型、句子、语言、语法树、二义性等；理解三种参数传递方式：传值、传地址、传名的含义。
3、理解词法分析器功能及形式；熟练掌握词法分析器设计的原理，掌握运用状态转换图进行词法分析器设计。
4、正确理解自顶而下分析的基本思想；熟练掌握递归下降分析基本方法：消除左递归，消除回溯，构造递归下降子程序；掌握预测分析程序的基本原理和预测分析表构造；理解LL(1)方法的定义。
5、正确理解自下而上语法分析的基本思想，以及归约、短语、句柄、分析树等概念；掌握算符优先分析基本方法：算符优先表和和算符优先函数构造技术。6、正确理解语法制导翻译基本原理；掌握基于属性文法的处理方法，了解自上而下分析制导翻译基本思想和实现方法。
7、熟悉常见的几种中间语言：四元式、三元式、逆波兰表示；掌握各种语句到四元式的翻译方法，包括：简单算术表达式，布尔表达式，控制语句，数组引用，过程调用等。8、理解符号表的作用及符号表组织和使用方法，了解名字的作用范围，了解符号表中一般应包含的内容。
9、正确理解目标程序运行进存储空间的使用和组织管理方式；理解静态分配和动态存储分配基本思想；掌握FORTRAN存储分配的处理方式；掌握栈式动态分配中活动记录的作用、组织、内容及使用；了解嵌套过程语言程序运行时整个运行栈的内容的组织。
10、正确理解代码优化的定义和各种可能的优化概念；掌握用DAG表示进行局部优化的方法。
11、正确理解代码生成过程的基本问题，理解待用信息、寄存器描述和地址描述等概念；掌握简单代码生成算法、寄存器分配策略。二、文字教材
文字教材是教学媒体的核心，是传递教学信息及学生进行自主学习的基本依据，是整个教学媒体体系的基础。包括主教材、学习指导书和参考资料汇编、教学大纲、课程教学设计方案、复习提要等。1、《编译原理》徐国定编著，高等教育出版社。参考资料：
1、《程序设计语言编译原理（第3版）》陈火旺、刘春林等编著，国防工业出版社。
2、《程序设计语言与编译》龚天富、侯文永编，电子工业出版社。3、《编译原理习题与解析》伍春香编著，清华大学出版社。4、《编译原理》吕映芝张素琴蒋维杜，清华大学版社。
三、教学内容和教学要求第一章概论
主要内容：编译程序，编译过程概述，编译程序的结构，编译程序与程序设计环境，编译程序生成，学习构造编译程序。
重点：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。第二章形式语言基础主要内容：程序语言定义，初等数据类型，数据结构，高级高级语言的一般特性，程序结构，语句与控制结构，上下文无关文法，语法分析树与二义性。重点：上下文无关文法，程序语言定义参数传递。第三章有限状态自动机和词法分析
主要内容：词法分析器任务，词法分析器设计，正规表达式与有限自动机，词法分析器自动生成。
重点：词法分析器的任务与设计，状态转换图。第四章自顶向下句法分析
主要内容：语法分析器的功能，自上而下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序，自上而下分析的错误诊察，语义错误诊察。
重点：递归下降子程序，预测分析表构造，LL(1)文法。第五章自底向上句法分析
主要内容：自下而上语法分析（算符优先分析法），算符优先分析，LR分析器，LR(0)项目集族和LR(0)分析表的构造，SLR分析表的构造，规范LR分析表的构造，出错处理概述，词法分析阶段的错误诊察，语法分析（自下而上）阶段的错误诊察，语法分析器自动产生工具YACC。重点：归约，算符优先表构造，LR分析法。第六章中间代码生成和符号表
主要内容：中间语言，说明语句，赋值语句的翻译，布尔表达式的翻译，控制语句的翻译，过程调用的处理各种常见中间语言形式，各种语句到四元式的翻译。符号表的组织与作用，整理与查找，名字的作用范围，符号表的内容。重点：三种中间语言：四元式、三元式、逆波兰表示；算术表达式的翻译，布尔表达式的翻译，控制语句的翻译。符号表的作用与内容。第七章运行时刻存储和环境管理
主要内容：目标程序运行时的活动，运行时存储器的划分，静态存储管理，简单的栈式存储分配的实现，嵌套过程语言的栈式实现，堆式动态存储分配。重点：静态分配策略和动态分配策略基本思想，嵌套过程语言栈式分配，活动记录、运行时栈的组织。第八章代码生成
主要内容：目标机器模型，一个简单代码生成器，寄存器分配，DAG目标代码，窥孔优化。
重点：简单代码生成器，寄存器分配策略。第九章出错恢复
主要内容：词法分析的出错恢复，LR和LL句法分析的出错恢复重点：错误的恢复方法。
四、考核方式说明
该课程的考核由形成性考核和期末课程考核两部分组成。其中形成性考核成绩由平时作业和上机实验两部分成绩组成,各占总成绩的10%，期末课程考核占总成绩的80%。
平时作业考核：要求学生认真完成平时作业，各办学点应组织作业的批改和成绩的核定。平时作业的成绩评定标准和要求按省电大有关文件执行。上机实验考核：学员必须完成规定的上机实验，并撰写实验报告，由辅导实验的老师批改并评定成绩，学员实验成绩评定单必须加盖承担实验单位的公章方能生效。
课程结业考核：该课程的结业考核在期末进行，采用笔试、闭卷，由省电大统一组织命题，试卷采用百分制，卷面成绩按80%的比例折算计入总成绩。四、考试题型
试题类型包括：选择题，判断题，填空题，简答题，应用题。模拟试题
一、单项选择题
1．把汇编语言程序翻译成机器可执行的目标程序的工作是由______完成的。A．编译器B．解释器C．汇编器D．预处理器2．编译过程中，语法分析器的任务是______。1)分析单词是怎样构成的
2)分析单词串是如何构成语句和说明的3)分析语句和说明是如何构成程序的4)分析程序的结构
A．2和3B．3和4C．2，3和4D．1，2，3和4
3．高级语言编译程序常用的语法分析方法中，递归下降分析法属于______分析方法。
A．自左至右B．自顶向下C．自底向上D．自右向左4．算符优先文法是指_______的文法。
1)没有形如U->…VW…的规则（U，V，W∈Vn）
2)终结符号集Vt中任意两个符号对之间至多有一种优先关系成立。3)没有相同的规则右部。4)没有形如U->ε的规则
A．1，2B．1，2，3C．1，2，3，4D．1，2，45．动态存储分配时，可以采用的分配方法是1)以过程为单位的栈式动态存储分配2)堆存储分配3)最佳分配方法
A．1B．2C．1，2D．1，2，3
二、填空题
1．编译方式和解释方式的根本区别在于__________________。
2．LL（1）分析法中，第一个L的含义是_________________，第二个L的含义是___________________，“1”的含义是____________________。
3．过程调用时，参数的传递方法通常有__________、__________、__________和传名。
4．一个上下文无关文法所含四个组成部分是____________集、______________集、_____________集和______________集。
三、判断题
1．算符优先关系表不一定存在对应的优先函数。…………（）2．每个文法都能改写为LL(1)文法。………………………（）3．符号表由词法分析程序建立，由语法分析程序使用……（）4．上下文无关文法规则的左部一定是非终结符号…………（）5．LL（1）文法有可能是二义性的。…………………………（）
四、简述题
1．简述词法分析阶段的任务。
2．什么是语法制导翻译？
3．什么是素短语？
4．什么是静态存储分配？
5．画图说明编译程序的组成结构。
五、综合应用题1．设文法G(S)：S→(L)|aS|aL→L，S|S
(1)消除左递归和回溯；
(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。
2．已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i
(1)给出句型(T*F＋i)的最右推导及画出语法树；(2)给出句型(T*F＋i)的短语、素短语。参考答案
一、单项选择题题号1答案C二、填空题
1．是否生成目标代码
2．从左向右进行分析，每次进行最左推导，向输入串中查看一个输入符号3．传值，传地址，传结果（顺序可互换）
2C3B4D5C4．终结符、非终结符、开始符号、产生式（顺序可互换）
三、判断题1．√2．×3．×4．√5．×
四、名词解释
1、答:词法分析的基本任务是从左向右扫描每行源程序的符号，识别出单词及其属性，把单词换成统一的内部表示送给语法分析程序。同时还要完成在语法分析之前需要做的工作，如删除注解、空格、换行符等非必要信息，把标识符登录到符号表及某些预加工处理等。
2、答:语法制导翻译就是在进行语法分析的同时，完成语义的分析，即在语法分析的过程中，根据语言的语义定义随时翻译已识别的那部分语法成分的全部含义。
答:有以下特征的短语称为素短语：1)它首先是一个短语。2)它至少含一个终结符号。3)除自身外，不再包含其它素短语。
3、答:如果在编译时就能确定一个程序在运行时所需要的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并确定每个数据项的存储单元地址，而这些数据项的存储地址在运行时始终不变，这就是静态存储分配。4、答：表格管理词法分析语法分析语义分析中间代码生成代码优化目标代码生成错误处理
五、综合应用题1．解：(1)
S→(L)|aS’S’→S|εL→SL’L’→SL’|ε(2)
FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}(3)SS’La，()＃S→aS’S→(L)S’→SS’→εS’→SS’→εS’→εL→SL’L→SL’L’L’→εL’→ε2．答：(1)最右推导：
E→T→F→(E)→(E＋T)→(E＋F)→(E＋i)→(T＋i)→(T*F＋i)语法树：ETF(E)E+TTFT*Fi
(2)短语：(T*F＋i)，T*F＋i，T*F，素短语：T*F,i
i
友情提示：本文中关于《编译原理文字总结》给出的范例仅供您参考拓展思维使用，编译原理文字总结：该篇文章建议您自主创作。
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
《编译原理文字总结》
由互联网用户整理提供,转载分享请保留原作者信息,谢谢!
http://m.bsmz.net/gongwen/747429.html
- 上一篇：通信原理总结