编译原理复习

第一章词法分析

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)文法。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4