第一章词法分析
1. 给出下面的正规表达式：
(1) 以01结尾的二进制数串 (2) 能被5整除的十进制整数
(3) 包含奇数个1和奇数个0的二进制数串
(4) 不包含字串abb的由a和b组成的符号串的全体 2. 构造下列正规式相应的DFA（要求状态最少）
(1) 1(0|1)*101
(2) 1(1010*|1(010)*1)*0 (3) a((a|b)*|ab*a)*b (4) b((ab)*|bb)*ab
3. 将下图的(a)确定化；(b)最小化
b0b2bb3aa0a,b1aaaab14b5aa
(a) (b)
4. 浮点数的定义如下：它只含有一个小数点，小数点前后至少有一位数字。指数用E表示，
后面跟一个符号（+或-）或者无此符号，再后面跟一个或一个以上的数字串。（例如，1.175494351 E – 38和3.402823466 E 38都是浮点数）(10分) (1) 构造出产生该浮点数的正规文法 (2) 用正规式表示上述浮点数
(3) 构造接受该浮点数的有限自动机（NFA和DFA都可以）
第二章语法分析
本章主要掌握下面的一些内容。 1． 文法和语言的基本知识。
2． 自上而下的分析方法：预测分析器(递归下降分析方法)，非递归的预测分析器（分
析表方法)，LL(1)文法。
3． 算符优先分析方法。现在的编译器很少用这种方法了，了解即可。
4． 自下而上的分析方法：SLR(1)方法，规范LR(1)方法和LALR(1)方法。这三种方法
中，重点是规范LR(1)方法，规范LR(1)方法了解透彻了，其它两种就不难了。
5． LR方法如何用于二义文法。 6．语法分析的错误恢复方法。 文法方面的习题：
1． 文法
S→aSbS | bSaS |ε
产生的语言是什么?该文法去是否二义？
语法分析方面的习题：
1.消除下列文法的左递归性。
(1) S→SA S→A A→SB A→B A→(S) A→( ) B→［S］ B→［ ］ (2) S→AS S→b A→SA A→a (3) S→(T) S→a S→ε T→S T→T,S 2.设已给文法：
S→AbB S→d A→CAb A→Bf B→CSd B→d C→ed C→a
试写出对符号串eddfbbd进行带回溯的自顶向下语法分析的过程。 3.对于如下的文法，求出各个FIRST集和FOLLOW集。
S→aAB S→bA S→ε A→aAb A→ε B→bB B→ε 4.验证下列文法是否为LL(1)文法。
(1) S→AB S→CDa A→ab A→c B→dE C→eC C→ε D→fD D→f E→dE E→ε
(2) S→aABbCD S→ε A→ASd A→ε B→Sac B→eC B→ε C→Sf
C→Cg C→ε D→aBD D→ε
5.对于如下的文法G［S］：
S→Sb S→Ab S→b A→Aa A→a (1) 构造一个与G等价的LL(1)文法G′； (2) 对于G′，构造相应的LL(1)分析表。 6.设已给文法
S→SaB S→bB A→S A→a B→Ac (1) 求出各个FIRST集和FOLLOW集； (2) 将它改写为LL(1)文法。 7.将下面的文法改写为LL(1)文法。
〈布尔表达式〉→〈布尔表达式〉∨〈布尔因子〉 〈布尔表达式〉→〈布尔因子〉
〈布尔因子〉→〈布尔因子〉∧〈布尔二次量〉
〈布尔因子〉→〈布尔二次量〉 〈布尔二次量〉〈布尔初等量〉 〈布尔二次量〉→〈布尔初等量〉 〈布尔初等量〉→(〈布尔表达式〉) 〈布尔初等量〉→true | false 8．设文法G(S):
S → S+aF | aF | +aF F → *aF | *a
(1) 消除左递归和回溯；
(2) 构造相应的FIRST和FOLLOW集合； (3) 构造预测分析表
9.对于下列的文法，试分别构造它们的LR(0)项目集规范族及识别全部活前缀的DFA。
(1) S→aSb S→aSc S→ab
(2) S→cA S→ccB A→cA A→a B→ccB B→b (3) S→aSSb S→aSSS S→c (4) S→A A→Ab A→a
10.下列文法是否为SLR(1)文法?若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。
(1) S→Sab S→bR R→S R→a
(2)S→aSAB S→BA A→aA A→B B→b (3)S→aSb S→bSa S→ab (4)S→aA S→bB A→cAd A→ε B→cBdd B→ε (5) 〈程序〉→〈分程序〉
〈程序〉→〈复合语句〉 〈分程序〉→〈分程序首部〉；〈复合尾部〉 〈分程序首部〉→begin D
〈分程序首部〉→〈分程序首部〉；D 〈复合尾部〉→Send 〈复合尾部〉→S；〈复合尾部〉 〈复合语句〉→begin〈复合尾部〉 (6) 〈程序〉→begin 〈说明表〉〈语句表〉end
〈说明表〉→〈说明表〉d； 〈说明表〉→ε
〈语句表〉→〈语句表〉；〈语句〉 〈语句表〉→〈语句〉 〈语句〉→S 〈语句〉→ε
11对于文法
S→A A→BA A→ε B→aB B→b (1) 构造LR(1)分析表；
(2) 给出用LR(1)分析表对输入符号串abab的分析过程。
12.对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。
(1)S→A A→AB A→ε B→aB B→b (2) E→E+T E→T T→(E) T→a
13.下列文法是否为LR(1)文法?若不是，能否将它们改写为等价的LR(1)文法。