编译原理 第3章 词法分析与有穷自动机(第5-8讲)

1、第第3章章 词法分析与有穷自动机词法分析与有穷自动机 1 3.1 3.1 词法分析程序的功能词法分析程序的功能 所谓所谓词法词法，即构成词的规则。，即构成词的规则。 词法分析的词法分析的任务任务是对字符串表示的源程序从左到右进是对字符串表示的源程序从左到右进 行扫描和分解，根据语言的词法规则识别出一个一个行扫描和分解，根据语言的词法规则识别出一个一个 具有独立意义的单词符号。具有独立意义的单词符号。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 2 3.2 单词符号及输出单词的形式单词符号及输出单词的形式 源程序源程序 词法分析程序词法分析程序 单词符号单词符号 词法分析程序输出的单词

2、符号通常表示成如下的二词法分析程序输出的单词符号通常表示成如下的二 元式：元式： （单词种别，单词自身的值）（单词种别，单词自身的值） 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 3 3.3 语言单词符号的两种定义方式语言单词符号的两种定义方式 多数程序设计语言的单词符号都能用多数程序设计语言的单词符号都能用正规文法正规文法或或正规正规 式式来定义。来定义。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 4 正规式正规式描述了单词符号的构成规则，描述了单词符号的构成规则，正规集正规集是正规是正规 式能描述的所有的单词的集合。式能描述的所有的单词的集合。 第第3章章 词法分析与

3、有穷自动机词法分析与有穷自动机 5 练习：练习： 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 6 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 7 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 8 正规文法与正规式都是描述正规集的工具。对任意正规文法与正规式都是描述正规集的工具。对任意 一个正规文法，存在定义同一语言的正规式；反之，一个正规文法，存在定义同一语言的正规式；反之， 对每个正规式存在一个生成同一语言的正规文法。对每个正规式存在一个生成同一语言的正规文法。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 9 (1)(1)将正规文法中的每个非终结符表示成

4、关于它的一将正规文法中的每个非终结符表示成关于它的一 个正规式方程，获得一个联立方程组。个正规式方程，获得一个联立方程组。 (2)(2)依照依照求解规则求解规则: : 若若x=x|(x=x|(或或x=x+)x=x+)，则解为，则解为x=x=* *; 若若x=x|(x=x|(或或x=x+)x=x+)，则解为，则解为x=x=* *; ; 以及正规式的分配律、交换律和结合律求关于文法以及正规式的分配律、交换律和结合律求关于文法 开始符号的正规式方程组的解开始符号的正规式方程组的解. . 这个解是关于该这个解是关于该文法开始符号文法开始符号S S的一个正规式，显然的一个正规式，显然 它表示了由该正规文

5、法所描述的语言。它表示了由该正规文法所描述的语言。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 10 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 11 练习练习 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 12 P28 (9)P28 (9) 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 13 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 14 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 15 3.4 正规式与有穷自动机正规式与有穷自动机 有穷自动机是词法的识别工具，它的功能是：寻有穷自动机是词法的识别工具，它的功能是：寻 找（匹配）符合正

6、规式要求的字符串，根据正规找（匹配）符合正规式要求的字符串，根据正规 式确定正规集。式确定正规集。 有穷自动机是描述特定类型算法的数学模型，可有穷自动机是描述特定类型算法的数学模型，可 分为确定性有穷自动机分为确定性有穷自动机(DFA)(DFA)和非确定性有穷自动和非确定性有穷自动 机机(NFA)(NFA)。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 16 数学定义（五元组形式）：严密；数学定义（五元组形式）：严密； 状态转换表：面向编程。状态转换表：面向编程。 状态转移图：直观；状态转移图：直观； 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 17 第第3章章 词法分析与

7、有穷自动机词法分析与有穷自动机 18 12 3 letter letter digit other other any 状态状态 状态转移状态转移 初始状态初始状态 接受状态接受状态 av3fk /0 as+67/0 两字符串两字符串 的识别过的识别过 程：程： 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 19 DFA M是一个五元组（是一个五元组（ , , ） 确定性有穷自动机确定性有穷自动机(DFA)(DFA)：下一状态由当前状态和当前输：下一状态由当前状态和当前输 入字符唯一给出的自动机。（取决于入字符唯一给出的自动机。（取决于f f） 数学定义数学定义 例：例： M=(Q,

8、, ) 其中：其中： f= Q Q 是如下的函是如下的函 数：数： f(1,a)=2，f(1,z)=2 f(1,A)=2，f(1,Z)=2 f(2,a)=2，f(2,z)=2 f(2,A)=2，f(2,Z)=2 f(2,0)=2f(2,9)=2 f(1,0)=3f(1,9)=3 f(3,a)=3f(3,z)=3 f(3,A)=3f(3,Z)=3 12 3 letter letter digit other other any 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 21 它所对应的状态表如图：它所对应的状态表如图： 一个一个DFADFA可用一个矩阵表示，该矩阵的行表示状态，列表示

9、可用一个矩阵表示，该矩阵的行表示状态，列表示 输入字符，矩阵元素表示输入字符，矩阵元素表示T(s,a)T(s,a)的值，这个矩阵称的值，这个矩阵称 状态转移矩阵）。状态转移矩阵）。 状态状态ab接受接受 012否否 132否否 213否否 333是是 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 22 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 23 给定给定DFA MDFA M，对于字符，对于字符c1,c2,c1,c2,cn,cn,当以下条件成立时，当以下条件成立时， 称称M M接受由接受由c1,c2,c1,c2,cn,cn组成的字符串组成的字符串c1c2c1c2cncn：

