编译原理词法分析2.ppt

《编译原理词法分析2.ppt》由会员分享，可在线阅读，更多相关《编译原理词法分析2.ppt（72页珍藏版）》请在三一办公上搜索。

1、第二章 词法分析,本章内容词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念,2.1 词法记号及属性,2.1.1 词法记号、模式、词法单元 记号名词法单元例举模式的非形式描述 if if 字符i,f for for字符f,o,r relation,=,=,或=或=或 id sum,count,D5由字母开头的字母数字串 number 3.1,10,2.8 E12任何数值常数 literal“seg.error”引号“和”之间的任意字符串，但引号本身除外,2.1 词法记号及属性,历史上词法定义中的一些问题忽略

2、空格带来的困难DO 8 I 3.75 DO8I 3.75 DO 8 I 3,75 关键字不保留IF THEN THEN THEN=ELSE；ELSE 关键字、保留字和标准标识符的区别保留字是语言预先确定了含义的词法单元标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义,2.1 词法记号及属性,2.1.2 词法记号的属性 position=initial+rate 60的记号和属性值：id，指向符号表中position条目的指针assign _ opid，指向符号表中initial条目的指针add_opid，指向符号表中rate条目的指针mul_ opnumber，整数值60,2.

3、1 词法记号及属性,2.1.3 词法错误词法分析器对源程序采取非常局部的观点例：难以发现下面的错误fi(a=f(x)在实数是a.b格式下，可以发现下面的错误123.x紧急方式的错误恢复删掉当前若干个字符，直至能读出正确的记号错误修补进行增、删、替换和交换字符的尝试,2.2 词法记号的描述与识别,2.2.1 串和语言字母表：符号的有限集合，例：=0,1串：符号的有穷序列，例：0110,语言：字母表上的一个串集,0,00,000,句子：属于语言的串串的运算连接（积）xy，s=s=s 幂s0为，si为si-1s（i 0）,2.2 词法记号的描述与识别,语言的运算并：L M=s|s L 或 s M 连

4、接：LM=st|s L 且 t M幂：L0是，Li是Li-1L 闭包：L=L0 L1 L2 正闭包：L+=L1 L2 例L:A,B,Z,a,b,z,D:0,1,9 L D,LD,L6,L*,L(L D)*,D+,2.2 词法记号的描述与识别,2.2.2 正规式正规式用来表示简单的语言，叫做正规集正规式定义的语言备注aa a(r)|(s)L(r)L(s)r和s是正规式(r)(s)L(r)L(s)r和s是正规式(r)*(L(r)*r是正规式(r)L(r)r是正规式(a)(b)*)|(c)可以写成ab*|c,2.2 词法记号的描述与识别,正规式的例子=a,ba|ba,b(a|b)(a|b)aa,ab

5、,ba,bbaa|ab|ba|bbaa,ab,ba,bba*由字母a构成的所有串集(a|b)*由a和b构成的所有串集复杂的例子(00|11|(01|10)(00|11)(01|10)句子：01001101000010000010111001,2.2 词法记号的描述与识别,2.2.3 正规定义对正规式命名，使表示简洁 d1 r1 d2 r2.dn rn各个di的名字都不同每个ri都是 d1,d2,di-1 上的正规式,2.2 词法记号的描述与识别,正规定义的例子C语言的标识符是字母、数字和下划线组成的串 letter_ A|B|Z|a|b|z|_ digit 0|1|9 id letter_(l

6、etter_|digit)*,2.2 词法记号的描述与识别,正规定义的例子 无符号数集合，例1946,11.28,63E8,1.99E6digit 0|1|9digits digit digit*optional_fraction.digits|optional_exponent(E(+|)digits)|numberdigits optional_fraction optional_exponent 简化表示number digit+(.digit+)?(E(+|)?digit+)?,2.2 词法记号的描述与识别,正规定义的例子（进行下一步讨论的例子）while whiledo dorelo

7、p|=letter A|B|Z|a|b|z id letter(letter|digit)*number digit+(.digit+)?(E(+|)?digit+)?delim blank|tab|newline ws delim+,2.2 词法记号的描述与识别,2.2.4 转换图关系算符的转换图,2.2 词法记号的描述与识别,标识符和保留字的转换图,2.2 词法记号的描述与识别,无符号数的转换图 number digit+(.digit+)?(E(+|)?digit+)?,2.2 词法记号的描述与识别,空白的转换图delim blank|tab|newline ws delim+,2.3

8、有 限 自 动 机,2.3.1 不确定的有限自动机（简称NFA）一个数学模型，它包括：1、状态集合S2、输入符号集合3、转换函数move:S()P(S)4、状态s0是唯一的开始状态5、F S是接受状态集合,识别语言(a|b)*ab 的NFA,状 态,NFA的转换表,2.3 有 限 自 动 机,识别语言(a|b)*ab 的NFA,2.3 有 限 自 动 机,例 识别aa*|bb*的NFA,2.3.2 确定的有限自动机（简称DFA)一个数学模型，包括：,1、状态集合S2、输入字母集合3、转换函数move:S S，且可以是部分函数4、唯一的开始状态 s05、接受状态集合F S,识别语言(a|b)*a

9、b 的DFA,2.3 有 限 自 动 机,2.3 有 限 自 动 机,例DFA，识别0,1上能被5整除的二进制数已读过尚未读已读部分的值某时刻10101110005读进01010 1110005 2=10读进110101 1100010 2+1=215个状态即可，分别代表已读部分的值除以5的余数,例DFA，识别0,1上能被5整除的二进制数,0,1,2,3,开始,4,2.3 有 限 自 动 机,10102=10101112=710,例DFA,接受 0和1的个数都是偶数的字符串,2.3 有 限 自 动 机,2.3.3 NFA到DFA的变换 子集构造法1、DFA的一个状态是NFA的一个状态集合2、读

10、了输入a1 a2 an后，NFA能到达的所有状态：s1,s2,sk，则 DFA到达状态s1,s2,sk,0,0,1,0,2,2.3 有 限 自 动 机,未画完,例(a|b)*ab，NFA如下，把它变换为DFA,2.3 有 限 自 动 机,状态,2.3 有 限 自 动 机,状态,A=0,1,2,4,7,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7,

11、2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1

12、,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9,2.3 有 限 自 动 机,状态,A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9,2.3 有 限 自 动 机,状态,2.3 有 限 自 动 机,识别语言(a|b)*ab 的自动机,2.3 有 限 自 动 机,识别语言(a|b)*ab 的自动机,子集构造法不一定得到最简DFA,2.3 有 限 自 动 机,2.3.4 DFA的化简死状态在转换函数由部分函数改成全函数表示时引入左图需要引入死状态E；右图无须引入死状态,2.3 有 限 自 动 机,可

13、区别的状态A和B是可区别的状态 从A出发，读过串b，到达非接受状态C，而从B出发，读过串b，到达接受状态DA和C是不可区别的状态 无任何串可用来像上面这样区别它们,2.3 有 限 自 动 机,方法1.A,B,C,Dmove(A,B,C,a)=Bmove(A,B,C,b)=C,D2.A,C,B,Dmove(A,C,a)=Bmove(A,C,b)=C,2.3 有 限 自 动 机,从正规式建立识别器的步骤从正规式构造NFA（本节介绍）用语法制导的算法，它用正规式语法结构来指导构造过程把NFA变成DFA（子集构造法，已介绍）将DFA化简（合并不可区别状态，也已介绍）,2.4 从正规式到有限自动机,首先

14、构造识别和字母表中一个符号的NFA重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,构造识别主算符为选择的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,构造识别主算符为连接的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,构造识别主算符为闭包的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,对于加括号的正规式(s)，使用N(s)本身作为它的NFA,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质N(r)的状态数最多是r中符号和算符总数的两倍

15、N(r)只有一个接受状态，接受状态没有向外的转换,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质N(r)的每个状态有一个用的符号标记的指向其它结点的转换，或者最多两个指向其它结点的转换,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,(a|b)*ab的两个NFA的比较,手工构造:,算法构造:,2.4 从正规式到有限自动机,小结：从正规式建立识别器的步骤从正规式构造NFA把NFA变成DFA将DF

16、A化简存在其它办法,2.4 从正规式到有限自动机,用Lex建立词法分析器的步骤,2.5 词法分析器的生成器,Lex程序包括三个部分 声明 翻译规则 辅助过程Lex程序的翻译规则 p1动作1 p2动作2 pn动作n,2.5 词法分析器的生成器,例声明部分%/*常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定义*/%/*正规定义*/delim t n wsdelim+letterA Za zdigit09idletter(letter|digit)*numberdigit+(.digit+)?(E+?digit+)?,2.5 词法分析器的生成器,例翻译规

17、则部分ws/*没有动作，也不返回*/whilereturn(WHILE);doreturn(DO);idyylval=install_id();return(ID);numberyylval=install_num();return(NUMBER);“”yylval=NE;return(RELOP);“”yylval=GT;return(RELOP);“=”yylval=GE;return(RELOP);,2.5 词法分析器的生成器,例辅助过程部分install_ id()/*把词法单元装入符号表并返回指针。yytext指向该词法单元的第一个字符，yyleng给出的它的长度*/install_

18、num()/*类似上面的过程，但词法单元不是标识符而是数*/,2.5 词法分析器的生成器,词法分析器的作用和接口，用高级语言编写词法分析器等内容掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法非形式描述的语言 正规式正规式 NFA非形式描述的语言 NFANFA DFADFA 最简DFA非形式描述的语言 DFA（或最简DFA）,本 章 要 点,叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图(1|01)*0*描述的语言是，所有不含子串001的0和1的串,例 题 1,bbabaabb,例 题 2,用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA,写出语言“所有

19、相邻数字都不相同的非空数字串”的正规定义123031357106798035790123answer(0|no_0 0)(no_0 0)(no_0|)|no_0 no_0(1|no_0-1 1)(no_0-1 1)(no_0-1|)|no_0-1.no_0-8 9 将这些正规定义逆序排列就是答案,例 题 3,下面C语言编译器编译下面的函数时，报告parse error before elselong gcd(p,q)long p,q;if(p%q=0)/*then part*/return q此处遗漏分号else/*else part*/return gcd(q,p%q);,例 题 4,现在少了第一个注释的结束符号后，反而不报错了long gcd(p,q)long p,q;if(p%q=0)/*then part return qelse/*else part*/return gcd(q,p%q);,例 题 4,第一次 2.3,2.4(f)(g)第二次2.7(c)(d)，2.8(仅为2.7(c)，2.11，2.15,习 题,