第4章 词法分析
重点内容：正规式转化为DFA
a、 正规式->NFA
b、 NFA -> DFA（子集法）
c、 DFA化简（分割法）
题目1：课件例题：
a、 为 R=(a|b)*(aa|bb)(a|b)*构造 NFA
b、 从NFA构造DFA的算法
c、 化简
题目2：
4.7 例1：构造正规式相应的DFA：1(0|1)*101
按照以下三步：
（1）由正规表达式构造转换系统（NFA）
（2）由转换系统（NFA）构造确定的有穷自动机DFA
（3）DFA的最小化
答：（1）构造与1(0|1)*101等价的 NFA
（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
B
C
B
C
A
D
D
C
B
1、将M的状态分成非终态和终态集{X,A,B,C}和{D}。
2、寻子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。
最后生成DFA：
题目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的转换表：
a
b
S
A
Q
A
A
B,Z
B,Z
Q
D
Q
Q
D,Z
D
A
B
D,Z
A
D
B
Q
D
4、子集法重命名状态：（上标0：初态，*：终态）
a
b
00
1
3
1
1
2
2*
3
4
3
3
5
4
1
6
5*
1
4
6
3
4

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#
（1）消除G的左递归得到文法 G‘
E→TE '   
E'→+TE'│ε
T→FT '   
T'→*FT'│ε
F→(E)│i   
（2）求出每个产生式的select集,G’是LL(1)文法
SELECT(E→TE' ) = { (,i }        SELECT(E'→+TE' ) = { + }
SELECT(E'→ε ) = { ),# }        SELECT(T→FT' ) = { (,i }
SELECT(T'→*FT' ) = { * }        SELECT(T'→ε ) = { +,),# }
SELECT(F→(E) ) = { ( }        SELECT(F→ i ) = { i }
（3）依照选择集合把产生式填入分析表
注：表中空白处为出错
题目2：
作业、习题5.1：消除左递归+判定+分析
G[S]:S->a|^|(T)  T->T,S|S
d、分析输入串（a,a）#   
文法G[S]:S->a|^|(T)，T->T,S|S
(1) 给出对(a,(a,a))的最左推导
(2) 改写文法，去除左递归
(3) 判断新文法是否LL1文法，如是，给出其预测分析表
(4) 给出输入串（a,a）#的分析过程，判断其是否文法G的句子 。
答：（1）对(a,(a,a))的最左推导为：
  S=>(T)
=>(T,S)
=>(S,S)
=>(a,S)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。