编译原理第四讲剖析.pptx

本节内容 有穷自动机 带空字符的有穷自动机 NFA到DFA的转换 正则集、正则文法和正则表达式 带ε动作的FA 定义：如果FA的弧上允许标记ε，既允许自动机对ε作状态转移，则称为ε自动机，记为 εNFA或εDFA 引入ε动作的意义 为了把识别各类单词的有穷自动机用ε矢线连接起来，组成一个单一的εNFA，再把所得到的εNFA确定化，再据此设计词法分析器 带ε动作的FA 例子 f o r f i ε ε 0 1 2 3 4 5 6 7 带ε动作的FA a b c s0 s1 s2 s3 ε ε ε c NFA到DFA的变换 NFA具有不确定性，因此通常需要构造一个等价的DFA，我们把接受同一语言的任何两个FA称作等价的FA，即：L(M)=L(N) 由NFA构造DFA的基本思想 算法：子集法 NFA到DFA的变换 预备知识： 状态的ε-闭包ε-closure(q) 状态集的ε闭包ε-closure(I) NFA到DFA的变换 例子： 教材P28 0 1 4 2 3 5 6 7 8 9 10 ε ε ε ε ε ε ε a b b ε b a 正则表达式 正则集 正则文法 正则表达式的作用 通过正则表达式来描述各种词法单元的模式。 正则表达式所表示的集合称为正则集 正则表达式与正则文法的等价性 正则表达式的非形式化描述 正则表达式及对应正则集的定义（递归） 设∑是一个字母表， ⑴ Φ是∑上的RE，L(Φ)=Φ； ⑵ ε是∑上的RE，L(ε)={ε}； ⑶ 对于a∈∑，a是RE，L(a)={a}； ⑷如果r和s是RE，L(r)=R,L(s)=S，则： r与s的“或（并）” (r|s)是RE，L(r|s)=R∪S； r与s的“连接” (rs)是RE，L(rs)=RS； r的闭包(r*)是RE，L(r*)=R*。 ⑸ 只有满足⑴、⑵、⑶、⑷的才是RE。 运算的优先级 正则表达式的例子 例：教材 P30 正则表达式的等价 正则文法到正则表达式的转换 正则文法到正则表达式的转换 例3.6，教材p32