搜索
编译原理课程学习研讨题上海大学计算机学院《编译原理》课程组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]：S→aAb|bBaA→aA|aB→Bb|bG2[S]：S→aA|bBA→aA|aCB→bB|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～n。2．构造下列语言的文法，并分析比较（1）L1(G)={anbn|n≥1}（2）L2(G)={(ab)n|n≥1}（3）L3(G)={anbm|n,m≥0}（4）L4(G)={anbm|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．证明下列文法为二义文法(能否转换为等价的非二义文法?)⑴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|ba)*b定义的字符串并给出相应的正规文法。2.写出简单查询语句的文法.例如:有2个关系R(a,b,c)，S(c,d,e)。以下是简单查询语句的样例：语句1:SELECTa,bFROMRWHEREa=15ORb18;语句2:SELECTR.a,S.cFROMR,SWHERER.c=S.cANDR.b18;3．下面文法G[S]产生a、b字符数相等的非空a、b字符串。S→aB|bAB→bS|aBB|bA→aS|bAA|a1）证明该文法是二义的。2）修改上述文法，使之非二义。4．试用有限自动机的等价性证明以下2个正规式((a|b)*|aa)*b和(a|b)*b是等价的，并给出相应的正规文法。5．写出Σ={a,b}上L={w|w中的a的个数为偶数}的正规式，构造接受L的DFA。6.构造一个最简的DFAM，接受Σ={a，b}上同时满足下列条件的符号串：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.构造一个最简DFAM，接受={d，.，e}，上的正规式dd.dd(edd)表示的无符号数的集合。其中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]的定义如下：E→E+T|TT→T*F|FF→(E)|i试构造一组递归下降分析子程序，使之识别G[E]所产生的语言。7.语言可接受的合法文件名为：device:name.extension，其中device、name、extension是长度至少为1的字符串，而且第一部分（device:）和第三部分（.extension）可缺省。试画出识别这种文件名的最简DFA。8．实验二词法分析(B)第三次研讨、第一批（第7周）1．设有文法G[S]：S→SaF|FF→FbP|PP→c|d(1)构造G[S]的算符优先关系表(2)分别给出cadbdac#和dbcabc#的分析过程2．已知文法G[P]的定义如下：P→beginDSendD→D;d|dS→S;s|s试构造一组递归下降分析程序，使之识别G[P]所产生的语言。3．设有文法G[S]：S→aBc|bABA→aAb|bB→b|(1)证明G[S]是一个LL(1)文法。(2)构造G[S]的预测分析表。(3)给出baabbb的分析过程。4．设有文法G[S’]:(0)S’→S(1)S→SaA(2)S→a(3)A→AbS(4)A→b(1)构造G[S]的LR(0)项目规范族C={I0,I1,…In}。(2)构造SLR(1)分析表，判断G[S]的文法类型。(3)写出句子aabba的分析过程。5．设采用自底向上的移进-归约语法分析，属性文法G[A]如下：A→aB{print“0”}A→c{print“1”}B→Ab{print“2”}(1)输入为aacbb时，打印的符号串是什么？(2)写出aacbb的语法制导分析过程。6．设有文法G[E]：E→E+T|E∨T|TT→T*F|T∧F|FF→num|bool|（E）设计G[E]的语义子程序，对表达式进行类型检查并翻译为逆波兰式。7．设有文法G[number]：number→num·numnum→digitnum|digitdigit→0|1|2|3|4|5|6|7|8|9设计G[number]的语义子程序，计算实数number的值。8．实验三语法分析(A)第三次研讨、第二批（第8周）1．设有文法G[S]：S→AA→AmDn|BB→a|mSnD→S|DbS(1)构造G[S]的算符优先关系表。(2)给出aman#和maban#的分析过程。(3)由(2)说明算符优先分析算法的局限性。2．设有文法G[E]：E→ETE|（E）|iT→+|*(1)证明G[E]是一个非LL(1)文法。(2)把G[E]等价改写为LL(1)文法G1[E]，并构造其预测分析表。(3)给出句子（i+i）*(i+i)的分析过程。3．设有文法G[S]:S→Ab|BaA→aA|aB→a将其改造成LL(1)文法，并编写递归下降分析程序，使之识别G[S]所产生的语言。4．设有文法G[S’]:(0)S’→S(1)S→aS(2)S→bA(3)A→dA(4)A→d(1)构造G[S]的LR(0)项目规范族C={I0,I1,…In},(2)说明G[S]属于哪一种LR文法，构造相应的LR分析表(3)写出句子aabbd的分析过程。5．写出表达式(a＋b*c)/(a＋b)－d的四元式，逆波兰式及三元式序列。6．条件语句的语法简写为：S→iSeS|iS|S;S|a其中:i代表if，e代表else，a代表赋值语句。如果规定：(1)else与其左边最近的if结合；(2)；服从左结合。请给出文法中i、e和；的优先关系，然后构造出无二义的LR分析表，并对输入串iiaea写出分析过程。7．设采用自底向上的移进-归约语法分析，属性文法G[E]如下：E→E+T{print“0”}E→T{print“1”}T→T*F{print“2”}T→F{print“3”}F→(E){print“4”}F→i{print“5”}写出i*(i+i*i)的语法制导分析过程，打印的符号串是什么？8．实验三语法分析(B)第四次研讨、第一批（第9周）1．以下是简单表达式（只含有加、减运算）计算的一个属性文法G（E）:E→TR{R.in:=T.val;E.val:=R.val}R→+TR1{R1.in:=R.in+T.val;R.val:=R1.val}R→-TR1{R1.in:=R.in-T.val;R.val:=R1.val}R→{R.val:=R.in}T→num{T.val:=lexval(num)}其中：lexval(num)表示从词法分析程序得到的常数的值。试给出表达式8-3+6的语法树和相应的带标注语法分析树。2．教材P224第4题。3．写出下列语句的三地址中间代码（四元式序列）：while(ACorBD)dobeginif(A=1)thenC:=C+1elsewhile(A=D)doA:=A+2;end4．教材P252第2题5．对下列基本块B应用DAG进行优化，设只有U，V在基本块后面还要继续引用。B:T0:=100T1:=k+T0T2:=T0*2U:=T1+T2T3:=k+T0V:=T3*U6．1）把下列中间代码序列划分为基本块并作出其流图（1）read(C)（2）A=0（3）B=1（4）L4:A=A+B（5）ifBCgotoL2（6）B=B+1（7）GotoL4（8）L2:write(B)2）找出题1）流图中的回边与循环7．把下列中间代码序列划分为基本块并作出其流图1）(1)read(x)(2)read(y)(3)A:=10(4)ifxygoto(7)(5)A:=20(6)x:=x+1(7)y:=y-1(8)ify≤20goto(4)(9)B:=A(10)write(B)2）找出题1）流图中的回边与循环3）讨论题2）循环中的不变运算（A:=20）外提的可行性8．实验四语义分析(A)或实验五中间代码生成(A)第四次研讨、第二批（第10周）1．教材P291第6题。2．教材P224第5题。3．设有向图G(E,V)的邻接矩阵如右图所示：找出G(E,V)中的回边与循环4．给出下列源语句的四元式序列：i:=100;s:=0;while(i0ors1000)dobeginif(is)thens:=s+i;i:=i-1;end;1234561011000200110030010004000011501000160001005．设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，写出DAG优化后的四元序列。6．写出对下列四元式进行优化后的结果。for(k=1;k=100;k++){m=i+10*k;n=j+10*k；}(1)(=,1,-,k)(2)(j,100,k,9)(3)(*,10,k,t1)(4)(+,i,t1,m)(5)(*,10,k,t2)(6)(+,j,t2,n)(7)(+,k,1,k)(8)(j,-,-,2)7．设计一个算法，对逆波兰算术表达式解释执行.例1:输入345+*输出27例2:输入345*+输出238．实验四语义分析(B)或实验五中间代码生成(B)