缂栬瘧鍘熺悊澶嶄範棰樼洰闆嗙瓟妗堣В鏋?- 鐧惧害鏂囧簱

第4章 词法分析

重点内容：正规式转化为DFA a、 正规式->NFA

b、 NFA -> DFA（子集法） c、 DFA化简（分割法） 题目1：课件例题：

a、 为 R=(a|b)*(aa|bb)(a|b)*构造 NFA

b、 从NFA构造DFA的算法

c、 化简

1

题目2：

4.7 例1：构造正规式相应的DFA：1(0|1)*101 按照以下三步：

（1）由正规表达式构造转换系统（NFA）

（2）由转换系统（NFA）构造确定的有穷自动机DFA （3）DFA的最小化 答：（1）构造与1(0|1)*101等价的 NFA

X 1(0|1)*101 Y 1 (0|1)* 1 0 1 X A B C D Y 0,1 1 1 0 1 X A B C Y

（2）将NFA转换成DFA：采用子集法，即DFA的每个状态对应NFA的一个状态集合： 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB

除X，A外，重新命名其他状态：

0 1 X A A A B

2

B C D C A C B D B 1、将M的状态分成非终态和终态集{X,A,B,C}和{D}。

2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。 最后生成DFA：

0 0 1 X A 1 1 B 0 C 1

1 D 0

题目3：自习、书本练习4.7，参考答案见《z4 书本练习4.7.doc》 已知文法G[S]：

S→aA|bQ A→aA|bB|b B→bD|aQ Q→aQ|bD|b E→aB|bF F→bD|aE|b 1、 构由于不可到达，去除E、F相关的多余产生式 2、 由新的G[S]构造NFA如下

3、 NFA的转换表： S A B,Z Q D D,Z B a A A Q Q A A Q b Q B,Z D D,Z B D D 0 1 2 3 4 5 6 **01 1 3 3 1 1 3 3 2 4 5 6 4 4

4、子集法重命名状态：（上标0：初态，*：终态）

a b 3

5、使用分割法化简以上DFA G：

5.1 令G={(0,1,3,4,6),(2,5)}// 分别为非终态和终态集 5.2 由{0,1,3,4,6}a={1,3}，{0,1,3,4,6}b={3,2,5,6,4}

将{0,1,3,4,6}划分为 {0,4,6}{1,3}，得G={(0,4,6),(1,3),(2,5)}

5.3 由{0,4,6}b={3,6,4}，将之划分为{0},{4,6}，得G={(0),(4,6),(1,3),(2,5)} 5.4 观察后，G中状态不可再分，为最小化DFA。

6、分别用 0，4，1，2代表各状态，DFA状态转换图如下：

造相应的最小的DFA

第5章 自顶向下的语法分析 重点内容：LL（1）文法

a、 去除左递归

b、 LL（1）文法的判定（first、follow、select集） c、 预测分析表

d、 使用栈和预测分析表对输入串的分析

题目1：课件例题：消除左递归+判定+分析 算术表达式文法G

E→E+T│T T→T*F│F F→(E)│I

d、分析输入串i+i*i#

4