编译原理复习资料

(1) 简述规范归约的基本思想。

（第五章课件第5张）用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

(2) 阐述编译程序各个组成部分主要完成的工作。

（课本P2~P4）词法分析的任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。

语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。

语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。

优化：在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。

目标代码生成：把中间代码变换成特定机器上的低级语言代码。

(3) 什么是编译器的前端和后端，这样划分有何意义？（课本P7）编译器粗略分为词法分析，语法分析，类型检查，中间代码生成，代码优化，目标代码生成，目标代码优化。

把中间代码生成及之前阶段划分问编译器的前端，那么后端与前端是独立的。

后端只需要一种中间代码表示，可以是三地址代码或四元式等，而这些都与前端生成的方式无关。

也就是不论你前端是用fortran 还是c/c++,只要生成了中间代码表示就可以了，后端是不管你是用哪种语言生成的。

(4) 乔姆斯基把文法分为哪几种类型？对这几种类型文法作简要说明。

（课本P34）把文法分成四种类型：0，1，2，3型。

与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。

0型(短语文法，图灵机)：产生式形如：α→β其中：∈α (VT ⋃ VN)*且至少含有一个非终结符；∈β (VT ⋃ VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：α→β其中：|α| ≤ |β|。

仅Sε→例外，但此时S不得出现在任何产生式的右部。

2型(上下文无关文法，非确定下推自动机)：产生式形如： A →β其中：A∈ VN；∈β (VT ⋃ VN)*。

a+b=5 a=7 x=5 y=3 b=3 z=7
(4) 所谓传名是在进入调用段之前不对实在参数预先进行计值，而 是过程中每当使用到相应的形参时才对它实行计值。因序),每当过程体中使用到相应 形参时就调用这个子程序。 因此，过程体执行y:=y+1;语句，实现时处理成为： a=a+1; 过程体执行z:=z+x;语句，实现时处理成为： a=a+(a+b); 执行上述两语句后，a的值是 9。因此，程序执行后输出 a的值是 9。 综上所述程序执行时a的输出： (1)传值：2 (2)传地址：8 (3)得结果：7 (4)传名：9 5、几个基本概念 考虑一个有穷字母表∑字符集,其中每一个元素称为一个符号,∑上的
程序是由函数或过程构成的，程序的任务是通过函数或过程之间的 协作（相互调用）l来完成的，函数或过程的调用有以下4种方式：传地 址（call-by-reference）、得结果（call by result）、传值（call-byvalue）和传名（call by name）。 定义函数Swap，其中M、N是形式参数，简称形参。 Void Swap(int M，int N) { int t; t=N; N=M; M=t; } 函数调用： Swap（I,J）；其中I和J是实在参数，简称实参。下面我们以下面的 程序为例分别讨论4种参数传递的方式。
（2）这种类型的数据对象可以具有的值； （3）可以作用于这种类型的数据对象的操作。 一个程序语言必须提供一定的初等数据类型，包括这些数据类型上能 进行的运算的定义。不同的语言含有不同的初等数据成分。常见的初等 数据类型有： （1）数值类型：整型、实型、复数、双精度， 运算：+，-，*，/等 （2）逻辑类型：布尔运算：∨，∧，┑ （3）字符类型：符号处理 （4）指针类型：指针式把内存地址作为其值的数据类型，通过指针可 以操作内存空间。 程序语言中的各种名字都是用标识符表示的。标识符是指由字母、 下划线和数字组成的，以字母或下划线为开头的一个字符串。名字和标 识符在形式上难于区别，标识符是一个没有意义的的字符序列，而名字 则有明确的意义和属性。用计算机术语来说，每个名字可看成是代表一 个抽象的存储单元，这个单元可含有一位、一字节或相继的多个字节。 该单元的内容则被认为是名字的值。仅把名字看成代表一定的存储单元 还是不够的，我们还必须同时指出它的属性（数据类型）。只有指定了 属性的存储单元，其值才是可以理解的。 一个名字的属性包括类型和作用域。名字的类型决定了它能具有什 么样的值， 值在计算机内部的表示方式，以及对它能施加什么运算。 名字的作用域规定了它的值的存在范围。 除了初等数据类型外，有些语言还提供了由初等数据构造复杂数据 的手段。常见的复杂数据类型有： （1）数组。一个数组是由同一类型数据所组成的某种n维矩形结 构。数组在内存中占有一块连续的空间，系统采用基地址加偏移量的方 式来访问数组元素。 （2）记录。从逻辑上讲，记录是由已知的数据组合起来的一种结 构。一个记录通常含有若干个分量，每个分量称为记录的一个栏（或域 field）。每个分量都是一个确定类型的数据，不同的分量的数据类型可 以不同。 （3）字符串、表格、栈和队列。 （4）抽象数据类型。抽象数据类型封装了数据和操作，在面向对象 程序设计语言中，Ada通过程序包（package）提供了数据封装的支持， Smalltalk、C++和Java语言则通过类（class）对抽象数据类型提供支 持。 4、函数调用的方式

