编译原理与实现03第3章词法分析1.pptVIP

3.5 正则表达式 3.5.1 正则表达式定义 3.5.1 正则表达式定义 3.5.1 正则表达式定义 3.5.1 正则表达式定义 3.5.2 正则文法与正则表达式的等价性 3.5.2 正则文法与正则表达式的等价性 3.6 有穷自动机（FA） 3.6.1 确定的有穷自动机 3.6.1 确定的有穷自动机 3.6.1 确定的有穷自动机 3.6.1 确定的有穷自动机 3.6.1 确定的有穷自动机 3.6.2 不确定的有穷自动机 3.6.2 不确定的有穷自动机 3.6.2 不确定的有穷自动机 3.6.2 不确定的有穷自动机 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.3 NFA到DFA 的转化 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.5 确定的有穷自动机的化简 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.4 正则表达式与有穷自动机的等价性 3.6.6 根据DFA构造词法分析程序 3.6.6 根据DFA构造词法分析程序 3.6.6 根据DFA构造词法分析程序 3.7 词法分析程序的自动生成器LEX 3.7 词法分析程序的自动生成器LEX 习题 ② 选择：设R1 和R2 都是正则表达式，去掉标记为R1和R2弧线，用一根弧线直接连接结点1和2，弧线上标记R1|R2： ③重复：设R是正则表达式，则构造与正则表达式{R}等价的NFA如图3.27所示： 1 2 R1|R2 1 2 R1 R2 图3.26由NFA构造正则表达式R1|R2 1 3 {R} 1 2 3 ε ε R 图3.27由NFA构造正则表达式{R} 例如，从例3.13中得到的NFA M（图3.23）反向看，图3.23、图3.22、图3.21以及图3.20就是构造正则表达式的过程。 如果有两个确定的有穷自动机DFA M1和DFA M2所接受的语言完全一样，我们说这两个自动机是等价的。但如果DFA M1的状态个数比DFA M2的状态个数少，那么，我们说DFA M1更加简洁。在设计词法分析程序时，效率是很重要的一个因数。如果可能的话，我们应该构造尽可能小的DFA。上一小节我们介绍了将正则表达式分解派生出DFA的方法，但这一方法有个缺点：就是生成的DFA可能比较复杂。自动机理论中有一个很重要的结论：对于任何给定的DFA，都有一个含有最少状态的等价的DFA，而且这个最少状态的DFA是唯一的。从任何DFA中都可以得到这个最少状态的DFA。 1、???? 等价状态与不等价状态 在一个确定的有穷自动机里，如果从S1状态出发接受的所有符号串集合与从S2状态出发接受的所有符号串集合一样，那么称状态S1和S2是等价的；否则是不等价的。 例3.14，观察图3.27所示的状态图，判断状态1和状态2是否等价。 解：因为有δ(1,a)=3，δ(2,a)=3，因此，状态1和状态2是等价的。 0 2 1 3 4 a b a a b 图3.28有等价状态的状态图 2.多余状态 多余状态有两种。一是指从初始状态出发，输入任何输入串也无法到达的状态，即从初始状态到该状态之间没有通路。二是指从初始状态出发能够到达的状态，但从它出发却无法到达终止状态的状态，即从该状态到终止状态之间没有通路。多余状态是无用的，应该删除。删除多余状态的方法很简单，从状态图上看，就是直接将多余状态结点以及相关的弧线删除，即可得到等价的自动机。 例3.15，在图3.28(a)所示的的状态图中，判断那些状态是多余状态。 解：根据多余状态的定义，可发现，从初始状态0出发，无法到达状态1，所以状态1是多余状态。而从状态5无法到达终止状态4，所以，状态5也是多余状态。删除多余状态后的状态图入3.28(b)所示。 0 1 2 3 4 5 b b b a a 0 2 3 4 b b a 图3.29(a) 有多余状态的状态图 图3.29(b) 删除多余状态的状态图 3.DFA化简算法 设DFA M= （Q，∑ ，δ ，q0，F），化简算法如下： 1）先将自动机的状态划分成终止状态集合S1和非终止状态集合S2