编译原理复习资料

(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)*。

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）文法。

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)工作过程中的每个阶段均采用了符号表管理器，出错处理器。