1、编译原理课程研讨题第一次研讨、第一批（第 3周）1.讨论：（1） 编译方法与解释方法的主要区别（2） 编译程序组合中分端（前端/后端）和分遍（单遍/多遍）的作用（3） 编译程序生成方法中自编译与自展的含义2.编写PL/O程序,功能：输入正整数n,求sum = 1! + 2 ! + . + n!3.扩充PL/O语言文法的定义，增加实数类型和数组类型 例：Var i:i nteger;r:real;A:array1.10of real;Ai:=r;4.设有下列文法G1S和G2S: 1）指出文法的类型2）证明两者等价G1 S:S aAb |bBaA aA |aB Bb |bG2S:S aA |bBA
2、 aA |aCB bB |bDCbDa5.构造一个文法，使其语言是奇数集，且每个奇数不以 0开头6.文法GS的一个句子abbba的语法树如下图：a1） GS可能包含哪些产生式？2） 给出句子abbba的规范推导3） 求出句子abbba的句柄。7 .设有上下文无关文法 GS: S aAb A aB A a B bA Bb 试构造与GS等价的正规文法。8实验一识别标识符（A）第一次研讨、第二批（第 4 周）1 编写PL/O程序，输入正整数 n、XI、X2、xn,计算：S=刀Xi! i=1n 2构造下列语言的文法，并分析比较(1)L1(G)=anbn|n 1(2)L2(G)=(ab) n|n 1(3
3、)L3(G)=a nbm|n,m 0(4)L4(G)=a nbm|n,m 13.定义一个文法，产生表达式 E： 1 ）含有双目运算符 +， * 2） + 的优先级高于 *3） + 右结合， * 左结合4） 运算对象为标识符 i5） 可用括号改变算符的优先级4扩充 PL/0 语言文法的定义 , 增加 for 语句的功能 for 语句的示例如下：for i:= 1 to 100 do s:=s+i;5.定义一个文法，产生下列语言：该语言由 a、 b 符号串组成，串中 a 和 b 的个数相同6证明下列文法为二义文法 （能否转换为等价的非二义文法 ?） G1S: S A A AA A aAb A ab
4、 G2S: S aSb S Sb S b7试写出Vt = 0,1，分别满足下述要求的正则表达式： 所有以 1 开始和 0 结束的符号串。 恰含有 3 个 1 的所有符号所组成的集合。 集合01， 1。 所有以 111 结束的符号串。8实验一 识别标识符 （B）1 构造一个DFA，接受刀=a b上由正规式as*(a|bajb定义的字符串并给出相 应的正规文法。2.写出 简单查询语句 的文法.例如：有2个关系R ( a,b,c), S (c,d,e)以下是简单查询语句的样例:语句 1：SELECT a, b FROM R WHERE a=15 OR b18;语句 2：SELECT R.a, S.c
5、 FROM R , S WHERE R.c=S.c AND R.b18;3下面文法GS产生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的DFA6.构造一个最简的DFA M，接受工=a b上同时满足下列条件的符号串:1 )以 a 开头，以 b 结尾；2)符号串中包含 “aba。”7.有一
6、台自动售货机，接收 1 分和 2分硬币，出售 3分一块的硬糖。顾客每次 向机器中投放一个硬币，当投放硬币额 =3 分时，机器会给顾客一块硬糖(只给 糖不找钱)。1)写出售后机售糖的正规表达式；2)构造识别上述正规表达式的最简 DFA。8.实验二 词法分析 (A)1.给出 嵌套查询语句 的文法例如：有2个关系R ( a,b,c)，S (c,d,e)。以下是嵌套查询语句的样例:语句：SELECT a,bFROM RWHERE R.c in (SELECT S.c FROM S WHERE d=15);2.构造一个最简DFA M，接受=d，.，e， 上的正规式 dd .dd (edd )表示的无符号
7、数的集合。其中 d 为 09 的数字。3 正规文法(又称为右线性文法)：文法中每一条产生式a 的形式都为： Af aB 或 Aa。左线性文法：每一条产生式 a 的形式都为：A Ba或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.语言
8、可接受的合法文件名为： device:name.extension其中 device、name、extension是长度至少为 1的字符串，而且第一部分( device:)和第三部分(.extension)可缺省。试画出识别这种文件名的最简 DFA。8实验二 词法分析 (B)1.设有文法 GS: S SaF | F F FbP | P P c | d(1)构造GS的算符优先关系表(2)分别给出 cadbdac# 和 dbcabc# 的分析过程2.已知文法GP的定义如下：P begin D S endD D; d | dS S; s | s试构造一组递归下降分析程序，使之识别 GP所产生的语言3
9、.设有文法 GS： Sa B c | b A B Aa A b | b Bb |证明GS是一个LL(1)文法。构造GS的预测分析表。(3)给出 baabbb 的分析过程。4.设有文法 GS: (0) S (1S) S SaA (2) S a (3) A AbS (4) A b(1)构造GS的LR(0)项目规范族 C=IO,I1,In构造SLR(1)分析表，判断GS的文法类型(3) 写出句子 aabba 的分析过程5 .设采用自底向上的移进-归约语法分析，属性文法 GA如下:A a B print“O”A c print“1”B A b print“2”(1) 输入为aacbb 时，打印的符号串
10、是什么？写出aacbb的语法制导分析过程6.设有文法 GE: E E+T | EVT | TT T*F | T A F | F F num | bool |(E)设计GE的语义子程序，对表达式进行类型检查并翻译为逆波兰式7.设有文法 Gnumber: number num numnu m digit num | digit digit O | 1 | 2 | 3 | 4 | 5 | 6 | 7| 8 | 9设计Gnumber的语义子程序，计算实数 number的值。8.实验三 语法分析 (A)1 .设有文法 GS: S A A A m D n | B B a | m S n S | DbS(1
11、)构造GS的算符优先关系表。(2)给出 aman# 和 maban# 的分析过程。(3)由(2)说明算符优先分析算法的局限性。2.设有文法 GE: EETE |(E)| iT + | * 证明GE是一个非LL文法。把GE等价改写为LL文法G1E，并构造其预测分析表。(3) 给出句子( i+i)* (i+i) 的分析过程。3.设有文法 GS: S Ab | BaA aA | aB a将其改造成LL(1)文法，并编写递归下降分析程序，使之识别 GS所产生的4.设有文法 GS: (0) S (1) S aS (2) S bA (3) A dA (4) A d(1)构造GS的LR(O)项目规范族 C=
12、lo,li,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“O”E T print“1”T T *
13、 F print“2”T F print“3”F (E) print“4”F i print“5”写出 i*(i+i*i) 的语法制导分析过程，打印的符号串是什么？8.实验三 语法分析 (B)1以下是简单表达式(只含有加、减运算)计算的一个属性文法 G(E)E TR R.in :=T.val ; E.val := R.val R +TRi 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)
14、 其中：lexval(num)表示从词法分析程序得到的常数的值。试给出表达式8-3+6 的语法树和相应的带标注语法分析树。2教材 P224 第 4题。3写出下列语句的三地址中间代码(四元式序列) ： while (AC or B=1) then C:=C+1 else while (AC goto L26)B=B+17)Goto L4(8)L2: write ( B )2)找出题1)流图中的回边与循环7把下列中间代码序列划分为基本块并作出其流图1) read(x) read(y)(3)A := 10 if xy goto (5)A := 20 x := x+1(7)y := y-1(8)if
15、y 0 or s s) the n s:=s+i; i:=i -1;end;5设有基本块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: 输入 3 4 5 + * 输出 27例 2: 输入 3 4 5 * + 输出 238实验四语义分析(B)或实验五中间代码生成(B)
