编译原理复习整理

1、文档编码 : CB8H2L9R3M10 HX4T6I6N6T3 ZJ5T2U4L6X9学习资料收集于网络,仅供参考1、给出下面语言的相应文法； L1=a nb nc i|n1,i 0 从 n,i 的不同取值来把 L1 分成两部分： 前半部分是 anbn：AaAb|ab 后半部分是 ci：BBc| 所以整个文法 G1S 可以写为： G1S:SAB ； AaAb|ab；BcB| 3、构造一个 DFA,它接受（要求：先将正规式转化为学习资料=a,b 上全部包含 ab 的字符串；NFA,再将 NFA 确定化,最小化）学习资料收集于网络,仅供参考4、对下面的文法 G: ETEE +E| TFTT T|F

2、PFF *F | PE|a|b|（1）证明这个文法是 LL1 的；（2）构造它的推测分析表；1 FIRSTE=,a,b, FIRSTE=+, FIRSTT=,a,b, FIRSTT=,a,b, FIRSTF=,a,b, FIRSTF=*, FIRSTP=,a,b, FOLLOWE=#, FOLLOWE=#, FOLLOWT=+,# FOLLOWT=+,# FOLLOWF=,a,b,+,# FOLLOWF=,a,b,+,#2 考虑以下产生式 : E E |T T |F * F |P E | | a bFOLLOWP=*,a,b,+,# FIRST+E FIRST =+ = FIRST+E FOL

3、LOWE=+ #,=FIRSTT FIRST =,a,b, = FIRSTT FOLLOWT=,a,b,+,#=FIRST*FFIRST =* = FIRST*FFOLLOWF=* ,a,b,+,#=FIRSTE FIRSTa FIRSTb FIRST= 所以 , 该文法式 LL1 文法 . 3 + * a b # 学习资料学习资料收集于网络,仅供参考E E TE E TE E TE E TE E E E E ET T FT T FT T FT T FTT T T T T T T T T T T TF F PF F PF F PF F PFF F F * F F F F F F FP P E

4、P a P b P 5、考虑文法 : SAS|b ASA|a（1）列出这个文法的全部 LR0 项目；0. SS1.SS2. SAS 3.S ASA S4.aSAS5. Sb6. Sb7.ASA8. A9. ASA 10. A11. AaDFA；2 给出识别文法全部活前缀的1 S A 7 8 9 S 学习资料学习资料收集于网络,仅供参考0 a 10 11 A S 2 3 4 b 5 6 确定化：0,2,5,7,10 S A a b 1,2,5,7,8,102,3,5,7,10 11 6 1,2,5,7,8,102,5,7,8,10 2,3,5,7,9,10 11 6 2,3,5,7,10 2,4

5、,5,7,8,102,3,5,7,10 11 6 2,5,7,8,10 2,5,7,8,10 2,3,5,7,9,10 11 6 2,3,5,7,9,102,4,5,7,8,102,3,5,7,10 11 6 2,3,5,7,9,10 11 6 2,4,5,7,8,102,5,7,8,10 学习资料学习资料收集于网络,仅供参考11 6 A S b 3: SS5: AS A6: ASAAS S A a S A S SAASSA SAbSASAaASASbSASAaASASbAa S a A S b S A b a A 学习资料0: SS4: SA S7: SASS ASASSASAS A S b

6、SbSASASAASASbAaAaASA学习资料收集于网络,仅供参考 b a a b b a 1: Aa2: Sb DFA 6、设有文法： PP+Q|Q QQ*R|R RP|i （1）证明 Q*R+Q+Q 是它的一个句型；（ 3 分 P=P+Q=P+Q+Q=Q+Q+Q=Q*R+Q+Q （2）给出 Q*R+Q+Q 的全部短语,直接短语和句柄；4 分 短语 : Q*R,Q*R+Q,Q*R+Q+Q 直接短语 : Q*R 句柄 : Q*R（3）给出句子 +* 的最右推导； 4 分 （4）给出句子 +* 的最左推导； 4 分 7、设有文法： EE+T|T TT*F|F FE|i ET*F（1）证明 E+

7、T*F 是它的一个句型；（ 3 分EET（2）给出 E+T*F 的全部短语,直接短语和句柄；4 分 短语 : E+T*F, T*F, 直接短语 : T*F 句柄 : T*F（3）给出句子 +* 的最右推导； 4 分 学习资料学习资料收集于网络,仅供参考11、构造下面正规式相应的 DFA 10|1 *101 14、对下面的文法 G: Expr- Expr ExprExpr|Var ExprTail ExprTail- Expr|Varid VarTail VarTailExpr |（1）构造 LL1 分析表；（ 12 分）学习资料学习资料收集于网络,仅供参考（2）给出对句子 ididid 的分析

