华南农业大学编译基础原理汇总题库.doc

^` 华南农业大学期末考试题库（含参考答案） 考试科目：　编译原理 　　 考试时间：　120　分钟 学号 姓名 年级专业 题号 一 二 三 四 五 总分 得分 评阅人 得分 一、本题共6小题，每小题5分，共30分。 1、写出下面右线性正规文法所对应的正规式。 文法所对应的正规式为： a(b|aa)*b S → aD D → bD | aA | b A → aD 2、给出下面语言集合的上下文无关文法。（2010 2014） 文法： S → aS | D D → aDb | ab L1={ anbm | n≥m≥1} 2、为正规集L2={anbm ck | n≥1,m≥1,k≥1}构造一右线性正规文法。（2010） S → aS | aA A → bA | bB B → cB | c 3、按照编译过程的5个阶段得到编译程序的逻辑结构框图如下： 4、简述编译过程的5个阶段及各阶段的主要功能。（多年必考） 编译过程即编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串组合成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其含义并进行初步翻译；④代码优化，对代码进行等价变换，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。 5、“含有优化部分的编译程序的执行效率更高。”这句话对吗？为什么？。 这句话是错的。优化不是编译程序必须的一个部分，含有优化的编译程序功能更强、算法更复杂，因而开发效率和执行效率低些，但得到的目标代码的效率通常更高。 6、简述语法制导翻译技术的基本思想。（2013） 语法制导翻译技术的基本思想是，对文法中的每个产生式都附加一个语义动作或语义子程序，在执行语法分析的过程中，当运用该产生式进行推导或归约时，就执行相应的语义动作，从而完成预定的翻译工作。 7、简述算符优先分析方法。（2013） 算符优先分析方法是一种移进-归约的语法分析方法，这种分析方法首先要根据文法来确定终结符之间的优先关系，然后借助这种优先关系，在移进-归约过程中通过比较相邻终结符之间的优先关系来确定句型的可归约串（最左素短语）并进行归约。它不是一种规范归约的分析方法，只适用于分析算符优先文法。 8、简要说明翻译程序与编译程序的异同、编译程序与解释程序的异同。（2011） 翻译程序是将一种语言程序（源）转换成另一种语言程序（目标），对源语言和目标语言没特别要求，编译程序特指将高级语言的源程序转换成低级语言程序，是翻译程序的一种。 编译程序与解释程序都是将高级语言翻译成低级语言，但编译程序要先编译生成目标代码、再执行目标代码，解释程序边转换边执行，不生成目标代码。 9、判断下图FA是NFA还是DFA，并用正规式来描述它所识别的语言。 是DFA(1分)，对应的正规式为： 1*01*(01*01*)* (4分) 1 A B 0 0 1 10、判断下图FA是NFA还是DFA，并用正规式来描述它所识别的语言。（2011） 0 A B 0,1 0 是NFA,因为A状态输入0可以转换到A或B两状态。 等价正规式：0*(0|1)(00*(0|1))* 11、有文法及其语义子程序如下： S →T { print(T.h) } T→ T 1*E { T.h= T 1.h +E.h } T→ E { T.h=E.h } E→（T） {E.h= T.h} E→ a { E.h= 1 } 采用移进归约的分析方法，当分析器的输入为(a)*(a*a) 时，画出其语法树（可以带注释、也可以不带注释），并求输出的结果。 语法树（略），输入为(a)*(a*a) 时，输出的结果为：3 12（2014）、空心圆柱体的表面积计算公式如 S=2*3.1416*(R+r)*(R-r)+ 2*3.1416*(R+r)*h 采用LR语法制导翻译技术生成相应的三地址代码，然后运用DAG对其进行局部优化，试写出能生成最优目标代码的优化后的三地址代码序列。 可以采用合并已知量、删除公共子表达式、删除无用赋值、交换语句位置等优化方法，得到三地址代码序列如下： (1) T1=R+r (2) T2=6.2832*T1 (3) T3=T2*h (4) T4=R-r (5) T5=T2*T4 (6) S=T5+T3 13、试求表达式A+B*(-C)+B/(-C)对应的后缀式和三地址代码。（2011） 后缀式：ABC-*+BC-/+ 三地址代码：T1=-C T2=B*T1 T3=A+T2 T4=-C T5=B/T4 T6=T3+T5 14、考虑如下的三地址语句序列：（2011） L1: read C; A=0; B=1; L2: A=A+B; if B≥C goto L3; B=B+1; goto L2; goto L1; L3: write A; halt; B1 B2 B3 多余的语句，删去 B4 (1). 将该代码序列划分成基本块，并给每个基本块一个序号； (2). 画出该代码序列的流图，每个基本块用(1)的序号表示； (3). 若有循环，列出构成循环的节点(基本块)。（10分） (1).如图分成四个基本块B1、B2、B3、B4 B1 (2).流图： B4 B3 B2 (3).构成循环的基本块是{B2, B3} 15、有翻译模式如下： S’ →S { print(S.h) } S→ a { S.h=0 } S→（T） {S.h= T.h+1} T→ T 1，S { T.h= T 1.h +S.h } T→ S { T.h= S.h } 采用移进归约的分析方法，当分析器的输入为(a,(a)) 时，画出其语法树（可以带注释、也可以不带注释），并求输出的结果。（2011） 输出结果是：2 S ( T ) T , S S a ( T ) S a 语法树： 得分 二、构造识别下列语言的最小DFA（共20分）： 1、正规式1（0|1）* 0 | 0；（7分） 1 1 1 D B A 0 0 1 0 C 求出NFA得4分，确定化了得6分，最小DFA的状态错漏一个扣1分，弧错漏一条扣0.5分。 2、以101结尾的二进制串；（8分） 0 0 B A D 0 C 1 1 1 1 0 求出NFA得4分，确定化了得6分，最小DFA的状态错漏一个扣1分，弧错漏一条扣0.5分。 3、不以101结尾的二进制串。（5分） 0 0 C B A 1 1 1 1 0 0 D 得分 构造识别下列语言的最小DFA（共15分）：（2011） 4、正规式（0|1）* （00 | 11）（0|1）*；（5分） 5、含有奇数个1或奇数个0的二进制串；（5分） 6、能被2整除的二进制串。（5分） 1、 A B C 0 0 0 0 1 1 1 D 1 0 2、 A C B D 0 1 1 1 1 0 0 3、 1 A B 0 1 0 构造下列正规式相应的DFA（用状态转换图表示）（15）（2008） （7） 1（0 | 1）*1 0,1 （8） 0*10*10*10*1 （9） letter（letter | digit）* 3 1 0 2 1 （7） 0 0 5 1 （8） 1 0 4 1 3 0 2 1 1 letter (9) 2 letter 1 digit 得分 7、将下图NFA确定化。（10分）（2013） b ε b b 2 a ε 1 0 b b 3 b {2} {3} a 确定化： （可以给状态换名） b a {0,1,3} a {1,2} {1,2，3} b b （确定化后再化简也不扣分，但要有说明） 8、将下图DFA化简。（5分）（2013） 0 1 0 0 1 0 0 D E A B C 1 1 首先将DFA的状态集划分成终态集和非终态集{E}、{A,B,C,D}; 由于{A,B,C,D}0={B,C,C,E}，所以再分划成{A,B,C}、{D}; 对于输入符号1，{A,B,C}1={ Φ,D,D}，所以再次分划成{A}、{B,C}; { B,C}0={C,C}，{B,C}1={D,D}，所以不用再分，B、C是等价状态。 得到最小的DFA如下： 0 1 0 A E 0 D B 1 0 1 9．有文法如下： S → a | b | (T) T → TeS | S S 请给出(Sebe(a))的语法树、短语、直接短语、素短语、句柄。（10分） 语法树： （5分） (2分)短语：(Sebe(a))、Sebe(a)、 Seb、(a)、S、b、a (1分)直接短语：S、b、a (1分)素短语：b、a (1分)句柄：S ) T ( S ) T e T S e T ( b S S a 10．有定义算术表达式的文法如下：（2011） E → E+T | E-T | T T → T*F | T/F | F F → PF | P P → (E) | i 构造句型E+T*PP-i的语法树；并指出该句型的所有短语、直接短语、素短语、句柄。（10分） 语法分析树： 所有的短语：E+T*PP-i、E+T*PP、i、T*PP、 PP、P 直接短语：P、i 素短语：PP、i 句柄：P F P E E - T + T T P * F F P E i ↑ 11、有文法如下：(共15分) S → aSe | ae (1) 构造文法的识别规范句型活前缀的DFA； (2) 分别写出上一步DFA各状态所识别的活前缀； (3) 给出符号串？？？？的LR移进-归约过程（包括状态栈、符号栈、输入串、分析动作）。 (1).(6分)拓广文法并给产生式编号： S’→S ①S→ aSe ②S→ae 文法的识别规范句型活前缀的DFA： a I5: S →aSe. I3: S →aS.e a I4: S →a e. e S e I2: S →a.Se S →a.e S →.aSe S →.ae S I1: S’ →S . I0: S’ →.S S →. aSe S →. ae (2).文法的所有规范句型的活前缀就是上一步DFA各状态所识别的符号串： ε| S | aa* | a*aS | a*ae | a*aSe （3分） (3). LR（0）分析表如下（6分）： ACTION GOTO a e # S 0 S2 1 1 acc 2 S2 S4 3 3 S5 4 r2 r2 r2 5 r1 r1 r1 空白处表示出错。 得分 12．有定义算术表达式的文法如下： E → E+T | E-T | T T → T*F | T/F | F F → PF | P P → (E) | i 构造句型Pi*(E+F-T)的语法树；并指出该句型所有的短语、直接短语、素短语以及句柄。（10分） （5分） 短语：(2分) Pi*(E+F-T)、Pi、i、 (E+F-T)、E+F-T、E+F、F 直接短语：i、F (1分) 素短语：i、E+F (1分) 句柄：i (1分) 语法树： E T * F T P F F E T + T - E ( E ) P F 13、给出下面语言的相应文法：（10）（2008） L1={a2n+1 bn+1 | n≥1} L2={anbm+nam | n≥1，m≥0} G1： S→AB A→aAb | ab B→bBa | ε G1： S→aaSb|ab 14、设有文法G[A]：（2008） A→BCc | gDB B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c (1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集； (2) 试判断该文法是否为LL（1）文法。（10） FIRST FOLLOW A B C D E a,b,c,d,g b，ε a,c,d d，ε c,g f a,c,d，f，g c,d,g a,b,c,f,g a,c,d,f,g 是LL（1）文法。 15、对表达式文法G：（2008） E → E+T | T T → T*F | F F → (E) | I （1）造各非终结符的FIRSTVT和LASTVT集合； （2）构造文法的算符优先关系表。（15） FIRSTVT LASTVT E T F *，+，（，i *，（，i （，i *，+，），i *，），i ），i 算符优先关系表 + * I （ ） # + * I （ ） # > > > < > < < > > < > < < < < < < < < < > > > = > > > > > = 16、对下述文法： （10） （2008） S→a | （T） T→ T ， S | S 构造一个翻译模式，统计输出配对的括号个数。 引入S、T的综合属性h来统计配对的括号个数，得到翻译模式如下： S’ →S {print(S.h)} S→ a { S.h=0 } S→（T） {S.h= T.h+1} T→ T 1， S { T.h= T 1.h +S.h } T→ S { T.h= S.h }  17、有文法如下： （共15分） S → aB B → aDd | d D → Ab | ε A → aD | e (1)计算文法的每个非终结符的FIRST集合和FOLLOW集合； (2)计算文法的每个候选产生式的SELECT集合； (3)说明文法是LL（1）文法的理由，并给出其预测分析表； (4)给出符号串aaebd 的预测分析过程（即最左推导过程）。 (1).（4分） FIRST(S)={ a } FOLLOW(S)={ # } FIRST(B)={ a,d } FOLLOW(B)={ # } FIRST(D)={ a,e,ε} FOLLOW(D)={ b,d } FIRST(A)={ a,e } FOLLOW(A)={ b } (2). （4分） SELECT(S → aB)={ a } SELECT(B → aDd)={ a } SELECT(B → d)={ d } SELECT(D → Ab)={ a,e } SELECT(D → ε)={ b,d } SELECT(A → aD)={ a } SELECT(A → e)={ e } a b d e # S S → aB B B →aDd B → d D D → Ab D→ε D→ε D→Ab A A → aD A→ e # # 结束 #d d# #db bd# #dbe ebd# A→e #dbA ebd# D→Ab #dD ebd# #dDa aebd# B →aDd #B aebd# #Ba aaebd# S→aB #S aaebd# 分析栈 输入串 所用规则 符号串aaebd 的最左推导过程： SaBaaDdaaAbdaaebd (3). （3分）符号串aaebd 的预测分析过程： (3). （4分）如上所求结果，定义非终结符B(或D或A)的两个规则的SELECT集合无交集，所以文法是LL(1)文法，其预测分析表如下： 18、有文法如下： （共10分）（2013） S → aAB B → a | d A → bB | eA | ε (1)计算文法的每个候选产生式的SELECT集合；(5分) (2)说明文法是LL（1）文法的理由，并给出其预测分析表。(5分) (1)SELECT(S → aAB)={a} SELECT(B → a)={a} SELECT(B → d)={d} SELECT(A → bB)={b} SELECT(A → eA)={e} SELECT(A →ε)={a，d} (2)文法不含左递归，定义B的两条产生式的SELECT集没有交集，定义A的三条产生式的SELECT集两两不相交，所以文法是LL（1）文法，预测分析表如下： a b d e # S S →aAB B B →a B →d A A →ε A →bB A →ε A→eA 19、有文法如下： （共15分）（2011） S → T L T → int | float L → id R R → ,id R |ε (1)计算文法的每个候选产生式的SELECT集合；(5分) (2)说明文法是LL（1）文法的理由，并给出其预测分析表；(6分) (3)给出符号串int id,id 的预测分析过程（包括分析栈、输入串、所用规则）。(4分) (1) SELECT(S → T L)={int，float} SELECT(T → int)={int } SELECT(T → float)={float} SELECT(L → id R)={id } SELECT(R → ,id R)={，} SELECT(R →ε)={$} (2)文法不含左递归，并且SELECT(T → int)∩SELECT(T → float)=Φ SELECT(R → ,id R)∩SELECT(R →ε)= Φ 所以文法是LL（1）文法，预测分析表如下： int float ， id $ S S → T L S → T L T T→int T→float L L → id R R R → ,id R R →ε (3)符号串int id,id 的预测分析过程： 分析栈 输入串 所用规则 $S int id,id$ S → TL $LT int id,id$ T→int $Lint int id,id$ int与int匹配 $L id,id$ L → id R $Rid id,id$ id与id匹配 $R ,id$ R → ,id R $Rid, ,id$ ，与，匹配 $ Rid id$ id与id匹配 $R $ R →e $ $ 分析结束 得分 20、有定义二进制串的文法如下：(共15分) S → L L → 0L1 L → 01 (1) 构造文法的识别规范句型活前缀的DFA； (2) 分别写出上一步DFA各状态所识别的活前缀； (3) 说明该文法是SLR（1）文法的理由，并给出SLR（1）分析表； (4) 给出符号串0011的LR移进-归约过程（包括状态栈、符号栈、输入串、 分析动作）。 (1).给产生式编号： S→L ①L→ 0L1 ②L→01 文法的识别规范句型活前缀的DFA（5分）： I5: L →0L1. I1: S →L. L I0: S →.L L →. 0L1 L →. 01 1 0 L I2: L→0.L1 L →0.1 L →.0L1 L →.01 ACTION GOTO 0 1 # L 0 S2 1 1 acc 2 S2 S4 3 3 S5 4 r2 r2 5 r1 r1 符号栈 状态栈 输入串 动作 # 0 0011# S2 #0 02 011# S2 #00 022 11# S4 #001 0224 1# r2 #0L 023 1# S5 #0L1 0235 # r1 #L 01 # acc (4)符号串0011的LR分析过程（3分）： (4)符号串aaee的LR分析过程（4分）： (3). （4分）因为上面DFA各状态都不含冲突，所以文法是LR(0)文法，也是SLR(1)文法。FOLLOW(L)={1,#}，SLR(1)分析表如下： LR（0）分析表如下（5分）： (2).上一步DFA各状态所识别的活前缀（3分）分别是： I0:ε； I1:L； I2:00*； I3:0*0L； I4:0*01； I5: 0*0L1； 0 I4: L →01. 1 I3: L →0L.1  21、有定义二进制串的文法如下：(共20分)（2011） L → LB | B B → 0 | 1 (1) 构造文法的识别规范句型活前缀的DFA； (2) 分别写出上一步DFA各状态所识别的活前缀； (3) 说明该文法是SLR（1）文法的理由，并给出SLR（1）分析表； (4) 给出符号串10的LR移进-归约过程（包括状态栈、符号栈、输入串、 分析动作）。 对文法进行拓广并为产生式编号： (0) S’ → L (1)L → LB (2)L → B (3)B → 0 (4)B → 1 (1)(6分)构造文法的识别活前缀的DFA如图： I0: S’ →.L L →.LB L →. B B →. 0 B →. 1 I1: S’ →L . L →L．B B →. 0 B →. 1 I2: L →B . I3: B → 0. I5: L →LB. I4: B →1. 0 B I0: S’ →.L L →.LB L →. B B →. 0 B →. 1 I1: S’ →L . L →L．B B →. 0 B →. 1 I2: L →B . I3: B → 0. I5: L →LB. I4: B →1. L B 0 0 1 1 (2) (4分)DFA各状态所识别的活前缀： I0: e I1: L I2: B I3: 0 | L0 I4: 1 | L1 I5: LB (3) (6分)I1中含移进-归约冲突, 但FOLLOW(S’) ={$},与待移进的符号集合{0，1}没有交集，所以是SLR(1)文法。FOLLOW(L)=FOLLOW(B) ={0,1,$}, SLR(1)分析表如下： 状态 ACTION GOTO 0 1 $ L B 0 S3 S4 1 2 1 S3 S4 acc 5 2 r2 r2 r2 3 r3 r3 r3 4 r4 r4 r4 5 r1 r1 r1 (4) (4分)符号串10的LR分析过程: 状态栈 符号栈 输入串 分析动作 0 $ 10$ S4 04 $1 0$ r4 02 $B 0$ r2 01 $L 0$ S3 013 $L0 $ r3 015 $LB $ r1 01 $L $ acc 六、证明题（本题共2小题，每小题5分，共10分） 1、证明正规式b(ab)* 与 (ba)*b是等价的。 （5分） 证明：因为两个正规式描述的正规集都是{ b，bab，babab，bababab，babababab，…… },所以等价。（用文字描述正规集也可以。） 或用等价的最小DFA一样来证明也可以，都是： a b 3 1 G[S]: S → (AS) | (b) A → (SaA) | (a) 2、有文法如： 证明符号串(((b)a(a))(b))是此文法的句子。（5分） 证明：因为存在最左推导序列（也可以用最右推导序列或语法树） S(AS)((SaA)S)(((b)aA)S)(((b)a(a))S) (((b)a(a))(b)) 且符号串(((b)a(a))(b))中只含终结符，所以它是此文法的句子。 3、证明文法G[S]： S → SS | a | b 是二义的。 （2013）（5分） S S 对于文法的符号串aabb，有两棵不同的语法树如右，所以该文法是二义的。 S S S S S S S S S S a S S b b a a a b b 4、证明下面的两个文法是等价的。（2013） （5分） G[S]: S → D0 | 0 D → S1 G[A]: A → 0B | 0 B → 1C C → 0B | 0 文法G[A]和文法G[S]定义的符号串集合都是0(10)*，所以两个文法是等价的。（用其他的等价正规式、DFA、改写文法也可以） G[S]: S → (AS) | (b) A → (SaA) | (a) 5、有文法如： 证明符号串(A((SaA)(b)))是此文法的规范句型。（5分） （2013） 对于符号串(A((SaA)(b)))存在如下最右推导（规范推导）： S(AS) (A(AS)) (A(A(b))) (A((SaA)(b))) 根据定义，符号串(A((SaA)(b)))是此文法的规范句型。 四、应用题（本题共15分） 1、写一个文法，使其语言是二进制奇数的集合，且每个奇数不以0开头。（5分）（2013） 或G[S]: S → 1A | 1 A → 1| 1A | 0A G[S]: S → 1 | 1A1 A →0A | 1A | ε 或G[S]: S → 1A1 | 1 A →ε| A0 | A1 或其他等价文法。 2、构造一个读取二进制串的有限自动机（要求是最小DFA），实现奇偶校验的奇校验。即，读入1的总数为奇数时则接受，读入1的总数为偶数时不接受。（10分） （2013）DFA读取的二进制串中1的个数或为偶数个、或为奇数个，所以该DFA只有两个状态，每个状态都可以输入0或1，输入0时对1的总数没影响（即状态不变），输入1时则1的总数多了一个（奇偶状态改变），可得最小DFA如下： 0 0 1 B A 1