1.简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检查。

2.考虑文法G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。

解：消除文法G[S]的左递归：S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子：S→(T) | aS′ S′→+S | ε T→ST′T′→,ST′| ε3.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (A<C ∧B<D) { if(A ≥ 1) C=C+1;else while (A ≤ D)A=A+2;}。

解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：100 (j<,A,C,102) 101 (j,_,_,113)102(j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 11310.短语------令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。

15.句柄------一个句型的最左直接短语。

18.素短语------素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。

3．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。

给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的语法树。

这棵树具有下列特征：(1)根节点的标记是开始符号S。

编译原理复习编译原理复习⼀、基本概念（填空15分，选择10分，简答：15分）1、编译程序按扫描源程序的遍数分类可以分为哪两类？⼀遍扫描、多遍扫描2、⾼级语⾔的单词分类有哪些？基本字、运算符、标识符、常数、界符3、⼆义性⽂法，⼆义性语⾔的定义？⼆义性⽂法：⽂法G对某句型存在⾄少两种不同的语法树。

⼆义性语⾔：某语⾔对应的任意⼀种⽂法都是⼆义性⽂法4、DFA的定义及组成：确定的有穷⾃动机； M=(K,∑,f, S,Z)K是⼀个有穷集，它的每个元素称为⼀个状态；∑是⼀个有穷字母表，它的每个元素称为⼀个输⼊符号，所以也称∑为输⼊符号表； F是转换函数，是K×∑→K上的映像S∈K，是唯⼀的⼀个初态Z K，是⼀个终极态，终态也称为接收状态或结束状态5、最左推导、规范推导的定义：最左推导：若x和y是符号串α中有两个以上的⾮终结符号时，对推导的每⼀步坚持把α中的最左⾮终结符号进⾏替换，称为最左推导。

规范推导：通常，我们把能由最左(右)推导推出的句型称为左(右)句型。

另外，也常把最右推导称为规范推导，⽽把右句型称为规范句型。

6、确定的⾃顶向下分析⽅法通常有哪两种？采⽤确定的⾃顶向下分析的前提条件是什么？递归⼦程序法、预测分析法对每⼀个⾮终结符A的两个不同产⽣式，A→α，B→β，满⾜SELECT（A→α）∩SELECT（B→β）=?，其中αβ不同时能→ε7、词法分析的常⽤⽅法有哪两种？⾃顶向下；⾃底向上。

8、简单优先分析法、算符优先分析法属于、LR(0)分析法分别属于何种归约？规范规约、⾮规范规约、规范规约9、⾼级程序设计语⾔的翻译⽅式主要有哪两种，⼆者的根本区别在于哪⾥？⽅式：编译程序、解释程序区别：⽣不⽣成⽬标代码10、词法分析程序和语法分析程序的任务分别是什么？词法分析是编译的第⼀阶段，它的主要任务是按语⾔的词法规则，从左⾄右逐个字符地对源程序进⾏扫描，从源程序中识别出每个单词，并把每个单词转换成它们的内部表⽰，即所谓的token，同时进⾏词法检查。

第1部分一简答题1．编译程序按功能分为哪几个阶段？各个阶段的主要功能？2．实现高级语言程序的途径有哪几种？它们之间的区别？3．给出描述非0数字作为开始符的奇数字符串的正则表达式或正则式。

4．判断字符串a n b n（n >0）是否可用确定自动机识别？如果能，则画出自动机，否则说明原因5．对如下文法：G[S]：S → a b S | a a B | a dB → b b B | b分别给出句子abaabbb和ad的句柄6．有如下文法，给出每个产生式的Predict集。

P → begin S endS → id := E ; S |E → n | id7．什么是可规约活前缀？举一例说明。

8．通过合并LR（1）文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？9．设对偶表（L，N）分别表示程序在当前位置的层数和偏移量，确定下面程序段中括号部分的内容。

假设系统规定整型(int)变量占1个单元，实型(real)变量占2个单元。

(L, N) Type at = array of [1..10] of int;(①) var x ：real;(②) function f ( ( ？,M) var a: at,(③) b: at,(④) var x: real ) : int10．给出活动记录空间结构?并给出各部分的存储对象？11．有如下文法：G[S]：S → ( L ) | aL → S PP → , S P |给出该文法的动作文法打印每个a的嵌套深度。

例如（a，（a），（a））打印1，2，2。

12．文法可分为几类；各举一例。

13．Display表的作用？14．如下是当前执行某个过程时的活动记录，设变量x的层数和偏移量分别为L和Off，说明如何访问变量x。

15．当实参为变量，形参分别为变参和值参时，传参的区别。

二、说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。

中间代码生成的自动生成工具
工具介绍
自动生成工具是一种辅助编译器设计的软件工具，它可以自动生成中间代码，从而简化编 译器的设计和实现过程。
工具分类
根据生成中间代码的方式不同，自动生成工具可以分为解析型和抽象语法树型两类。解析 型工具将源代码直接翻译成中间代码；抽象语法树型工具则将源代码先转换为抽象语法树 ，然后再将抽象语法树转换为中间代码。
Antlr
一个强大的语法分析器生成器，支持多种语言和复杂 的文法规则。
GOLD
一个高效的语法分析器生成器，支持多种目标语言和 优化选项。
04 中间代码生成
中间代码生成的定义与任务
定义
中间代码生成是编译过程的一个阶段，将源代码转化为一种中间表示形式，这种中间表 示形式称为中间代码。
任务
其任务包括控制结构的抽象、语义的消除、代码优化等，以简化后续的代码优化和目标 代码生成阶段。
循环结构的优化
循环展开
将循环体中的代码复制到循环 外部，以减少循环次数。
循环合并
将多个循环合并为一个循环， 以减少循环次数。
循环嵌套
将一个循环嵌套在另一个循环 内部，以减少循环次数。
循环展开与循环合并的优 缺点
循环展开可以减少循环次数， 但会增加代码量；循环合并可 以减少代码量，但会增加循环 次数。在实际应用中，需要根 据具体情况选择合适的优化方 法。
算法优化
根据问题的特点，选择合适的算法，以提高程序 执行效率。
系统资源优化
根据系统资源的特点，合理分配和利用系统资源， 以提高系统运行效率。
循环优化
1 2
循环展开
将循环体中的操作展开，以减少循环次数和减少 循环开销。
循环合并
将多个循环合并为一个循环，以减少循环次数和 减少循环开销。

2、解：改写后的文法变为 Z∷=(A) , A∷=a{abb}
过程Z INPUTSYM=’(’ N 错误
Y INPUTSYM=下一个符号
过程A INPUTSYM=’)’ Y INPUTSYM=下一个符号 出口 非终结符号Z的分析程序 N 错误
过程A N INPUTSYM=’a’ Y INPUTSYM=下一个符号 INPUTSYM=’a’ INPUTSYM=下一个符号 Y INPUTSYM=’b’ N 错误
q3b=ε-closure(δ(q3,b))= ε-closure({8})={8} =q6; q4a=ε-closure(δ(q4,a))= ε-closure({2,4})={2,4,6,7,9} =q1; q4b=ε-closure(δ(q4,b))= ε-closure({5,8})={5,6,7,8,9} =q2; q5a=ε-closure(δ(q5,a))=ε-closure({φ})= φ; q5b=ε-closure(δ(q5,b))= ε-closure({8})={8} =q6 q6a=ε-closure(δ(q6,a))= ε-closure({7})= {7,9}=q5; q6b=ε-closure(δ(q6,b))= ε-closure({φ})= φ； 计算到此，不再有新的状态。
8、栈式符号表工作过程。
9、程序运行时存储分配方法有哪 些？动态存储分配包括两种方式 ？ 10、代码优化常用的三种方法 ？
二、针对语言构造文法
1、L(G)={奇正整数}; 2、L(G)={anbm|n,m≥1};
1、A::=1|3|5|7|9|NA N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9 N::=0|1|2|3|4|5|6|7|8|9

1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

（4）优化器，对中间代码进行优化处理。

（5）目标代码生成器，把中间代码翻译成目标程序。

（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。

（7）出错管理，把错误信息报告给用户。

编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。

（2）。

语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。

（3）语义分析与中间代码产生。

任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

（4）优化。

任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

（5）目标代码生成。

任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。

2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。

b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。

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一定是上下文无关文法。

复习汇总一、第一章概述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)工作过程中的每个阶段均采用了符号表管理器，出错处理器。

