第4章词法(1-6)案例.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 根据样本S语言的定义， 一个合法的程序如下： { int a; int b; a=10; if (a0) then b=a } * 一个简单的词法分析器的设计与实现 2．样本S语言的单词类别及内部表示 文法中的终极符是语言的单词，单词的类别以助记符的形式在文法中表现出来。文法的非终极符是语法单位名称，如语句、算术表达式等。 保留字：int、if、then、else、while、do。 标识符：用助记符(或称为单词记号） ID 表示。 常数： 用助记符　NUM　表示。 算术运算符：+、- 、*、/。 逻辑运算符：and、or。 关系运算符：、、=、=、!= 、= = 　　　　　　用助记符　relop　表示。 分隔符：{、}、 ；、（、 ）、=。 * * 一个简单的词法分析器的设计与实现 3．样本S语言的单词识别的状态转换图 每个单词的识别都从初始状态开始，如果把状态转换图看成一个函数，则每次调用只能识别出一个单词。 对于保留字这类单词，并不专设对应的状态转换图，而是事先存在保留字表中。每识别出一个标识符，就去查保留字表，若匹配成功，则该标识符是一个保留字，否则就是一个标识符。 * * （ID，标识符名）或（保留字，_ ） 返回（NUM，常数值） （+，_）或（- ，_）或（*，_）或（/，_）或（and，_）或（or，_） 　或（（，_）或（ ），_） 或（{，_）或（}，_）或（；，_） （relop，=）或（relop ，=）或（relop，!=） （relop，）或（relop，）或 　“ ! 是非法字符” 返回（relop，= =）， 返回（=，_） 返回 “非法字符” * * * * * * * * * * * * * * * * * * * * * * * * * * * 4. 5.2 正则式R构造等价的NFA M （1）引进两个状态x和y，x是NFA M的开始状态，y是终止状态，x引向y的弧上标记为正则式R，即把正则式表示成拓广转换图。 （2）运用如下的三条转换规则不断加入新结点进行分解，直到每个弧的标记只是VT中的一个字符或ε为止，所得的NFA M即为所求。 正则式R到NFA M的转换规则 ? 1 β 2 ?| β 1 2 ? 1 β 3 2 ? β 1 2 ? 1 ? 3 2 ? ?* 1 2 若有 若有 若有 代之为： 代之为： 代之为： * 例：已知正则式r=b*(d|ad)(b|ad)+，构造等价的NFA M。 解： 因为R+=RR*原来正则式改造为：b*(d|ad)(b|ad)(b|ad)* 构造NFA M 的步骤见图(a)~(c)。 正则式构造NFA M (c) x y b*(d|ad)(b|ad)(b|ad)* x y b* 1 2 d | ad 3 b | ad (b | ad)* (a) (b) x ? d a d 4 b 2 5 ? 1 d a 3 6 d a 8 ? 7 b ? y b d * 例：已知正则式r= 1 (01)*(0* | 1* ) 0 ，构造等价的NFA M。 解：根据正则式定义语言的特征，可以使NFA M的状态图更简化。 NFA M S 1 D E 0 1 A 0 B 1 C 0 ? ? 0 * 4.6 DFA的化简 (DFA的最小化） 在编译程序中，扫描器的效率是很重要的，如果可能的话，应该使构造的DFA最小（即状态数最少）。 实际上，对于任何给定的DFA，都有与之等价且具有最小状态数的DFA存在，并且是唯一的. * DFA的最小化的例子 A a B b b a a S B S a b a 最小化的DFA * 一. 定义 1.化简的FA：是指没有多余状态且状态中没有两个是互相等价的。 2.多余状态：从DFA的开始状态出发，任何输入串也不能到达的那个状态。 3.在DFA中，状态s和t状态等价的条件是： （1）一致性条件——s和t必须同时为可接受态或不可接受态。 （2）蔓延性条件——对于所有输入符号， s和t必须转换到等价的状态集里。 如果DFA的状态s和t不等价，则称s和t是可区分的。 * 二. 分割法将DF