《编译原理》课程研讨题.pdf

编 译 原 理 课程学习研讨题 上海大学计算机学院 《编译原理》课程组 2016 年3 月 第一次研讨、第一批 （第3 周） 1．讨论： （1）编译方法与解释方法的主要区别 （2 ）编译程序组合中分端(前端/后端)和分遍(单遍/ 多遍) 的作用 （3 ）编译程序生成方法中自编译与自展的含义 2 ．编写PL/0 程序,功能： 输入正整数n ，求sum = 1! + 2 ! + ... + n! 3 ．扩充PL/0 语言文法的定义，增加实数类型和数组类型。 例： Var i:integer; r:real; A:array[1..10]of real; …… A[i]:=r; 4 ．设有下列文法G1[S]和 G2[S] ：1)指出文法的类型 2 ）证明两者等价 G [S]：S→aAb | bBa 1 A→aA | a B→Bb | b G [S]：S→aA | bB 2 A→aA | aC B→bB | bD C→b D→a 5. 构造一个文法，使其语言是奇数集，且每个奇数不以0 开头。 6.文法G[S] 的一个句子abbba 的语法树如下图: S A B a A b b B a b 1) G[S]可能包含哪些产生式? 2) 给出句子abbba 的规范推导。 3) 求出句子abbba 的句柄。 7 ．设有上下文无关文法G[S] ：S→aAb A→aB A→a B→bA B→b 试构造与G[S]等价的正规文法。 8 实验一 识别标识符(A) 第一次研讨、第二批（第4 周） 1．编写PL/0 程序，输入正整数n 、x 、x 、…、x ，计算：S= ∑ x /i! i=1～n 。 1 2 n i 2 ．构造下列语言的文法，并分析比较 n n （1）L1(G)={a b |n≥1} （2 ）L2(G)={(ab) n |n≥1} n m （3 ）L3(G)={a b |n,m≥0} n m （4 ）L4(G)={a b |n,m≥1} 3.定义一个文法，产生表达式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 [S]：S→A A→AA A→aAb A→ab 1 ⑵ G [S]：S→aSb S→Sb S→b 2 7 ．试写出VT ＝{0,1}，分别满足下述要求的正则表达式： ⑴ 所有以1 开始和0 结束的符号串。 ⑵ 恰含有3 个1 的所有符号所组成的集合。 ⑶ 集合{01，1}。 ⑷ 所有以111 结束的符号串。 8．实验一 识别标识符(B)