总复习■第1章1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。

2、编译程序是计算机系统中重要的系统软件！3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。

4、编译的各个阶段。

答：整个编译过程可以分为5个阶段：词法分析，语法分析，语义分析及中间代码生成，代码优化和目标代码生成。

5、编译程序的结构框图或步骤。

6、遍（趟）：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序的过程。

■第2章1、符号串的基本运算。

2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。

3、推导（最左、最右）、句型、句子、短语、句柄4、乔姆斯基层次中：L3 ⊂ L2 ⊂ L1 ⊂ L0■第2章例题已知文法G[E]：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i（1）该文法的开始符号是什么？（2）请给出该文法的终结符号集合VT和非终结符号集合VN。

（3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。

■第3章1、词法分析程序的输出是单词符号序列。

2、DFA的三种表示形式——状态转移图、状态转换表和五元组表示（Q, ∑, f, S, Z ）；3、正规式向DFA的转换：（1）正规式——NFA;（转换原则见下页）（2）NFA——DFA；（3）DFA的最小化。

4、DFA向正规式的转换。

正则式向NFA转换的原则：例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。

■第4章1、语法分析方法的各种分类；2、LL(1)分析方法。

提示：在此算法中注意First集和Follow集的求法。

并且一定要注意分析过程中步骤要完整。

