完整编译原理复习整理重点含答案,推荐文档

1、3NFA构造相应的任观式最小化NFA确定化,最小化a , b上所有包含ab的字符申1、给出下面语言的相应文法 从n, i的不同取值来把所以整个文法G1S可以写为nbnC|n> 1,i > 0L1分成两局部：前半局部是anbn： 2aAb|ab后半局部是ci: EHBc| £G1(S):SAB ; 2aAb|ab ; BcB| £IL(1.234L,2,3m,5, 时(1,2U,2i3(1.2(lFZf3f5r6>Ur Zf 5, 6(1.2,3,5,6( >2,3f5心!.lr2, 4,5,6)以,1.2. 5,6).分确定化4、对下面的文法G:Et

2、TE' E't+E| eTTFT'T'tT| eFt PF'F' t*F' e|Pt(E)|a|b|A(1) 证实这个文法是LL(1)的.(2) 构造它的预测分析表. FIRST(E)=(,a,b,A FIRST(E')=+,£ FIRST(T)=(,a,b,AFIRST(T')=(,a,b,气£ FIRST(F)=(,a,b?FIRST(F')=*,£ FIRST(P)=(,a,b,AFOLLOW(E)=#,)FOLLOW(E')=#,) FOLLOW(T)=+,),# FO

3、LLOW(T')=+,),# FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F')=(,a,b,A,+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2)考虑以下产生式：E e|T T| F *F |P (E)Ra|bfirst(+e) n first( £ )=+ n £ = 4 first(+e) n follow(E')=+ n #,)= 4 FIRST(T) n FIRST( £ )=(,a,b,A n £ =()FIRST(T) n FOLLOW(T')=(,a,b,A n +,),#=

4、() FIRST(*F') A FIRST( £ )=* n £ =()FIRST(*F') n FOLLOW(F')=* n (,a,b,A,+,),#=()FIRST(E) n FIRST(a) n FIRST(b) n FIRST(A)=() 所以,该文法式LL(1)文法.+*()abA#ee te 'E TE'E TE'E TE'E'eeEETT FTT FTT FTT FTT'TT TTT TT TT TTFF PFF PFF PFF PFF'FF *FFFFFFFPP (E)P aP

5、 bP A5、考虑文法：SAS|b AtSA|a (1)列出这个文法的所有 LR(0)工程.0. S S 1. S S 2. S AS 3. S A S4. S AS 5. S b6. s b 7.11. A aA SA8. A S A 9. A SA 10. A给出识别文法所有活前缀的 DFA.确定化:SAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,102,4,5,7,8,102,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,101162

6、,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,1011611444464444s A £ ss saAb s3:AAASSA sASbSAaA :-.X§SAASSJAA bs aAs >0:s s A AsAsJA b Absa s lssaassbs2:DFA6、 设有文法：PtP+Q|Q QtQ*R|RRt(P)|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的

7、所有短语,直接短语和句柄.(4分)短语：Q*R,Q*R+Q,Q*R+Q+Q 直接短语：Q*R 句柄：Q*R(3) 给出句子1+1 * 1的最右推导.(4分)(4) 给出句子1+1 * 1的最左推导.(4分)7、 设有文法：EtE+T|TTtT*F|FFt(E)|i(1) 证实E+T*F是它的一个句型.(3分)E E T E T*F(2) 给出E+T*F的所有短语,直接短语和句柄.(4分)短语：e+t*f, t*f,直接短语：t*f句柄:t*f(3) 给出句子i+i * 1的最右推导.(4分)11、构造下面正规式相应的DFA1(0|1)*101I10IIXA B, C(A, B?C B,C( B

8、,C,DB,C( B,C B,C,D B, C, E B, C, D(B, C3 E(B, C)(B, C, D, yB, C3 D, y(B, C, E( B, C, D)14、对下面的文法G:Exprt- ExprExpL (Expr)|Var ExprTail ExprTail - Expr| eVaid VarTail VarTail(Expr) | e(1)构造LL(1)分析表.(12分)(1)FIRST (Expr) = _ ? (> id FIRST(EsprTail)=L, E FIRST(Var) = id)FnST (VarTail ) = ( ( , E ：FOLL

9、OW(Expr)二W , ) FOLLOW(ExprTail)二H , ) FOLLOW (Var)=_.#,) FOI.LOW (VarTai 1)二_,#,)：,1:)tEwprIsprT"工 zprEzpr VarEyprTail(Expr)ExprTui LEacprTalErTai 1 "*£Vai* id二'二 _ LVarTailVarrail-»*£VarTail f (Eapr)VarlailE(2)给出对句子id id(id)的分析过程.(8分)步囊 符号槌输入宝idid(1 id)ExprTailVarid_ _i

10、d(id)= ExprVar ExprTailEsprTai1VarTftilid id. i# Varid VarTailExprTailVarTailExprTailExpr_id(id)EExprTai_ ExprEmExpr.ExprExprTailTar沃(id)E idC(idj) # id(id) UExpff ExprEpr-Var ExprTail10ExptLailVarTail id id (id)井膈id VarTail11心VAi'TailExprTailhExpr'：(id)-VarTail (Expr)13ExprTail)Expr(id)拌14E

11、xprTailh Expr(id)«ExprTExpr)IIExprTail? )Expiid)#16# ExprTail )Fx piT et i:arid：)#Var ExprTail17ExprTail )ExprTail VaiTailid id) #Var-id Vai-TailISExprlail >ExprTail VarTail)> #19ExprTail )ExprTail )#ExprTail )ExprTailEExprT&il22Ezp?JailExpmii£合析成为16、文法GS为：S->a |(T)T->T,S|S

12、 消除文法GS中的左递归,得文法G' S.G (S)S aB|(T)T STT ,ST | 文法G' S是否为LL(1)的假设是,给出它的预测分析表.FIRST(S)=a?,( FIRST(T)=a?,( FIRST(T )=(,FOLLOW(S)=),# FOLLOW(T)=) FOLLOW( T )=) 预测分析表aA(),#SSaP S AS (T)TT STT STT STTTT ,ST是LL(1)文法17、对下面的文法G:S S a T | a T | a T (1)消除该文法的左递归和提取左公因子；构造各非终结符的FIRST和FOLLOW集合;(1)(消除左递归2分

13、) 5 T aTSr | vary St vaTS I £ T t A.aT ' a a (提取左公因子2分) St aTSf | v S' v a TSf | £FIRST(S)=a, V； FIRSTG)=s FIRST(T)*FIRSim=z FOLLOW)湖 FOLLOW$)=# FOLLOW仃户房H FOLLOW)fv,18、文法G(S)及其LR分析表如下,请给出申baba#勺分析过程 S t DbB (2) D t d (3) D t e B t a (5) B t Bba B t eLR分析表ACTIONSOIQ步骚状态符号缁入串00#babs

14、#.102#DbMlDW#2024#Dbaba#:30245#Db-aba440246#DbBbat:502 67WbBbat024678#DbBoa#7 0246#DbB廿8 01#S陋acctot)as0E531E1acc23434r6r665成或6=7rl7asBe5c52、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列答：逆波兰式：abc*bd*+:=四兀式序列：三元式序列：OP ARG1 ARG2(*, b ,c , t 1)(1) (* b, c )(*, b ,d , t 2)(2) (* b , d )(+ , t1 ,t 2, t3)(3) (+ (1),

15、(2)(:=,t3 ,/ , a)(:=(3), a)八、语义分析题1、将语句if (A<0)(B>0) then while (C>0) do C:=C-D译成四元式答案：100 (j<, A, 0, 104)101 (j, -, -, 102)102 (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)1092、写出下面语句经语法制导译后所生成的四元式代码序列

16、if x<y then while e>c do c:=c+1 else x:=x+5答案：假设初始为100,那么四元式代码序列为100ifx<ygoto102101goto107102ife>cgoto104103goto109M:=C+1041105C:=M106goto102N:=X+1075108X:=N1098、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列答案：逆波兰式：(abcd-*+)三元式序歹0 :OPARG1ARG2-cd*b(1)+a1 .编译程序是对高级语言程序的解释执行.X2. 一个有限状态自动机中,有且仅有一个唯一的终态.?3. 一个

17、算符优先文法可能不存在算符优先函数与之对应.V 4. 语法分析时必须先消除文法中的左递归.必(V)5. LR分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点.6 .逆波兰表示法表示表达式时无须使用括号.V 7. 静态数组的存储空间可以在编译时确定.?8. 进行代码优化时应着重考虑循环的代码优化,这对提升目标代码的效率将起更大作用.9. 两个正规集相等的必要条件是他们对应的正规式等价.X10. 一个语义子程序描述了一个文法所对应的译工作.必1. 一个上下文无关文法的开始符,可以是终结符或非终结符. x 2, 一个句型的直接短语是唯一的.X 3, 已经证实文法的二义性是可判定的.

18、x 4, 每个根本块可用一个 DA#示.立5, 每个过程的活动记录的体积在编译时可静态确定.V 6.2型文法- -定是 3型文法.x 7. 一个句型一定句子.X 8. 算符优先分析法每次都是对句柄进行归约. x 9. 采用三元式实现三地址代码时,不利于对中间代码进行优化.立 10. 编译过程中,语法分析器的任务是分析单词是怎样构成的. X 11. 一个优先表一定存在相应的优先函数.V 12. 目标代码生成时,应考虑如何充分利用计算机的存放器的问题. V 13. 递归下降分析法是一种自下而上分析法.x 14. 并不是每个文法都能改写成LL1文法./ 15. 每个根本块只有一个入口和一个出口. V

19、 16. 一个LL1文法一定是无二义的.V 17. 逆波兰法表示的表达试亦称前缀式. X 18. 目标代码生成时,应考虑如何充分利用计算机的存放器的问题. V 19, 正规文法产生的语言都可以用上下文无关文法来描述. V 20. 一个优先表一定存在相应的优先函数. V 21.3型文法一定是2型文法.V 22.如果一个文法存在某个句子对应两棵不同的语法树,那么文法是二义性的.V1、 简述编译程序的工作过程：编译程序的工作过程,是指从输入源程序开始到输出目标程序为止的整个过程,是非常复杂的,就其过程而言,一般可以划分为五个工作阶段：词法分析,对构成源程序的字符串进行扫描和分解,识别出一个个的单词；

20、语法分析,根据语言的语法规那么,把单词符号串分解成各类语法单位；语义分析与中间代码产生,即对各类语法单位,分析其汉一并进行初步译；代码优化,以期产生更高效的代码；目标代码生成,把中间代码变换成特定机器上的低级语言指令形式.2、 简述代码优化的目的和意义：代码优化是尽量生成 好的代码的编译阶段.也就是要对程序代码进行一种等价变换,在保证变换前后代码执行结果相同的前提下,尽量使目标程序运行时所需要的时间短,同时所占用的存储空间少.3、 简要说明语义分析的根本功能 ：确定类型、类型检查、语义处理和某些静态语义检查. 1 .词法分析：词法分析的主要任务是从左向右扫描每行源程序的符号,根据词法规那么从构

21、成源程序的字符串中识别出一个个具有独立意义的最小语法单位,并转换成统一的内部表示(token),送给语法分析程序.3.简述自下而上的分析方法.：所谓自下而上分析法就是从输入串开始,逐步进行归约,直至归约到文法的开始符号；或者说从语法树的末端开始,步步向上归约,直到根节点.2. LL(1)文法：假设文法的任何两个产生式 A |都满足下面两个条件：(1) FIRST()FIRST( ) = ; (2)假设 * ,那么FIRST( ) FOLLOW( A )=.我们把满足这两个 条件的文法叫做LL(1)文法,其中的第一个L代表从左向右扫描输入,第二个L表示产生最左推导,1代表在决定分析器的每步动作时

22、向前看一个输入符号.除了没有公共左因子外,LL(1)文法还有一些明显的性质,它不是二义的,也不含左递归.3. 语法树：句子的树结构表示法称为语法树(语法分析树或语法推导树).给定文法G=(Vn,Vt, P, S),对于G的任何句型都能构造与之关联的语法树.这棵树具有以下特征：(1)根节点的标记是开始符号 S.(2)每个节点的标记都是 V中的一个符号.(3)假设一棵子树的根节点 为A ,且其所有直接子孙的标记从左向右的排列次序为AiA2A R,那么A AiA2 A R一定是P中的一条产生式.(4)假设一标记为A的节点至少有一个除它以外的子孙,贝U A Vn.(5) 假设树的所有叶节点上的标记从左

23、到右排列为字符串w,那么w是文法G的句型；假设w中仅含终结符号,那么 w为文法G所产生的句子.4. LR(0)分析器：所谓LR(0)分析,是指从左至右扫描和自底向上的语法分析,且在分析的每一步,只须根据分析栈当前已移进和归约出的全部文法符号,并至多再向前查看0个输入符号,就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成,从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等 ).5. 语言和文法：文法就是语言结构的定义和描述,是有穷非空的产生式集合.文法 G定义 为四元组的形式：G=(Vn , Vt, P, S)其中：Vn是非空有穷集合,称为非终结符号集合；V

24、t是非空有穷集合,称为终结符号集合；P是产生式的集合(非空);S是开始符号(或识别符号).这里,VnAV t= , S Vn.V=Vn U Vt,称为文法 G的字母表,它是出现文法产生 式中的一切符号的集合.文法G所描述的语言用L(G)表示,它由文法 G所产生的全部句子组成,即L(G)=x| S *x,其中S为文法开始符号,且 x VT 简单的说,文法描述的语言是该文法一切句子的集合.2. 二义性文法：如果一个文法存在某个句子对应两棵不同的语法树,那么称这个文法是二义性文法.6. 语法：一组规那么,用它可形成和产生一组合式的程序.7.文法：描述语言的语法结构的形式规那么.12.标准句型-由标准

25、推导所得到的句型.15.句柄：一个句型的最左直接短语.21.语义：定义程序的意义的一组规那么.10.短语：令G是一个文法,S划文法的开始符号,假定 a 6 a是文法G的一个句型,如果 有 Sa AS且 A6 ,那么称3是句型a 6 6相对非终结符A 的短语.1. 编译程序和高级语言有什么区别用汇编语言或高级语言编写的程序,必须先送入计算机,经过转换成用机器语言表示的 目标程序这个过程即编译,才能由计算机执行.执行转换过程的程序叫编译程序.汇编 程序是指没有编译过的汇编语言源文件.编译程序转换过的叫目标程序,也就是机器语言.编译程序的工作情况有三种：汇编型、解释型和编译型.汇编型编译程序用来将汇

26、编语言编写的程序,根据一一对应的关系,转换成用机器语言表示的程序. 解释型编译程序将高级语言程序的一个语句,先解释成为一组机器语言的指令,然后立即执行,执行完了,取下一组语句解释和执行,如此继续到完成一个程序止.用解释型编译程序, 执行速度很慢,但可以进行人和计算机的"对话",随时可以修改高级语言的程序.BASIC语言就是解释型高级语言. 编译型编译程序将级语言编写的程序,一次就会部译成机器语言表示的程序,而且过程进行很快,在过程中,不能进行人机对话修改.FORTRAN语言就是编译型高级语言.1 .计算机执行用高级语言编写的程序主要有两种途径：解释 和 编译 .2 .扫描器

27、是 词法分析器,它接受输入的源程序,对源程序进行词法分析并识别出一个个单词符号,其输出结果是单词符号,供语法分析器使用.3. 自上而下分析法采用移进、归约、错误处理、接受 等四种操作.WMHaMHWaWMII4. 一个LR分析器包括两局部：一个 总控程序和一张分析表 .5. 后缀式abc-/所代表的表达式是a/b-c.6 .局部优化是在根本块范围内进行的一种优化.2. 编译过程可分为词法分析,语法分析,语义分析与中间代码生成,优化和目标代码生成五个阶段.3. 如果一个文法存在某个句子对应两棵不同的语法树,那么称这个文法是二义性的.5. 语法分析器的输入是单词符号,其输出是 语法单位 .6. 扫描器的任务是从源程序中识别出一个个单词符号.13. 根据优化所涉及的程序范围,可将优化分成为局部优化,循环优化,全局优化三个级别.14. 语法分析的方法大致可分为两类,一类是自上而下分析法,另一类是自下而上分析法.15. 预测分析程序是使用一张分析表和一个符号栈进行联合限制的.17. 一张转换图只包含有限个状态 ,其中有一个被认为是初态；而且实际上至少要有一个 终态.1