下载文档原格式
(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)*。
编译原理复习重点含答案编译原理复习重点编译原理是计算机科学中的一门重要课程，它研究的是如何将高级语言程序转化为机器语言的过程。
在编译原理的学习中，我们需要掌握一些重要的概念和技术，以便能够理解和应用编译器的工作原理。
本文将重点介绍编译原理的几个重要主题，并提供相应的答案供参考。
一、词法分析词法分析是编译器的第一个阶段，它的任务是将输入的字符序列划分为一个个有意义的词素（token）。
词法分析器通常使用有限自动机（DFA）来实现，其工作原理是将输入字符序列逐个读入，并根据事先定义好的词法规则进行匹配和识别。
常见的词法单元包括关键字、标识符、常量、运算符等。
常见的词法规则包括：1. 关键字：例如if、while、for等。
2. 标识符：由字母、数字和下划线组成，且以字母或下划线开头。
3. 常量：包括整数常量、浮点数常量、字符常量和字符串常量等。
4. 运算符：例如加法运算符+、减法运算符-等。
5. 分隔符：例如逗号、分号等。
词法分析的结果是一个个词法单元，每个词法单元包含一个词素和对应的词法单元类型。
例如，对于输入程序"int a = 10;"，词法分析的结果可能是[("int", "关键字"), ("a", "标识符"), ("=", "运算符"), ("10", "整数常量"), (";", "分隔符")]。
二、语法分析语法分析是编译器的第二个阶段，它的任务是将词法分析器输出的词法单元序列转化为抽象语法树（AST）。
语法分析器通常使用上下文无关文法（CFG）来描述语言的语法结构，并使用递归下降、LL(1)分析、LR分析等算法进行分析。
常见的语法规则包括：1. 表达式：例如算术表达式、布尔表达式等。
第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）文法。
编译原理期末总结复习编译原理期末总结复习篇一：一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。
将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。
2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S）–其中Vn表示非终结符号– Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ– S是开始符号，–P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*)3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。
确定整个输入串是否构成语法上正确的程序。
4.局部优化有哪些常用的技术？答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量）5．编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。
每个阶段把源程序从一种表示变换成另一种表示。
6. 什么是文法？答：文法是描述语言的语法结构的形式规则。
是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。
7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。
8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：逐个读入源程序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号—滤掉空格，跳过注释、换行符—追踪换行标志，指出源程序出错的行列位置—宏展开，……10.什么是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。
编译原理总复习总复习■第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.编译程序：把高级语言程序翻译成等价的低级语言程序4.解释执行方式：解释程序，逐个语句地模拟执行翻译执行方式：翻译程序，把程序设计语言程序翻译成等价的目标程序5.计算机程序的编译过程类似，一般分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成词法分析的任务：扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等）语法分析是：在词法分析的基础上的，语法分析不考虑语义。
语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。
语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。
所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序编译程序结构包括五个基本功能模块和两个辅助模块6.编译划分成前端和后端。
编译前端的工作包括词法分析、语法分析、语义分析。
编译前端只依赖于源程序，独立于目标计算机。
前端进行分析编译后端的工作主要是目标代码的生成和优化后端进行综合。
独立于源程序，完全依赖于目标机器和中间代码。
把编译程序分为前端和后端的优点是：可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。
7.汇编器把汇编语言代码翻译成一个特定的机器指令序列第二章1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，X n，2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20 A0 ={ε}3.重写规则，简称规则。
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。
语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。
任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。
任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
编译原理复习资料1、某操作系统下合法的文件名为：device:name.extension，其中第一部分(device:)和第三部分(.extension )可缺省，若device, name和extension都是字母串，长度不限，但至少为1,画出识别这种文件名的DFA。
用标记d表示任意字母。
d d图1接受文件名的DFA2、用两个不同最左推导来说明下面的文法是二义的。
S A S | bA S A | a答：句型aSAS的两个不同最左推导如下：S AS aS aAS aSASS AS SASASAS aSAS3、证明下面的文法S S A | AA a不是LL(1)文法，但是SLR(1)文法，并画出SLR(1)分析表。
答：该文法的第一个产生式表现出直接左递归，因此该文法不是LL(1)。
接受该文法的活前缀的DFA见下面右边；Follow( S) = {$}，Follow( S) = {$, a}，Follow( A)SLR(1)的。
5、下面是int i, j, k这样的类型声明的两种不同语法:T int | real TL L , id | id L如果用LL(1)分析方法，应该选择哪个文法？如果用某种简要说明理由。
答：对于LL(1)分析方法，两个文法都不合适，左边的文法是左递归的，右边文法有公共左因子。
修改右边文法来适应LL(1)分析的要求，相对来说比较容易一些，因为只要提公共左因子。
对于LR的各种分析方法，两个文法都适用，但是采用左边的文法更好一些。
用左边的文法时，分析器一边扫描一边归约，占用分析栈的空间较少。
而用右边的文法时，分析器要把所有的标识符都移进栈后才进行归约，因此使用较多的分析栈空间。
(结合语法制导的翻译，采用左边的文法还有好处：便于确定T的类型属性在栈中的位置。
) 6、在C语言中，3++和(id + id )++这样的表达式被编译时，编译器都会报告如下的错误：in valid lvalue in in creme nt说明左值不能为数值或表达式。
现有如下简化的C语言表达式文法： E E + E | (E ) | E ++ | id | num请写一个语法制导定义或翻译方案，检查++的运算对象是否合法。
答：给非终结符 E 一个综合属性v,其值可取lvalue或rvalue，分别表示E是左值标识符和右值表达式，那么语法制导定义如下(无输出则表示无错) ：E id E.v := lvalueE num E.v := rvalueE E+T | TT num.num | num给出一个语法制导定义以确定每个子表达式的类型int/real 。
答：E E1+T { if ( E1.type=real or T.type=real )4、用SLR(1)文法能定义的语言集合、定义的语言集合之间有什么关系？答：用SLR⑴文法能定义的语言集合用LR(1)文法能定义的语言集合和用LALR(1)文法能用LALR(1)文法能定义的语言集合，用LALR⑴文法能定义的语言集合用LR(1)文法能定义的语言集合。
int | realid , L | idLR分析方法，选择哪个文法更好?E EE E i + E2 E ( E i ) E E i ++ E.v := rvalueE.v := E i.vif E i.v = rvalue then printf(E.v := rvaluein valid lvalue in in creme nt ”);7、then E.type=real else E.type=integer } E T { E.type = T.type;}T num .num {T.type = real;}T num {T.type = integer;}8、把下列 C 语言程序的可执行语句翻译为：main(){int i; int a[10];while (i<=10) a[i] = 0; }(a) 三地址代码(b) 后缀式答：(a) L0: if i<=10 goto L1goto L2L1: a[i]:=0goto L0L2:(b) 后缀式：i 10 <= a[i] 0 assign while9、试构造下面的程序的流图，并找出其中所有回边及循环。
read Px := 1 c := P * P if c < 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10x := x + 2 B := B + x write B if B < 100 goto L2 halt L2: x := x + 1goto L1答：程序的流图如下10、对本题中所示的流图，求出其各结点n 的控制结点集 D(n)、回边及循环(n o 为首结点) 答：各结点n 的控制结点集D(n)如下：D(n 0)= ={n o }D(n 1)= ={n 0, n 1}D(n 2)= ={n 0, n 1, n 2}D(n 3)= ={n 0, n 1, n 2, n 3} D(n 4)={n 0, n 1, n 2, n 4} D(n 5)= ={n 0, n 1, n 2, n 5}D(n 6)= ={n 0,n 1, n 2,n 5, n 6}D(n 7)={n 0, n 1, n 2, n 5, n 6, n 7}回边和循环：因为D(n 5) = {n o , n 1, n 2, n 5}，且n 5 -> n 2,所以n 5 -> n 2为一条回边。
根据它 求出的循环 Li = {n 2, n 5, n 3, n 4}。
因为 D(n 6)= {n 0, n 1, n 2, n5, n 6}，且 n 6 -> n 1，所以 n 6 -> n 1 为一条回边。
根据这条回边，求出的循环 L 2 = {n 6, n 1, n 5, n 3, n 4, n 2}。
11、考虑下面求矩阵 A B 成绩的程序片段：BEGINFOR i := 1 TO n DOFOR j := 1 TO n DOFOR k = 1 TO n DOc[i, j] := c[i, j] + A[i, k} * B[k, j]END (1)假定对数组A 、B 、C 采用静态存储分配，每个字占用 4个字节，存储器以字节为单位编址。
给出该程序的三地址代码序列。
(2) 构造该程序相应的流图。
(3) 删除流图中各基本块内的公共子表达式(4)指出流图中所有回边及其相应循环，并且进行循环优化。
答：(1)设数组元素按行存放，A、B C数组都是n*n的二维数组，各维的下界均为0，每个元素占一个字(4个字节)，则数组元素(如A[i, j])的地址计算公式为：D(A[i, j]) = addr(A) + ((i - 0) * n + (j - 0)) * 4=addr(A) + 4 * ( i * n + j )该程序的三地址代码序列被划分成基本块后如下：(105) if k > 门ecrta 130Bp (130) J := J + 1(131)goto 103(3 )仅基本块B7中有公共子表达式，删除公共子表达式后基本块B7变换成:(106)鼻：二I 半n(107)T：:二 J + J(108)T2 := addr (0(109)T t：= 4 + T”(110)T5:二T2[T t](111)T&:二几+ K(112)T r:二addr (A)(113)T e;= 4 * T6(114)T fi:二T?[t s] ill5) T, ：= K * n(116)Tg ：二Tg + J(117)T lQ:二吕療r(B)(118)T?:二4 * T9(119)T lt - T®[TJ(120)T12:= T3加T n(121)T； T5十T12(122)T JTJ :二(123)K ;= K + 1(124)goto 105(4)根据(2)的程序流图，每个结点的控制结点集如下:D(B i) = { B i }D(B2) = { B 1, B2 }D(B3) = { B 1, B 2, B 3 }D(B4) = { B 1, B 2, B 3, B 4 }D(B5) = { B 1, B 2, B 3, B 4, B 5 }D(B6) = { B 1, B 2, B 3, B 4, B 5, B 6 }D(B7) = { B 1, B 2, B 3, B 4, B 5, B 6, B 7 } D(B8) = { B 1, B 2, B 3, B 4, B 5, B 6, B 8 } D(B9) = { B 1, B 2, B 3, B 4, B 9 }根据回边B7 -> B 6 ，循环L i为：L1 = { B 7, B 6 }根据回边B8 -> B 4 ，循环L2为：L2 = { B 8, B 6, B 7, B 5, B 4 }根据回边B9 -> B2, 循环:L3为：L3 = { B 9, B 4, B 5, B 6, B 7 , B 8, B 3, B 2 } 经循环优化后三地址代码序列变为Sy. 4(2)经理度削弱后的梳圈(3)删除归纳变量：变换循环控制条件，删除归纳变量 I 后的流图显示在图12、试求出如下四元式程序中的循环并进行循环优化 I := 1 read J, K L: A := K * I B := J * IC := A * B write C I := I + 1 if I < 100 goto Lhalt 答：把本题的三地址代码划分成基本块并画出其程序流图显示在图 9.4(1)中 其中有三个基本块B1, B2, B3,有一条回边 B2 -> B2，相应的循环是｛B2｝。
I 1Tead J, KE ;= J * [C - * 8WLL lU €I ：二 I + 1i£ I < 各口丄口 Lhalt 国9. 4(1〕程序毓国 (1 )代码外提：由于循环中没有不变运算，故不做此项优化 (2)强度削弱: B2中A 和B都是 I 的归纳变量。
优化结果显示在图 9.4(2)中。
h 丹】t 9.4(3)中A 用静态分配存储单元，且下届为 0；/* 置初值*/4/* 第一个for 语句*/T 2[T 1] := true i := i + 1图9.4(3)删除归纳变量的程序流图 13、下面是应用筛法求 2到N 之间素数的程序: beginread N; for i := 2 to N do A[i] := true; /*置初值*/ 表幕乘*/ for i := 2 to N**0.5 do/*运算符**代T 2 := addr(A) T 1:= 2 * T 1 /* 数组A 的基地址*/the n/*i false/*j 可被i 除尽*/endif A[i]是一个素数*/for j := 2 * i to N by i doA[j]:=(1)试写出其四元式中间代码，假设对数组 (2 )作出流图并求出其中的循环； (3 )进行代码外提；(4)进行强度削弱和删除归纳变量；答：采用字节地址，两个字节作为一个机器字。