（分析步骤见下页总结）例：文法：S◊a|^|(T) T◊T,S|S试判断该文法是否是LL(1)文法。

习题4：P100 4.3 4.7 4.9■LL(1)分析方法相关知识总结1、消除文法中的左递归或提取左因子；（1）简单直接左递归的消除A →βA’A →Aα| β→A’ →αA’| ε（2）将文法G：A→αβ|αγ提取左因子。

编译原理复习《编译原理》第⼀章：绪论1.翻译器：把⼀种语⾔变换到另外⼀种语⾔的软件。

这两种语⾔分别称为源语⾔和⽬标语⾔。

2.编译器：⼀种翻译器，它的⽬标语⾔⽐源语⾔低级。

3.典型的编译器可以划分成6个逻辑阶段：词法分析，语法分析，语义分析，中间代码⽣成，代码优化，代码⽣成。

4.按照对⽬标机器的依赖性，把编译过程分成前端（依赖于源语⾔，独⽴于⽬标机器）和后端（依赖于⽬标机器，独⽴于源语⾔,只与中间语⾔有关（从中间代码⽣成⽬标代码））。

5.前端包括：词法分析，语法分析，语义分析，中间代码⽣成。

6.后端包括：代码优化，代码⽣成。

7.解释器：不同于编译器的另⼀类语⾔处理器，直接执⾏源程序所指定的运算。