8、过程；（ 8 分）学习资料学习资料收集于网络,仅供参考16、已知文法 GS 为：S-a|T T-T,S|S 排除文法 GS中的左递归,得文法 G S；G S S a | | T T S TT , S T | 文法 G S是否为 LL1 的？如是,给出它的推测分析表；FIRSTS=a, FIRSTT=a, FIRSTT =, FOLLOWS=,# FOLLOWT= FOLLOWT = 推测分析表S Sa TS S T T, ST# aT TST,TSTSTT是 LL1 文法17、对下面的文法 G: S S a T | a T | a T T a T | a 1 排除该文法的左递归和提取左公因子；

9、 构造各非终结符的 FIRST 和 FOLLOW集合；学习资料学习资料收集于网络,仅供参考18、文法 GS及其 LR 分析表如下,请给出串baba#的分析过程；1 S DbB 2 D d 3 D 4 B a 5 B Bba 6 B LR 分析表学习资料学习资料收集于网络,仅供参考2、写出表达式 a=b*c+b*d 对应的逆波兰式、四元式序列和三元式序列；答：逆波兰式： abc*bd*+:= 四元式序列：三元式序列 : OP ARG1 ARG2 1 *, b , c , t1 1 * b, c 2 *, b , d , t2 2 * b, d 3 +, t1 , t2,t 3 3 + 1, 2

10、4 :=, t3 , / , a 4 := 3, a 学习资料学习资料收集于网络,仅供参考八、语义分析题1、将语句if A0 then while C0 do C:=C-D 翻译成四元式 答案： 100 j, B, 0, 104 103 j, -, -, 109 104 j, C, 0, 106 105 j, -, -, 109 106 -, C, D, T1 107 :=, T1, -, C 108 j, -, -, 104 109 2、写出下面语句经语法制导翻译后所生成的四元式代码序列；if xc do c:=c+1 else x:=x+5 学习资料学习资料收集于网络,仅供参考答案： 假设

11、初始为100,就四元式代码序列为xc 103 goto 109 104 M:=C+102 1 105 C:=M 106 goto 107 N:=X+5 108 X:=N 109 8、写出表达式 a+b*c-d对应的逆波兰式和三元式序列；答案：逆波兰式： abcd-*+ 三元式序列 : 1 OP ARG1 ARG2 - c d 2 * b 1 3 + a 2 学习资料学习资料收集于网络,仅供参考1编译程序是对高级语言程序的说明执行； 2一个有限状态自动机中,有且仅有一个唯独的终态； 3一个算符优先文法可能不存在算符优先函数与之对应； 4语法分析时必需先排除文法中的左递归； 5LR 分析法在自左至

12、右扫描输入串时就能发觉错误,但不能精确地指出出错地点； 6逆波兰表示法表示表达式时无须使用括号； 7静态数组的储备空间可以在编译时确定； 8进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用； 9两个正规集相等的必要条件是他们对应的正规式等价； 10一个语义子程序描述了一个文法所对应的翻译工作； 1. 一个上下文无关文法的开头符,可以是终结符或非终结符；2. 一个句型的直接短语是唯独的；（） （）3. 已经证明文法的二义性是可判定的；（）4. 每个基本块可用一个DAG表示；（）5. 每个过程的活动记录的体积在编译时可静态确定；6.2 型文法确定是3 型文法；（）7. 一

13、个句型确定句子； （ ）8. 算符优先分析法每次都是对句柄进行归约； 9. 接受三元式实现三地址代码时,不利于对中间代码进行优化；10. 编译过程中,语法分析器的任务是分析单词是怎样构成的； 11. 一个优先表确定存在相应的优先函数； 12. 目标代码生成时,应考虑如何充分利用运算机的寄存器的问题；13. 递归下降分析法是一种自下而上分析法； 14. 并不是每个文法都能改写成LL1 文法； 15. 每个基本块只有一个入口和一个出口； 16. 一个 LL1 文法确定是无二义的； 17. 逆波兰法表示的表达试亦称前缀式； 18. 目标代码生成时,应考虑如何充分利用运算机的寄存器的问题；学习资料学习

14、资料收集于网络,仅供参考19. 正规文法产生的语言都可以用上下文无关文法来描述； 20. 一个优先表确定存在相应的优先函数； 21.3 型文法确定是 2 型文法； 22. 假如一个文法存在某个句子对应两棵不同的语法树,就文法是二义性的； 1、简述编译程序的工作过程：编译程序的工作过程,是指从输入源程序开头到输出目标程序为止的整个过程,是特殊复杂的, 就其过程而言,一般可以划分为五个工作阶段：词法分析, 对构成源程序的字符串进行扫描和分解,识别出一个个的单词；语法分析,依据语言的语法规章, 把单词符号串分解成各类语法单位；语义分析与中间代码产生,即对各类语法单位, 分析其汉一并进行初步翻译；代码

