q1={0,1} q2={1} DFA:
{0,1} {0} {1} Φ a a q0 b q2 3.5
将图3.37的DFA化简。
q1 a b 0 a 1 a 解： 划分 {0,1} {2,3,4,5} 划分 {0,1} {2,4} {3,5} b a a b 2 4 b b b b a 3 a 5
图3.37 DFA状态图
a {1} {1,0,3,5} a {1} {0,1} {3,5} q2={3,5}
b {2,4} {3,5,2,4} b {2,4} {3,5} {2,4} q0={0,1} q1={2,4} 化简后的DFA：
b a q0 a
4.1 对下面文法，设计递归下降分析程序。 S→aAS|(A) , A→Ab|c
解：首先将左递归去掉，将规则A→Ab|c 改成 A→c{b} 非终结符号S的分析程序如下：
b q1 b q2 a
过程S N INPUTSYM=’a’ Y INPUTSYM=下一个符号 INPUTSYM=’(’ Y INPUTSYM=下一个符号 N 错误 过程A 过程A N INPUTSYM=’)’ Y INPUTSYM=下一个符号 错误 过程S 出口 非终结符号A的分析程序如下：
过程A INPUTSYM=’c’ Y INPUTSYM=下一个符号 N 错误 INPUTSYM=下一个符号 INPUTSYM=’b’ Y N 出口
4.2 设有文法G[Z]： Z∷=(A) , A∷=a|Bb , B∷=Aab
若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？
解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A
∷=a|Bb和规则B∷=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件（1）（书P67），且规则 A: := a|Bb，FIRST(a)={a}，FIRST(Bb)={a}，即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（2）（书P67），在分析过程中，将造成回溯。 改写文法可避免回溯：
将规则B∷=Aab代入规则A∷=a|Bb得：A∷=a|Aabb，再转换成：A∷=a{abb}，可避免回溯。
4.3 若有文法如下，设计递归下降分析程序。 <语句>→<语句><赋值语句>|ε <赋值语句>→ID=<表达式>
<表达式>→<项>|<表达式>＋<项>|<表达式>－<项> <项>→<因子>|<项>*<因子>|<项>/<因子> <因子>→ID|NUM|(<表达式>)
解：首先，去掉左递归
<语句>→<语句><赋值语句>|ε改为： <语句>→{<赋值语句>} <表达式>→<项> | <表达式> + <项> | <表达式> - <项> 改为： <表达式>→<项>{（+ | -）<项>}
<项>→<因子> | <项> * <因子> | <项> / <因子> 改为： <项>→<因子>{（* | /）<因子>}
则文法变为：
<语句>→{<赋值语句>} <赋值语句>→ID=<表达式> <表达式>→<项>{（+ | -）<项>} <项>→<因子>{（* | /）<因子>} <因子>→ID|NUM|(<表达式>) 非终结符号 <语句> 的分析程序如下： <语句>→{<赋值语句>} 语句 FIRST(<赋值语句>)={ID} N INPUTSYM=’ID’ Y 赋值语句 出口
非终结符号 <赋值语句> 的分析程序如下：
<赋值语句>→ ID=<表达式>
赋值语句 N INPUTSYM=’ID’ INPUTSYM=下一个符号 N INPUTSYM=’=’ Y INPUTSYM=下一个符号 错误 错误 表达式 出口
非终结符号 <表达式> 的分析程序如下：
<表达式>→<项>{（+ | -）<项>} 表达式 项 INPUTSYM=下一个符号 Y INPUTSYM=’+’ N Y INPUTSYM=’-’ N 出口