解释器的执⾏效率⽐编译器低，因为解释器⽆法解开循环。

8.遍：编译的⼏个阶段常⽤⼀遍（pass）扫描实现，⼀遍扫描包括读⼀个输⼊⽂件和写⼀个输出⽂件。

《编译原理》第⼆章：词法分析⼀些概念：1.词法单元：⼜称单词，是编程语⾔中合法的字符串。

2.词法记号：满⾜某种规则的词法单元，采⽤同⼀种记法——词法记号。

该规则称为模式。

3.模式：描述词法单元与词法记号对应关系的规则。

是描述源程序中某个记号的词法单元集合的规则。

4.字母表：符号的有限集合，例：∑={0,1}串：符号的有穷序列，例：0110,ε语⾔：字母表上的⼀个串集{ε,0,00,000,…},{ε},?正规式（运算符的优先级：*>连接运算>|）N F A是这样⼀个数学模型，包括1)状态集合S2)输⼊字母表∑3)转换函数m o v e:S?(∑?{ε})→P(S)4)唯⼀的初态s∈S5)终态集合F?SD F A是这样⼀个数学模型，包括1)状态集合S2)输⼊字母表∑3)转换函数m o v e:S?∑→S4)唯⼀的初态s∈S5)终态集合F?S第三章语法分析3.1 上下⽂⽆关⽂法上下⽂⽆关⽂法是四元组（V T , V N, S , P ）1) V T: 终结符集合(⾮空有限集合，记号名是其同义词)2) V N: ⾮终结符集合（⾮空有限集合）3) S : 开始符号4) P : 产⽣式集合，产⽣式形式 : A →α上下⽂⽆关⽂法没有强制的顺序关系。

编译原理复习《编译原理》复习README来源⽹络&书本&PPT整理截取了⽼师课上讲解or布置的题⽬⼀些题⽬懒得贴答案了，写了些注意事项第1 章引论运⾏编译程序的计算机：宿主机运⾏编译程序所产⽣的⽬标代码的计算机：⽬标机第1 题解释下列术语：（1）编译程序：如果源语⾔为⾼级语⾔，⽬标语⾔为某台计算机上的汇编语⾔或机器语⾔，则此翻译程序称为编译程序。

（2）源程序：源语⾔编写的程序称为源程序。

（3）⽬标程序：⽬标语⾔书写的程序称为⽬标程序。

（4）编译程序的前端：它由这样⼀些阶段组成：这些阶段的⼯作主要依赖于源语⾔⽽与⽬标机⽆关。

通常前端包括词法分析、语法分析、语义分析和中间代码⽣成这些阶段，某些优化⼯作也可在前端做，也包括与前端每个阶段相关的出错处理⼯作和符号表管理等⼯作。

（5）后端：指那些依赖于⽬标机⽽⼀般不依赖源语⾔，只与中间代码有关的那些阶段，即⽬标代码⽣成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语⾔程序从头到尾扫视并完成规定任务的过程。

第2 题⼀个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

(区别编译程序的六个阶段)答案：⼀个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码⽣成程序、中间代码优化程序、⽬标代码⽣成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输⼈源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进⾏语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码⽣成程序：按照语义规则，将语法分析程序分析出的语法单位转换成⼀定形式的中间语⾔代码，如三元式或四元式。

中间代码优化程序：为了产⽣⾼质量的⽬标代码，对中间代码进⾏等价变换处理。

教材资料授课顺序：1教学目的：正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任务；熟悉编译程序总框；了解编译程序的生成过程和构造工具。

教学重点与难点：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。

