第一次研讨、第一批（第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）证明两者等价G1[S]：S→aAb | bBaA→aA | aB→Bb | bG2[S]：S→aA | bBA→aA | aCB→bB | bDC→bD→a5. 构造一个文法，使其语言是奇数集，且每个奇数不以0开头。
6.文法G[S] 的一个句子abbba 的语法树如下图:SA B aA b b Ba b1) 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、x1、x2、…、x n，计算：S= ∑ x i/i! i=1～n。
2．构造下列语言的文法，并分析比较（1）L1(G)={a n b n|n≥1}（2）L2(G)={(ab) n|n≥1}（3）L3(G)={a n b m|n,m≥0}（4）L4(G)={a n b m|n,m≥1}3.定义一个文法，产生表达式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．证明下列文法为二义文法(能否转换为等价的非二义文法?)⑴G1[S]：S→A A→AA A→aAb A→ab⑵G2[S]：S→aSb S→Sb S→b7．试写出V T＝{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: SELECT a, b FROM R WHERE a=15 OR b<18;语句2: SELECT R.a, S.c FROM R , S WHERE R.c=S.c AND R.b<18; 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. 构造一个最简的DFA M，接受Σ={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)。
以下是嵌套查询语句的样例：语句：SELECT a,bFROM RWHERE R.c in (SELECT S.cFROM SWHERE d=15);2.构造一个最简DFA M，接受∑={d，.，e}，∑上的正规式dd*.dd*(edd*∣ε)表示的无符号数的集合。
其中d 为0~9的数字。
3．正规文法（又称为右线性文法）：文法中每一条产生式α→β的形式都为：A→aB或A→a。
左线性文法：每一条产生式α→β的形式都为：A→Ba或A→a。
设计一个算法，把给定的左线性文法转换为等价的右线性文法。
4. 构造一个DFA M,接受Σ={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 | F F→FbP | P P→c | d(1) 构造G[S]的算符优先关系表(2) 分别给出cadbdac# 和dbcabc# 的分析过程2．已知文法G[P]的定义如下：P → begin D S endD → D; d | dS → S; s | s试构造一组递归下降分析程序，使之识别G[P]所产生的语言。
3．设有文法G[S]：S→a B c | b A B A→a A b | b B→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→ a B { print “0”}A→ c { print “1”}B→ A b { 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→digit num | digitdigit→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7| 8 | 9设计G[number]的语义子程序，计算实数number的值。
8．实验三语法分析(A)第三次研讨、第二批（第8周）1．设有文法G[S]：S→A A→A m D n | B B→a | m S n D→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 (A<C or B<D ) dobeginif (A>=1) then C:=C+1else while (A<=D) doA:=A+2;end4．教材P252 第2题5．对下列基本块B应用DAG进行优化，设只有U，V在基本块后面还要继续引用。