第二章高级语言及其语法描述
1、设有文法G[S]：
S→N
N→D|ND
D→0|1|2|…|9
试写出028和4321的最左推导和最右推导过程。
2、证明文法G[S]是二义性文法：
S→if E then S else S |if E then S |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.1 M 的状态转换图
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→A a)
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。