授课学时：2学时教学方式：多媒体讲授教学内容：第一章引论1.1什么是编译程序一、基本概念1、翻译程序：是指这样的一种程序，它能够把一种语言程序(源语言程序)转换成另一种功能等价的语言程序(目标语言程序)。

2、编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。

通常是一次性翻译方式。

如TC等高级语言编译程序。

3、解释程序也是一种翻译程序，它与编译程序的区别：立即执行源程序，通常是逐句翻译执行。

如BASIC、SQL、JA V A的BYTECODE解释程序等。

二、高级语言程序的处理过程高级程序设计语言程序的典型处理过程如下图所示：1.2编译过程和编译程序结构一、编译过程的阶段划分一般编译程序的工作过程按阶段进行，每个阶段将源程序从一种表示形式转换成另一种表示形式。

典型的阶段划分方法是将整个编译过程分为如下六个阶段：1、词法分析：任务：对构成源程序的字符串进行扫描和分解，识别出单词(如标识符等)符号。

输入：源程序输出：单词符号序列例子：有待分析源程序：main(){int x=10,y;}词法分析后的输出：1）保留字：main2）界符：左圆括号(3）界符：右圆括号)4）界符：左大括号{5)保留字：int6)标识符：x7)运算符：=8)常数：10 ，界符：，9)标识符：y10)界符：；11）界符：右大括号}2、语法分析任务：根据语言的语法规则对单词符号串(符号序列)进行语法分析，识别出各类语法短语(可表示成语法树的语法单位)，判断输入串在语法上是否正确。

输入：单词序列输出：语法分析后的单词序列3、语义分析任务：按语义规则对语法分析器归约出的语法单位进行语义分析，审查有无语义错误，为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理。

一、问答题（共25分）1．什么是翻译程序？什么是编译程序？（4分）2．简述编译过程各阶段的主要任务。

（5分）3．什么是上下文无关文法？（3分）4．什么是语法制导翻译法? （3分）5．写出下列状态转换图对应的词法分析程序。

（5分）字母或数字6．写出下面表达式的逆波兰表示和四元式序列（5分）–(A-B)/D*(C/D+E)二、构造正规式1(0|1)*101相应的DFA.（共15分）三、语法分析题（50分）1．简述确定的和不确定的自顶向下语法分析的基本思想。

（10分）2．已知文法G(P)：（10分）P→begin d；X endX→d；X|sYY→；sY|ε（1）画出句型begin d；s；s Y end的语法树（2）写出该句型的短语、直接短语、句柄。

3．设文法G(S)：（30分）S→SaB | bBA→SaB→Ac（1）将此文法改造为LL(1)文法。

（2）构造各非终结符的First集和Follow集。

（3）为改造后的文法构造递归下降分析程序。

四、语义分析（10分）已知下列文法及其对应的语义动作，采用自下而上的翻译过程，分析当输入串是aacbb时，其输出是什么，写出分析过程。

1. A→aB { print “1”}2. A→c { print “10” }3. B→Ab { print “100”}一、问答题：1． 将一种语言翻译成另外一种语言的程序成为翻译程序。

将高级语言翻译成低级语言的程序称为编译程序。

2． 分为词法分析、语法分析、中间代码生成、代码优化、目标代码生成几个阶段（任务略） 3． 由一组终结符号，一组非终结符号、一个开始符号、一组产生式构成。

其中每个产生式形如：A →β，A 是非终结符，β是由终结符和非终结符构成的符号串。

4． 根据每个产生式所对应的语义子程序进行翻译的办法。

5．If （IsLetter （）） BeginWhile (IsLetter() or IsDigit())Begin Concat();GetChar();EndRetract();Code:=Reserve(); If (code=0)Begin Value:=InsertId(strToken);return ($ID,value);End Else return (code,-); end6．答：–(A-B)/D*(C/D+E) 逆波兰式：AB-@D/CD/E+*四元式序列： (-,A,B,T1) (-,T1,_,T2) (/,T2,D,T3) (/,C,D,T4) (+,T4,E,T5) (*,T3,T5,T6)二、解：确定化重新命名，令AB 为B 、AC 为C 、ABY 为DDFA ： 1三、1．（1）确定的自顶向下语法分析的基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪个产生式替换相应的非终结符往下推导，构造分析树。

