编译原理各章习题.pdf

编译原理各章习题

第⼆章⾼级语⾔及其语法描述

1、设有⽂法G[S]：

S→N

N→D|ND

D→0|1|2|…|9

试写出028和4321的最左推导和最右推导过程。

2、证明⽂法G[S]是⼆义性⽂法：

S→ifEthenSelseS|ifEthenS|s

E→0|1

3、设有⽂法G[E]：

E→E-T|T

T→T/F|F

F→i|(E)

（1）试写出i/(i-i-i)的推导树。

（2）试写出（F-i）/F的短语、简单短语和句柄。

4、设∑={0,1}，请给出∑上下列语⾔的⽂法（1）所有以0开头的串

（2）所有以0开头，以1结尾的串

5、证明⽂法G1和G2等价

G1：S→0S1，S→01

G2：A→0R，A→01，R→A1

第三章有限状态⾃动机和词法分析

1、请⽤中⽂描述下列正规式表⽰的正规集

（1）0(0|1)*0

（2）0*10*10*10*

2、试写出∑＝{0，1}上下列集合的正则表达式：（1）所有以1开始和结束的符号串。

（2）恰含有3个1的所有符号所组成的集合。（3）集合{01，1}。

（4）所有以111结束的符号串。

3、试写出∑＝{0，1}上下述集合的正则表达式：（1）试写出⾮负整数集的正则表达式。

（2）试写出以⾮5数字为头的所有⾮负整数集的正则表达式。4、试将图3.1中所⽰的有限状态⾃动机M最⼩化。
图3.1M的状态转换图

5、设∑＝{a,b}，试构造下述正则表达式的确定性有限状态⾃动机：（1）a(a|b)*baa（2）(a|b)*bbb*

6、对于下列的状态转换矩阵：

（1）分别画出相应的状态转换图。

（2）⽤⾃然语⾔分别描述它们所识别的输⼊串的特征7、将图3.2所⽰的⾮确定的有限状态⾃动机确定化和最⼩化。

图3.2⾮确定的有限状态⾃动机M

第四章⾃顶向下语法分析1、从下列⽂法中消去左递归。

（1）S→Aa|b

A→Ac|Sd

（2）A→A∨B|B

B→B∧C|C

C→?D|D

D→(A)|i

2、请消去下⾯⽂法G[S]中的回溯

G[S]：S→aBc|a

B→bB|ε

3、有⽂法G[S]：

S→AB

A→a|ε

B→b|ε

（1）验证该⽂法是LL(1)⽂法；

（2）请构造预测分析表

4、考虑⽂法G[A]：
A→aABc|d|ε

B→Bb|b

（1）改写为LL(1)⽂法；

（2）请构造预测分析表

（3）给出句⼦adbc的分析过程

第五章⾃底向上语法分析

1、请对下列⽂法G[S]构造算符优先分析表

S→bAb

A→(B|a

B→Aa)

2、⽂法G[S]：

S→S(Sa

S→b

该⽂法是LR(0)还是SLR(1)⽂法？

3、⽂法G[A]：

A→(A)|a

构造该⽂法的LR(0)分析表，并请描述((a))的分析过程。

4、⽂法G[S]:

S→(S)

S→

（1）这个⽂法是例如LR(0)⽂法吗？若是，请构造该⽂法的LR(0)分析表。（2）这个⽂法是例如SLR(1)⽂法吗？若是，请构
造该⽂法的SLR分析表。（3）构造该⽂法识别活前缀的DFA