10、 存在状态序列存在状态序列s0,s1,s2,s0,s1,s2,sn,sn,使得使得s1=f(S,c1), s1=f(S,c1), s2=f(s1,c2),s2=f(s1,c2),sn=f(sn-1,cn),sn=f(sn-1,cn)，且，且snsnZ Z。 例：判断例：判断abbbbaabbbba是否是上页是否是上页DFA MDFA M所定义的语言所定义的语言 由由DFA MDFA M接受的语言接受的语言L(M)L(M)是所有是所有M M接受的字符串组成的集接受的字符串组成的集 合。合。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 24 NFA MNFA M也是一个五元组（也是一个五

11、元组（ , , , , ） 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 25 转换函数转换函数T T初态初态 NFA M (S,T,S0,F) S S ( ( U)U) SS的子集的子集 多值映射多值映射 S S0 0 S S 非空初态非空初态 DFA M (S,T,s0,F) S SSS的元素的元素 单值映射单值映射 s s0 0SS 唯一的初态唯一的初态 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 26 判断下图是判断下图是DFADFA还是还是NFANFA的状态转换图，并的状态转换图，并 写出其他写出其他2 2种表示形式种表示形式 第第3章章 词法分析与有穷自动机词法分

12、析与有穷自动机 27 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 28 2、若、若r,s为正规式：为正规式： 123 r s s r 13 rs r|s r* 例：构造与正规表达式例：构造与正规表达式 R=abR=ab* *a(a|b)a(a|b)* *等价的等价的NFANFA。 1 r 32 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 29 (a|b)* (aa|bb) (a|b)* P55 3.1(1)(2) 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 30 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 31 第第3章章 词法分析与有穷自动机词法分析与

13、有穷自动机 32 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 33 初态初态 DFA的的 状态状态 P42 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 34 包含包含NFA终终 态的状态子态的状态子 集全都是集全都是 DFA的终态。的终态。 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 35 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 36 v将所有将所有DFA的终态与其它状态划分成两个子集的终态与其它状态划分成两个子集G1,G2; v分别从两个子集分别从两个子集G1,G2中寻找不等价状态进行分割。中寻找不等价状态进行分割。 第第3章章 词法分析与有穷自动

14、机词法分析与有穷自动机 37 将所有 DFA的 终态与 其它状 态划分 成两个 子集 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 38 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 39 0 0 5 3 1 1 2 4 0,1 1 0,1 0,1 0 1 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 40 有一台自动售货机，接受有一台自动售货机，接受1 1分和分和2 2分硬币，出售分硬币，出售3 3分一块分一块 儿的硬糖。顾客每次向机器中投放儿的硬糖。顾客每次向机器中投放3 3分的硬币，便分的硬币，便 可得到一块糖（注意：只给一块并且不找钱）。清为可得到一块糖（注意：

15、只给一块并且不找钱）。清为 自动售货机编制程序使其能够正确售出货物。自动售货机编制程序使其能够正确售出货物。 （1 1）写出售货机售糖的正规表达式；）写出售货机售糖的正规表达式； （2 2）构造识别上述正规式的最简）构造识别上述正规式的最简DFADFA。 （3 3）将该）将该DFADFA用代码实现。用代码实现。 设顾客投入设顾客投入1 1分硬币用分硬币用a a表示，表示，2 2分硬币用分硬币用b b表示，则售表示，则售 货机售糖的正规表达式为：货机售糖的正规表达式为： a(a(a|b)|b)|b(a|b) DFA与代码（略）与代码（略） 简单应用举例：简单应用举例： 第第3章章 词法分析与有穷

16、自动机词法分析与有穷自动机 41 b ba b 7 2 3 86145 b b a 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 42 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 43 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 44 有穷自动机到正规式的转换有穷自动机到正规式的转换 P46 转换规则：转换规则： (1)添加结点，保证只有一个初态结点和一个终态结点；添加结点，保证只有一个初态结点和一个终态结点； (2)逐步消去中间结点。逐步消去中间结点。 例：例：P46 图图3.19 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 45 第第3章章 词法分析与

17、有穷自动机词法分析与有穷自动机 46 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 47 复习复习 规则：若规则：若x=x|(或或x=x+)，则解为，则解为x=*; 若若x=x|(或或x=x+)，则解为，则解为x=*; 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 48 复习复习 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 49 3.5 正规文法与有穷自动机正规文法与有穷自动机 例：例： 算法：算法： 算法：算法： 第第3章章 词法分析与有穷自动机词法分析与有穷自动机 52 (1) 右线性文法右线性文法 增加终态；增加终态； 左线性文法左线性文法 增加初态增加初态 解方程组，若解方程组，若 x=x+，则，则 x=*; Aab 转换成转换成AaB和和Bb Aa*b转换成转换成AaA|b; 练习练习1：将该有穷自动机转换成等价的正规文法：将该有穷自动机转换成等价的正规文法G 练习练习2：将下列正规文法：将下列正规文法G转换成等价的正规式转换成等价的正规式 练习练习2的正规文法：的正规文法： S 练习练习3：给出下列文法对应的最小的：给出下列文法对应的最小的DFA SaS | bA | b AaS 练习练习4：构造正规式：构造正规式1(0|1)*101相应的相应的DFA。 第第3章章 词法分析与有穷自动机词法分析与有