编译原理_03词法剖析.ppt

几类单词的描述 标识符： 〈标识符〉→l | l〈字母数字〉 〈字母数字〉→l | d | l〈字母数字〉| d〈字母数字〉 无符号整数：〈无符号整数〉→d | d〈无符号整数〉 运算符：〈运算符〉→ + | - | * | / | = | =| =…… 界符：〈界符〉→ , | ; | ( | ) |…… 无符号实数：〈无符号实数〉→ d 〈余留无符号数〉| . 〈十进小数〉| e〈指数部分〉〈余留无符号数〉→ d 〈余留无符号数〉| . 〈十进小数〉| e〈指数部分〉|ε〈十进小数〉 → d 〈余留十进小数〉〈余留十进小数〉 → e〈指数部分〉| d 〈余留十进小数〉| ε〈指数部分〉 → d 〈余留整指数〉| s〈整指数〉〈整指数〉 → d 〈余留整指数〉〈余留整指数〉 → d 〈余留整指数〉 |ε其中s表示正或负号。 如 125.55e+15 和 232.147 例：如图所示NFA M，求正规式R 构造规则如下： ①字母表与G的终结符集相同；②为G中的每个非终结符生成M的一个状态， G 的开始符号是初态S； ③增加一个新状态Z，作为NFA的终态；④对G中的形如A→tB的产生式（其中t为终结符或ε，A和B为非终结符），构造M的一个转换函数f(A,t)=B；⑤对G中形如A→t的产生式，构造M的一个转换函数f(A,t)=Z。 转换规则非常简单： ①对转换函数f(A,t)=B ，可构造产生式A→tB； ②对终态Z ，增加产生式Z → ε ； ③有穷自动机的初态对应文法的开始符号； ④有穷自动机的字母表对应文法的终结符集； 4.5 正规文法和有穷自动机间的转换 正规文法转换为有穷自动机 例：已知正规文法G如下，试构造等价的NFA N，使得L(N)=L(G) G[s]: S?aA S?bB S? ε A?aB A ?bA B?aS B?bA B? ε 解：应用上述规则可得等价NFA如右图 S A B Z ε a a a b b b ε ? 有穷自动机转换为正规文法 下面我们来看一个具体的例子 例：证明t=baab被如下的DFA所接受。 DFA M=（{S,U,V,Q}, {a,b}, f, S, {Q}）其中 f 定义为： f（S，a）=U，f（V，a）=U f（S，b）=V，f（v，b）=Q，f（U，a）=Q f（Q，a）=Q，f（U，b）=V，f（Q，b）=Q b S U V a a a b a , b b Q 证明如下： f（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f（Q，b）=Q Q属于终态。得证。 我们把DFA M所能接受的字符串的全体记为L（M）称为语言 （也即句子的集合） 3. DFA的确定性： 当f：k×Σ→K是一个单值函数，即对任何状态K?R，输入符号a ? K，f(k,a)唯一确定下一状态。 　　“确定”的含义：下一个输入字符唯一地确定了下一个当前状态． 二. 不确定的有穷自动机NFA 一个不确定的有穷自动机NFA M是一个五元组:：M=（K，Σ，f，S，Z），其中 ① K是一个有穷集，每个元素表示一个状态； ②Σ是一个有穷字母表，每个元素是一个输入字符； ③ f是一个从K×Σ*到K上的子集的映象； ④ S?K，是一个非空初态集； ⑤ Z ?K，是一个终态集。 例：已知NFA， M＝({0,1,2,3,4},{a,b},f,{0},{2,4}) 其中：f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1} f(3,a)={4} f(1,b)={2} f(4,a)={4} f(2,a)={2} f(4,b)={4} 状态图表示如下： 说明： DFA是NFA的特例 对于每个NFA M，存在一个DFA M