编译原理复习
- 格式：doc
- 大小：145.00 KB
- 文档页数：8
第一章词法分析
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)最小化
01a,baa021435bbaaaabbbbaa
(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)文法。
(1) E→E+E E→E*E E→i
(2) S→aSa S→bSb S→a S→b
(3) S→V∶=E S→LS L→I: V→I
(4) 〈程序〉→begin〈说明表〉；〈语句表〉end
〈说明表〉→d;〈说明表〉
〈说明表〉→d
〈语句表〉→S;〈语句表〉
〈语句表〉→S
14.设已给文法G［S］:
S→AaAb S→BbBa A→e B→ε
试证明G是LL(1)文法，但不是SLR(1)文法。
15.设已给文法
(1) G1［S］：
S→Aa|bAc|dc|bda
A→d
(2) G2［S］：
S→Aa|bAc|Bc|bBa
A→d
B→d
试证明： G1是LALR(1)文法但不是SLR(1)文法；G2是LR(1)文法但不是LALR(1)文法。
16.试为如下的文法构造LALR(1)分析表。
E→E+T|T T→TF|F F→F*|a|b
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27、他的命是我的，你想要，不给你。
28、诞生于想象之中，流传于口舌之上，欲望，永远存在，生生不息。
29、我，还会回来的。
30、人活着就会失去。你失去的不会再来，你争取的永远都会失去。
31、死亡与夜色为友，揭开了黄泉的一角，寄予这生命，时机一到，他便降临到你身边。
32、就为了这么一点点的美丽，她们可以放弃友情，亲情，爱情…这就是，所谓的TM的人性#
世界脏到羞耻，谁有资格说难过。
创伤，也是一种成熟的象征。
你知道被迷惑，说明你尚且清醒，当你不知道迷惑时，才是最可怜的。
狂妄的人有救，自卑的人没法救。
伤害别人并不能掩盖自己的缺点，不过是自欺欺人罢了。
内心各种小心算计，心中不坦白，表达颠三倒四，五官又怎么端正。
多讲点笑话，以幽默的态度处事，这样子日子会好过一点。
活在别人的赞扬与掌声中，终究会成为一个敏感脆弱的人。
沉默是毁谤最好的答覆。
对人恭敬，
无私奉献的爱心，让你拥有一切。
仇恨的心无法被治愈，只有宽容才能化解仇恨，饶过别人就是饶过自己。
接受眼前的现实，你才能超越现实。