编译原理复习资料一、填空题.1.编译程序是一种程序，能够将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，它们在逻辑上等价，完成相同的工作。

2.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是_二义性的__。

3.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号，并以__单词符号或单词符号表示的源程序_的形式输出。

4.编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、和代码优化目标代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是表格管理和出错处理。

5.目前，语法分析方法有两大类，分别为自上向下的分析方法和__自下而上_分析方法。

自上而下的分析方法是从___文法的开始符号__出发，根据文法规则正向推导出给定句子的方法。

6.属性文法是编译技术中用来说明程序设计语言的___语义__的工具。

7.若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为 ____编译程序___。

8.扫描器（程序）的任务是从_字符串__中识别出一个个_单词符号_。

9.一个LR分析器包括三部分：总控程序、_分析表_和分析栈。

10.自顶向下的语法分析方法的基本思想是：从文法的_开始符号_出发，根据给定的输入串并按照文法的产生式一步一步的向下进行__正向推导_，试图推导出文法的给力句子__，使之与给定的输入串匹配。

11.按Chomsky分类法，文法被分成___4（0~3型文法）__类。

12.局部优化是在__基本块___范围内进行的一种优化。

13.编译程序是一种＿翻译＿程序，它将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，源程序和目标程序在逻辑上等价，完成相同的工作。

14.编译程序与解释程序的根本区别为__解释程序在执行中不产生目标程序_。

15.语法分析的任务是识别给定的终结符号串是否为给定文法的___句子__。

编译原理总复习总复习⼀、基本概念：1、请简单解释编译程序的概念。

答：编译程序是现代计算机系统的基本组成部分之⼀。

简⽽⾔之, 编译程序就是⼀种语⾔翻译程序。

所谓翻译程序，是指这样⼀个程序，它能将⾼级程序设计语⾔程序翻译成逻辑上等价的低级语⾔(汇编语⾔,机器语⾔) 程序。

编译程序⼀般由词法分析程序、语法分析程序、语义分析程序、中间代码⽣成程序、⽬标代码⽣成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。

2、请解释编译程序的前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？(10分)答：编译程序的前端只依赖于源语⾔，由⼏乎独⽴于⽬标机器的阶段或阶段的⼀部分组成。

编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码⽣成程序及相关的表格管理程序和出错处理程序。

编译程序的后端是指编译器中依赖于⽬标机器的部分,它们⼀般独⽴于源语⾔，⽽与中间代码有关。

通常包括⽬标代码⽣成程序、代码优化程序以及相关的表格管理程序和出错处理程序。

3、语⾔的语法描述⽅法有其三，请列举出来。

答：⽤⾃然语⾔描述语⾔的语法，⽤语法图描述语⾔的语法和⽤巴科斯-瑙尔范式及扩充的巴科斯-瑙尔范式(EBNF)两种形式给出语⾔的语法描述。

答：根据Chomcky⽂法的定义，该⽂法是2类⽂法，即上下⽂⽆关⽂法。

4、请写出Chomcky关于⽂法的定义。

答：Chomcky⽂法的定义：⽂法G定义为四元组,记为:G=(V N,V T,P,S)其中：V N—⾮空有限的⾮终结符号集V T—⾮空有限的终结符号集P —产⽣式集S —开始符号/识别符号5、已知⽂法：（20分）E→X|E+XX→Y|X*YY→（E）|i请判定该⽂法是那类⽂法？5、简单说明词法分析程序的主要任务。

答：词法分析程序是编译程序的⼀个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。

6、请简单介绍确定的有穷⾃动机。

答：确定的有穷⾃动机也称有限⾃动机，它是作为⼀种识别装置，它能准确地识别正规集，即识别正规⽂法所定义的语⾔和正规式所表⽰的集合。