《《编译原理》课程研讨题》由会员分享，可在线阅读，更多相关《《编译原理》课程研讨题（10页珍藏版）》请在金锄头文库上搜索。
1、编 译 原 理课程学习研讨题上海大学计算机学院编译原理课程组2016年3月第一次研讨、第一批（第3周）1讨论： （1）编译方法与解释方法的主要区别（2）编译程序组合中分端(前端/后端)和分遍(单遍/多遍)的作用（3）编译程序生成方法中自编译与自展的含义2编写PL/0程序,功能：输入正整数n，求sum = 1! + 2 ! + . + n!3扩充PL/0语言文法的定义，增加实数类型和数组类型。例：Var i:integer; r:real; A:array1.10of real; Ai:=r;4设有下列文法G1S和 G2S：1)指出文法的类型 2）证明两者等价 G1S：SaAb | bBa Aa
2、A | a BBb | b G2S：SaA | bB AaA | aC BbB | bD Cb Da5. 构造一个文法，使其语言是奇数集，且每个奇数不以0开头。6.文法GS 的一个句子abbba 的语法树如下图: S A B a A b b B a b 1) GS可能包含哪些产生式? 2) 给出句子abbba的规范推导。3) 求出句子abbba 的句柄。7设有上下文无关文法GS：SaAb AaB Aa BbA Bb试构造与GS等价的正规文法。8 实验一 识别标识符(A)第一次研讨、第二批（第4周）1编写PL/0程序，输入正整数n、x1、x2、xn，计算：S= xi/i! i=1n。2构造下列语
3、言的文法，并分析比较（1）L1(G)=anbn|n1（2）L2(G)=(ab) n|n1（3）L3(G)=anbm|n,m0（4）L4(G)=anbm|n,m13.定义一个文法，产生表达式E： 1）含有双目运算符 +，* 2）+ 的优先级高于* 3）+ 右结合，* 左结合 4）运算对象为标识符 i 5）可用括号改变算符的优先级4扩充PL/0语言文法的定义, 增加for语句的功能。for语句的示例如下：for i:= 1 to 100 do s:=s+i; 5.定义一个文法，产生下列语言： 该语言由a、b符号串组成，串中a和b的个数相同6证明下列文法为二义文法(能否转换为等价的非二义文法?) G
4、1S：SA AAA AaAb Aab G2S：SaSb SSb Sb 7试写出VT0,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: SELECT a, b FROM R WHERE a=15 OR b18;语句2: SELECT
5、R.a, S.c FROM R , S WHERE R.c=S.c AND R.b=3分时，机器会给顾客一块硬糖（只给糖不找钱）。 1）写出售后机售糖的正规表达式； 2）构造识别上述正规表达式的最简DFA。8. 实验二 词法分析(A)第二次研讨、第二批（第6周）1.给出的文法。例如：有2个关系R ( a,b,c)，S (c,d,e)。以下是嵌套查询语句的样例：语句：SELECT a,b FROM R WHERE R.c in (SELECT S.c FROM S WHERE d=15);2.构造一个最简DFA M，接受S=d，.，e，S上的正规式dd*.dd*(edd*e)表示的无符号数的集合
6、。其中d为09的数字。3正规文法（又称为右线性文法）：文法中每一条产生式的形式都为 ： AaB或Aa。 左线性文法：每一条产生式的形式都为：ABa或Aa。设计一个算法，把给定的左线性文法转换为等价的右线性文法。4. 构造一个DFA M,接受=a,b上满足下列条件的符号串： 1）以a开头，以b结尾； 2）不包含“aba”。5.对一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试举例说明。6已知文法GE的定义如下：E E + T | TT T * F | FF (E) | i 试构造一组递归下降分析子程序，使之识别GE所产生的语言。7.语言可接受的合法文件名为：device:n
7、ame.extension，其中device、name、extension是长度至少为1的字符串，而且第一部分（device:）和第三部分（.extension）可缺省。试画出识别这种文件名的最简DFA。8实验二 词法分析(B)第三次研讨、第一批（第7周）1设有文法GS：SSaF | F FFbP | P Pc | d(1) 构造GS的算符优先关系表(2) 分别给出cadbdac# 和 dbcabc# 的分析过程2已知文法GP的定义如下：P begin D S endD D; d | dS S; s | s试构造一组递归下降分析程序，使之识别GP所产生的语言。3设有文法GS：Sa B c |
8、b A B Aa A b | b Bb | e (1) 证明GS是一个LL(1)文法。 (2) 构造GS的预测分析表。 (3) 给出 baabbb 的分析过程。4设有文法GS: (0) SS (1) SSaA (2) Sa (3) AAbS (4) Ab(1) 构造GS的LR(0)项目规范族 C=I0,I1,In。(2) 构造SLR(1)分析表，判断GS的文法类型。(3) 写出句子aabba 的分析过程。5设采用自底向上的移进-归约语法分析，属性文法GA如下： A a B print “0”A c print “1”B A b print “2”(1) 输入为 aacbb 时，打印的符号串是什
9、么？(2) 写出aacbb的语法制导分析过程。6设有文法GE：EE+T | ET | TTT*F | TF | FFnum | bool |（E）设计GE的语义子程序，对表达式进行类型检查并翻译为逆波兰式。7设有文法Gnumber：number numnum numdigit num | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7| 8 | 9设计Gnumber的语义子程序，计算实数number的值。8实验三 语法分析(A)第三次研讨、第二批（第8周） 1设有文法GS：SA AA m D n | B Ba | m S n DS | DbS (1) 构造GS
10、的算符优先关系表。(2) 给出aman# 和 maban# 的分析过程。(3) 由(2)说明算符优先分析算法的局限性。 2设有文法GE：EETE |（E）| i T + | * (1) 证明GE是一个非LL(1)文法。 (2) 把GE等价改写为LL(1)文法G1E，并构造其预测分析表。 (3) 给出句子（i+i）* (i+i) 的分析过程。3 设有文法GS: S Ab | Ba A aA | a B a 将其改造成LL(1)文法，并编写递归下降分析程序，使之识别GS所产生的语言。4设有文法GS: (0) SS (1) SaS (2) SbA (3) AdA (4) Ad(1) 构造GS的LR(
11、0)项目规范族 C=I0,I1,In,(2) 说明GS属于哪一种LR文法，构造相应的LR分析表(3) 写出句子aabbd的分析过程。5写出表达式(ab*c)/(ab)d的四元式，逆波兰式及三元式序列。6条件语句的语法简写为：S iSeS | iS | S ; S | a其中: i代表if，e代表else，a代表赋值语句。如果规定：(1) else与其左边最近的if结合；(2) ；服从左结合。请给出文法中i、e和；的优先关系，然后构造出无二义的LR分析表，并对输入串iiaea写出分析过程。7设采用自底向上的移进-归约语法分析，属性文法GE如下：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