15、优化,以期产生更高效的代码；目标代码生成,把中间代码变换成特定机器上的低级语言指令形式；2简述代码优化的目的和意义：代码优化是尽量生成“ 好” 的代码的编译阶段；也就是要对程序代码进行一种等价变换,在保证变换前后代码执行结果相同的前提下,尽量使目标程序运行时所需要的时间短,同时所占用的储备空间少；3、 简要说明语义分析的基本功能：确定类型、类型检查、语义处理和某些静态语义检查；1词法分析： 词法分析的主要任务是从左向右扫描每行源程序的符号,依据词法规章从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位,token ,送给语法分析程序；并转换成统一的内部表示3简述自下而上的分析方法；：

16、所谓自下而上分析法就是从输入串开头,逐步进行“归约 ”,直至归约到文法的开头符号；或者说从语法树的末端开头,步步向上“归约 ”,直到根节点；2LL1 文法： 如文法的任何两个产生式 A | 都中意下面两个条件：（1）FIRST FIRST = ；（ 2）如 * ,那么 FIRST FOLLOW A = ；我们把中意这两个条件的文法叫做 LL1 文法 ,其中的第一个 L 代表从左向右扫描输入,其次个 L 表示产生最左推导, 1 代表在准备分析器的每步动作时向前看一个输入符号；除了没有公共左因子外,LL1 文法仍有一些明显的性质,它不是二义的,也不含左递归；学习资料学习资料收集于网络,仅供参考3语

17、法树： 句子的树结构表示法称为语法树 语法分析树或语法推导树 ；给定文法 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 所产生的句子；4L

18、R0 分析器： 所谓 LR0 分析,是指从左至右扫描和自底向上的语法分析,且在分析的每一步, 只须依据分析栈当前已移进和归约出的全部文法符号,并至多再向前查看 0 个输入符号,就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成,从而也就可以确定当前所应实行的分析动作 是移进仍是按某一产生式进行归约等 ；5语言和文法： 文法就是语言结构的定义和描述,是有穷非空的产生式集合；文法 G 定义为四元组的形式：G=V N,V T,P,S其中： V N 是非空有穷集合,称为非终结符号集合；V T 是非空有穷集合,称为终结符号集合；P 是产生式的集合 非空 ；S 是开头符号 或识别符号 ；这里,

19、 V NV T=,S VN；V=VNVT,称为文法 G 的字母表,它是显现文法产生式中的一切符号的集合；文法 G 所描述的语言用 LG 表示,它由文法 G 所产生的全部句子组成,即LG=x| S *x ,其中 S为文法开头符号,且 x V T 简洁的说,文法描述的语言是该文法一切句子的集合；2. 二义性文法： 假如一个文法存在某个句子对应两棵不同的语法树,就称这个文法是二义性文法；6. 语法：一组规章,用它可形成和产生一组合式的程序；式规章； 12. 规范句型 -由规范推导所得到的句型；7. 文法 : 描述语言的语法结构的形15. 句柄：一个句型的最左直接短语；21. 语义：定义程序的意义的一

20、组规章；10. 短语：令 G是一个文法, S划文法的开头符号,假定 是文法 G的一个句型,假如有 S A且 A ,就称 是句型 相对非终结符A 的短语；1编译程序和高级语言有什么区分. 用汇编语言或高级语言编写的程序,必需先送入运算机,经过转换成用机器语言表示的 目标程序（这个过程即编译）,才能由运算机执行；执行转换过程的程序叫编译程序；汇编 程序是指没有编译过的汇编语言源文件；编译程序转换过的叫目标程序,也就是机器语言；学习资料学习资料收集于网络,仅供参考编译程序的工作情形有三种：汇编型、 说明型和编译型；汇编型编译程序用来将汇编语言编写的程序,依据一一对应的关系,转换成用机器语言表示的程序

21、；说明型编译程序将高级语言程序的一个语句,先说明成为一组机器语言的指令,然后马上执行,执行完了, 取下一组语句说明和执行,如此连续到完成一个程序止；用说明型编译程序,执行速度很慢, 但可以进行人和运算机的 对话 ,随时可以修改高级语言的程序；BASIC 语言就是说明型高级语言；编译型编译程序将级语言编写的程序,一次就会部翻译成机器语言表示的程序,而且过程进行很快,在过程中,不能进行人机对话修改；FORTRAN 语言就是编译型高级语言；1运算机执行用高级语言编写的程序主要有两种途径：_说明 _和_编译 _；2扫描器是 _词法分析器 _,它接受输入的_源程序 _,对源程序进行_词法分析 _并识别出一个个单词符号,其输出结果是单词符号,供语法分析器使用；3自上而下分析法接受_移进 _、归约、错误处理、_接受 _等四种操作；4一个 LR分析器包括两部分：一个总控程序 和_一张分析表 _；5后缀式 abc-/ 所代表的表达式是 _a/b-c _；6局部优化是在 _基本块 _范畴内进行的一种优化；2. 编译过程可分为（ 词法分析 ） ,（ 语法分析 ）,（ 语义分析与中间代码生成）,（ 优化）和（ 目标代码生成）五个阶段；3.