编译原理试卷.doc

一、判断对错：（对 ；错 ； 每小问2分共24分）算符优先分析法是一种规范归约分析法。（ ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（ ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ）若两个正规式所表示的正规集相同，则认为二者是等价的。 （ ）LR分析法是一种规范归约分析法。（ ）一个LR(0)项目集I=B .b, P aA.,则说I中含有“移进归约”冲突。（）SLR(1)文法是无二义性文法。（ ）消除左递归后的文法一定是LL(1)文法。（ ）对任何编译程序而言，代码优化是必不可少的。（ ）编译程序与具体的机器无关。（ ）在自动机的概念中，终态与非终态是可区别的。（ ）逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（ ）1. 一个语言有文法是不惟一的。（ ）2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（ ）3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（ ）4. 算符优先分析法是一种规范归约分析法。（ ）5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（）6. LR(0)文法、SLR(1)文法都是无二义性文法。（ ）7K、分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K 到K的单值映射。（ ）8. 对任何编译程序而言，代码优化是必不可少的。（ ）9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（ ）10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ）11. 一个LR(0)项目集为：I=Aa.b, D.,则说I中含有“移进-归约”冲突。（ ）12. 若两个正规式所表示的正规集相同，则认为二者是等价的。 （ ）13. 无左递归的文法是LL(1)文法。（ ）14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（ ）15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ）16. LALR分析法中，同心集的合并不会产生 “ 移进-归约 ” 冲突。（ ）算符优先分析法是一种规范归约分析法。（ 错 ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（对 ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ 错 ）若两个正规式所表示的正规集相同，则认为二者是等价的。 （ 对 ）LR分析法是一种规范归约分析法。（ 对 ）一个LR(0)项目集I=B .b, P aA.,则说I中含有“移进归约”冲突。（ 对 ）SLR(1)文法是无二义性文法。（ 对 ）消除左递归后的文法一定是LL(1)文法。（错 ）对任何编译程序而言，代码优化是必不可少的。（ 错 ）编译程序与具体的机器无关。（ 错 ）二、将下图所示的NFA确定化。(状态转换矩阵4分；状态转换图2分)解： 状态转换矩阵4分 状态转换图2分给出语言L= d an b | n1相应的文法。GA：A dBb GA：A dB B aB |a B aB | ab三、编译程序的工作过程一般划分为五个基本阶段： B；D 、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理 B.词法分析 C.表格管理 D.语法分析已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法终结符集合VT= A；C ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. +,(,),*,E C. +,*,(,),b D. E,T,F已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法的非终结符集VN= B ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. E,T,F C. +,*,(,),b D. E,T,F,*,+文法用于描述语言的语法结构，它由如下四个部分组成： A；C；D 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集一个文法被称为是二义性的，如果 A , D 。A.文法的某一个句子有两个以上的最右或最左推导。 B.文法的预测分析表中有多重入口。C.文法的某个LR(0)项目集中有冲突项目。 D.文法的某一个句子有两棵以上不同的语法树。程序设计语言的单词符号一般可分为五种，它们是保留字、 A；D 及运算符和定界符。A.常数 B.表达式 C.注解 D.标识符设有一个LR(0)项目集I=A.b， B. ，D.，I中存在冲突项目，它们是 A；D 。A.“移进-归约”冲突 B. “移进-接受”冲突 C. “移进-待约”冲突 D. “归约-归约”冲突一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数 A 。A.相同 B.不相同的 C.前者大于后者 D.后者大于前者1编译程序的工作过程一般划分为五个基本阶段：词法分析、 B D 、中间代码优化、目标代码生成。A.出错处理 B.语法分析 C.表格管理 D.语义分析与中间代码生成2识别某文法所有LR(0)项目集簇的DFA中，若项目集k中含有项目“A.”，且仅当输入符号aFOLLOW(A)时，才用规则“A ”归约的语法分析方法是 D 。ALALR分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法3程序设计语言的单词符号一般可分为五种，它们是常数、 C D 及运算符和定界符。A.注解 B.表达式 C.标识符 D.保留字4文法用于描述语言的语法结构，它由如下四个部分组成： A C D 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集5一个文法被称为是二义性的，如果 A C 。A.文法的某一个句子有两个以上的最右或最左推导。B.文法的预测分析表中有多重入口。C.文法的某一个句子有两棵以上不同的语法树。 D.文法的某个LR(0)项目集中有冲突项目。6已知文法GB：BB+T | T TT*F | F F(B) | b 那么，该文法终结符集合VT= A B ， GE称2型文法或上下文无关文法。 A. VT=+,*,(,),b B. VT= b,(, +,* ,) C. VT=B,T,F D. VT=B,T,F,+,*,(,b,)7在动态存储分配时，可以采用的分配方法有 B C 。A.分时动态存储分配 B.栈式动态存储分配 C. 堆式动态存储分配 D.最佳动态存储分配8设有一个LR(0)项目集I=A.d；Ab.B； Bd. ；DdB. ，I中存在冲突项目，它们是 A B 。A.“移进-归约”冲突 B.“归约-归约”冲突 C. “移进-待约”冲突 D. “移进-接受”冲突9在编译程序采用的优化方法中， B C D 是在循环语句范围内进行的。A. 删除多余运算 B.代码外提 C. 删除归纳变量 D.强度消弱10编译程序生成的目标代码通常有3种形式，它们是 A C D 。A.能够立即执行的机器语言代码 B.中间语言代码 C.汇编语言程序 D.待装配的机器语言代码编译程序的工作过程一般划分为五个基本阶段： BD 、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理 B.词法分析 C.表格管理 D.语法分析已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法终结符集合VT= AC ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. +,(,),*,E C. +,*,(,),b D. E,T,F已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法的非终结符集VN= B ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. E,T,F C. +,*,(,),b D. E,T,F,*,+文法用于描述语言的语法结构，它由如下四个部分组成： ACD 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集一个文法被称为是二义性的，如果 D 。A.文法的某一个句子有两个以上的最右或最左推导。 B.文法的预测分析表中有多重入口。C.文法的某个LR(0)项目集中有冲突项目。 D.文法的某一个句子有两棵以上不同的语法树。程序设计语言的单词符号一般可分为五种，它们是保留字、 AD 及运算符和定界符。A.常数 B.表达式 C.注解 D.标识符设有一个LR(0)项目集I=A.b， B. ，D.，I中存在冲突项目，它们是 AD 。A.“移进-归约”冲突 B. “移进-接受”冲突 C. “移进-待约”冲突 D. “归约-归约”冲突一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数 A 。A.相同 B.不相同的 C.前者大于后者 D.后者大于前者四、计算题（共10分；画出语法树4分；其余按要求分别得：1分+1分+2分+2分）对于如下文法GB： B B + D | DD D * F | F 给出句型D + D *d+d 的最左素短语、句柄、F ( B ) | d 所有直接短语、短语。解：已知NFA如下图所示。(8分=6分+2分)确定化。(状态转换矩阵4分；状态转换图2分) 写出与其等价的右线性文法。解： 计算出DFA的状态转换矩阵4分；画出相应的状态转换图2分与其等价的右线性文法为：GA：A dA | bB | b A dA | bA | bB | B A代表结点1 B bB | dA | b B bC | b B代表结点2按确定化后的DFA构造的结果； 按NFA构造的结果对于文法GE：（共8分：语法树2分；其余按要求分别得1分、1分、2 分、2分） E E + B | BB B * F | F 给出句型B + B * b + b 的最左素短语、句柄、F ( E ) | b 直接短语和所有短语。解：五、1 给出以下表达式的三地址指令（或四元式序列）：(8分) d + b * d + b / m * ( m - b*d + 2 )解：四元式序列为 (三地址指令略)（*, b , d , T1） （+, d , T1 , T2） （/, b , m , T3） （*, b , d , T4）(-, m , T4, T5) (+,T5, 2,T6) (*, T3,T6,T7) (+,T2,T7,T8)2 给出以下表达式的三地址指令（即四元式序列）：(8分=3分+3分+2分) d + b *d+d* ( d + b * d )写出四种以上常用的代码优化技术？ 解：四元式序列为： 1 （*, b , d , T1）2 （+, d , T1 , T2）3 （*, b , d , T3）4 （+, d , T3 , T4）5 （*, d , T4 , T5）6 （+, T2 , T5, T6） 上述中间代码可以采用的优化措施有：合并（或称删除）公共子表达式即合并公共四元式1和3合并 4中T3改为T1 2和4合并 5中T4改为T2 删除四元式3和41 （*, b , d , T1）2 （+, d , T1 , T2）3 删除4 删除5 （*, d , T2 , T5）6 （+, T2 , T5, T6） 常用的代码优化技术有：循环上的优化包括：代码外提；强度削弱；删除归纳变量等基本块上的优化包括：合并公共子表达式；合并常数等六、综合题（每小题4分，共32分。若缺少必要的计算或分析步骤，扣适当的分数）已知文法GS：S dDb 提示：.=.=. 且 |=0 D aD | 求每个非终结符的First集、Follow集。求每条规则的Select集，判定是LL(1)文法。 构造GS的递归下降分析程序。 构造GS的预测分析表。 给出字符串daabb的LL(1)分析过程。 构造识别GS拓广文法的所有规范句型活前缀的DFA。 构造SLR(1)分析表。 GS是LR(0)文法吗？GS是SLR(1)文法吗？ 为什么？ 给出字符串daab的SLR(1)分析过程。解： 每个非终结符的First集、Follow集:每条产生式的Select集，判断该文法是否为LL(1)文法。 Select(S dDb)= d Select(D aD)= a Select(D )= b 因为 式 式 = ，因此，GS是LL(1)文法。递归下降分析器：Read()函数读一个单词到全局变量SYM中 ERROR()出错处理；SKIP空操作 Main()函数；略S( ) if sym=d then read(); D(); If sym=b then read(); Else Error() D( ) if sym=a then read(); D() Else if sym=b then skip; Else Error(); 构造GS的预测分析表如下： 分析栈 输入流 动作#S daabb# dDb#bDd daabb# 匹配 #bD aabb# aD #bDa aabb# 匹配 #bD abb# aD #bDa abb# 匹配 #bD bb# D #b bb# 匹配 # b# 出错 识别GS拓广文法的所有规范句型活前缀的DFA构造如下：说明：产生式编号可以不从1开始，但是与归约符r的下标必须一致； SLR(1)表中的行可以任意排列，但是必须与项目集编号一致。 SLR(1)分析表构造如下： 显然项目集I2、I4中有“移进归约”冲，GS不是LR(0)文法。因为SLR(1)分析表中无多重入口，所以GS是SLR(1)文法。字符串daab的SLR(1)分析过程如下：状态栈 符号栈 输入流 动作0 # daab# S202 #d aab# S4024 #da ab# S40244 #daa b# r402446 #daaD b# r30246 #daD b# r3023 #dD b# S50235 #dDb # r201 #S # OK已知文法GD：D aD | dAb （共40分，每小题5分） A dA | 提示：. =.=. 且 |=0 求每个非终结符的First集、Follow集。 求每条规则的Select集，判定是LL(1)文法。 构造GD的递归下降分析程序。 构造GD的预测分析表。 给出字符串addb的LL(1)分析过程 构造识别GD拓广文法的所有规范句型活前缀的自动机。 构造SLR(1)分析表。 GD是LR(0)文法吗？GD是SLR(1)文法吗？GD是LL(1)文法吗？为什么？ 给出字符串addbb的SLR(1)分析过程。解： 每个非终结符的First集、Follow集: 每条产生式的Select集，判断该文法是否为LL(1)文法。 Select(D dDb)= d Select(D aD)= a Select(A dA)= d Select(A ) = b 因为: 式 式 = ; 式 式 = 因此，GD是LL(1)文法。 递归下降分析程序构造如下：(1分+2分+2分)Main( ) /* Read函数表示把输入流首符读入变量SYM中*/Read( ); D( ); /* SYM存放输入流首符的全局变量*/if SYM=# then /* Write为输出函数；Skip为空操作*/write(“分析成功!”) /* Error