资源描述：
《上海大学编译原理试卷09.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、单项选择题。1．设x是符号串，则符号串的幂运算x0=__C___.A.1B.xC.εD.Æ2．字母表中的因素可以是__D___.A.字母B.字母、数字C.数字D.字母、数字和其它符号3．设文法G[S]=({S,B},{b},{S→bB
2、b,B→bS},S),则该文法所描述的语言是C__.A.L(G[S])={bn
3、n≥0}B.L(G[S])={b2n
4、n≥0}C.L(G[S])={b2n+1
5、n≥0}D.L(G[S])={b2n+1
6、n≥1}4．一个句型最左边的C__称为该句型的句柄.A.短语B.素短语C.直接短语D.规范短语5．语法分析方法中
7、，递归下降分析法属于B__.A.自左至右B.自上而下C.自下而上D.自右至左6．通常程序设计语言的词法规则可用正规式描述，词法分析器可用B__描述.A.语法树B.有穷自动机C.栈D.堆7．自下而上语法分析的原理是B__.A.“移进—推导法”B.“移进—归约法”C.“最左推导法”D.“推导—归约法”8．算法优先文法从左向右扫描输入串，当栈顶出现D_时进行归约.A.素短语B.直接短语C.句柄D.最左素短语9．LR语法分析栈中存放的状态是识别文法规范句型B__的DFA状态.A.前缀B.活前缀C.项目D.句柄10．中缀表达式-a+b*(-c+d)的逆波兰式
8、是A__.A.a@bc@d+*+B.abc@d+*+@C.a@bcd+@*+D.abcd+@*+@二、是非判断题正确的在题后的括号内填T，错误的填F1.描述一个语言的文法是惟一的。（F）2.用二义性文法定义的语言也是二义的。（F）3.若两个正规式所表示的正规集相同，则认为两者是等价的。（T）4.有穷自动机的初态和终态是可区别的。（T）5.算法优先分析方法属于自上而下的分析方法。（F）6.SLR(1)文法是二义性文法。（F）1.转移语句是基本块的入口语句。（F）2.堆式存储分配属于静态存储分配。（F）3.跟踪嵌套过程语言的每个外层过程的最新活动过程的
9、记录，常用的办法有在过程活动记录中增设存取链，或者建立一张嵌套层次显示表Display表。（T）4.符号表可以辅助语法错误检查。（T）三、（本题满分10分）构造正规式1(0
10、1)*101相应的DFA.解：NFA如下：（4分，每错1处扣1分，扣完4分为止）确定化（4分，每错1处扣1分，扣完4分为止）I(标记)I0I1[X]0[A]1[A]1[A]1[A,B]2[A,B]2[A,C]3[A,B]2[A,C]3[A]1[A,B,Y]4[A,B,Y]4[A,C]3[A,B]2I0=ε-Closure(move(I,0))I1=ε-Closure(move(
11、I,1))DFA：（2分，每错1处扣1分，扣完2分为止）四、（本题满分15分）对文法G[S]S→a
12、Ù
13、(T)T→T,S
14、S进行改写，消除左递归。经改写后的文法是否是LL(1)文法？证明之。【解】（10分，每错1处扣1分，扣完10分为止）改写文法为：0)S->a1)S->^2)S->(T)3)T->ST’4)T’->,ST’5)T’->εFIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST(T’)={,,ε}FOLLOW(S)={#,,,)}FOLLOW(T)={)}FOLLOW(T’)={)}（5分，每错1处扣1分，扣完5分
15、为止）SELECT(S->a)={a}SELECT(S->^)={^}SELECT(S->(T))={(}∴SELECT(S->a)∩SELECT(S->^)∩SELECT(S->(T))=fSELECT(T’->,ST’)={,}SELECT(T’->ε)=FOLLOW(T’)={)}∴SELECT(T’->,ST’)∩SELECT(T’->ε)=f∴相同左部符号产生式的SELECT集的交集为空，从而判断该文法是LL(1)文法五、（本题满分5分）已知一个算符优先文法G[S]的优先关系表如下：算符优先关系表aÙ(),#a·>·>·>Ù·>·>·>(
16、<·<·<·=·<·)·>·>·>,<·<·<··>·>#<·<·<·=·给出输入串(a,a)#的算符优先分析过程，并说明该输入串是否是该文法的一个句子。解：（4分，每错一处扣0.5分，扣完4分为止）对输入串为(a,a)#的算符优先分析过程步骤栈优先关系当前符号剩余输入串移进/归约1#<·（a,a)#移进2#(<·a,a)#移进3#(a·>,a)#归约4#(N<·,a)#移进5#(N,<·a)#移进6#(N,a·>)#归约7#(N,N·>)#归约8#(N=·)#移进9#(N）·>#归约10#N=·#接受输入串为(a,a)是该文法的一个句子。（1分）
17、六、下列文法是否为SLR(1)文法？（要求构造相应的分析表，说明理由）SàSab
18、bRRàS
19、a解：(a)该文法的拓广文法
