资源描述：
《《编译原理》课程研讨题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理课程学习研讨题上海大学计算机学院《编译原理》课程组2016年3月第一次研讨、第一批（第3周）1．讨论：（1）编译方法与解释方法的主要区别（2）编译程序组合中分端(前端/后端)和分遍(单遍/多遍)的作用（3）编译程序生成方法中自编译与自展的含义2．编写PL/0程序,功能：输入正整数n，求sum=1!+2!+...+n!3．扩充PL/0语言文法的定义，增加实数类型和数组类型。例：Vari:integer;r:real;A:array[1..10]ofreal;……A[i]:=r;4．设有下列文法G1[S]和G2[S]：1)指出文法的类型2）证明两者等价G1[S]：
2、S→aAb
3、bBaA→aA
4、aB→Bb
5、bG2[S]：S→aA
6、bBA→aA
7、aCB→bB
8、bDC→bD→a5.构造一个文法，使其语言是奇数集，且每个奇数不以0开头。6.文法G[S]的一个句子abbba的语法树如下图:SABaAbbBab1)G[S]可能包含哪些产生式?2)给出句子abbba的规范推导。3)求出句子abbba的句柄。7．设有上下文无关文法G[S]：S→aAbA→aBA→aB→bAB→b试构造与G[S]等价的正规文法。8实验一识别标识符(A)第一次研讨、第二批（第4周）1．编写PL/0程序，输入正整数n、x1、x2、…、xn，计算：S=∑xi/i!i=1
9、～n。2．构造下列语言的文法，并分析比较（1）L1(G)={anbn
10、n≥1}（2）L2(G)={(ab)n
11、n≥1}（3）L3(G)={anbm
12、n,m≥0}（4）L4(G)={anbm
13、n,m≥1}3.定义一个文法，产生表达式E：1）含有双目运算符+，*2）+的优先级高于*3）+右结合，*左结合4）运算对象为标识符i5）可用括号改变算符的优先级4．扩充PL/0语言文法的定义,增加for语句的功能。for语句的示例如下：fori:=1to100dos:=s+i;5.定义一个文法，产生下列语言：该语言由a、b符号串组成，串中a和b的个数相同6．证明下列文法为二义文法(
14、能否转换为等价的非二义文法?)⑴G1[S]：S→AA→AAA→aAbA→ab⑵G2[S]：S→aSbS→SbS→b7．试写出VT＝{0,1}，分别满足下述要求的正则表达式：⑴所有以1开始和0结束的符号串。⑵恰含有3个1的所有符号所组成的集合。⑶集合{01，1}。⑷所有以111结束的符号串。8．实验一识别标识符(B)第二次研讨、第一批（第5周）1．构造一个DFA，接受∑={a，b}上由正规式aa*(a
15、ba)*b定义的字符串并给出相应的正规文法。2.写出<简单查询语句>的文法.例如:有2个关系R(a,b,c)，S(c,d,e)。以下是简单查询语句的样例：语句1:SELE
16、CTa,bFROMRWHEREa=15ORb<18;语句2:SELECTR.a,S.cFROMR,SWHERER.c=S.cANDR.b<18;3．下面文法G[S]产生a、b字符数相等的非空a、b字符串。S→aB
17、bAB→bS
18、aBB
19、bA→aS
20、bAA
21、a1）证明该文法是二义的。2）修改上述文法，使之非二义。4．试用有限自动机的等价性证明以下2个正规式((a
22、b)*
23、aa)*b和(a
24、b)*b是等价的，并给出相应的正规文法。5．写出Σ={a,b}上L={w
25、w中的a的个数为偶数}的正规式，构造接受L的DFA。6.构造一个最简的DFAM，接受Σ={a，b}上同时满足
26、下列条件的符号串：1）以a开头，以b结尾；2）符号串中包含“aba”。7．有一台自动售货机，接收1分和2分硬币，出售3分一块的硬糖。顾客每次向机器中投放一个硬币，当投放硬币额>=3分时，机器会给顾客一块硬糖（只给糖不找钱）。1）写出售后机售糖的正规表达式；2）构造识别上述正规表达式的最简DFA。8.实验二词法分析(A)第二次研讨、第二批（第6周）1.给出<嵌套查询语句>的文法。例如：有2个关系R(a,b,c)，S(c,d,e)。以下是嵌套查询语句的样例：语句：SELECTa,bFROMRWHERER.cin(SELECTS.cFROMSWHEREd=15);2.构造一
27、个最简DFAM，接受S={d，.，e}，S上的正规式dd*.dd*(edd*½e)表示的无符号数的集合。其中d为0~9的数字。3．正规文法（又称为右线性文法）：文法中每一条产生式α→β的形式都为：A→aB或A→a。左线性文法：每一条产生式α→β的形式都为：A→Ba或A→a。设计一个算法，把给定的左线性文法转换为等价的右线性文法。4.构造一个DFAM,接受Σ={a,b}上满足下列条件的符号串：1）以a开头，以b结尾；2）不包含“aba”。5.对一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1))文法？试举例说明。6．已知文法G[E]的定义如
