《西北工业大学编译原理所有课件第二章词法分析》由会员分享，可在线阅读，更多相关《西北工业大学编译原理所有课件第二章词法分析（136页珍藏版）》请在金锄头文库上搜索。
1、machunyan,西北工业大学软件与微电子学院,1,课程内容 第1章 概论 第2章 词法分析 第3章上下文无关文法及分析 第4章自上而下的语法分析 第5章自下而上的语法分析 第6章语义分析 第7章运行时环境 第8章代码生成 第9章 代码优化,machunyan,西北工业大学软件与微电子学院,2,第2章 词法分析,单词的描述工具,单词的识别系统,设计和实现词法分析程序,作业,课程设计1,2.1 词法分析器的作用 2.2 正规表达式 2.3 有穷自动机 2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机 2.6 自动生成词法分析程序,machunyan,西北工业大学软件与微电子学院,3,
2、词法分析器(词法分析程序)的任务：从源代码中读取输入字符，按照构词规则切分成一系列单词(token )， 提交给语法分析使用。 识别出源程序中的单词； 删除无用的空白字符及注释； 检测出输入中不能形成源语言任何单词的错误字符串。,2.1 词法分析器的作用,machunyan,西北工业大学软件与微电子学院,4,2.1 词法分析器的作用(续),词法分析器的输出: token序列，每个token包括两个方面的内容： token表示的字符串（词义） if, y, , 3, x, =, 0 token的类型（词法） 关键字（if, ） 操作符（=, ） 数字 （3, 0, ） 标识符（x, y, ） J
3、ava举例,machunyan,西北工业大学软件与微电子学院,5,Token类型,Token词义,定义token的数据类型： typedef struct TokenType tokenval; union char *stringval; int numval; attribute; TokenRecord;,2.1 词法分析器的作用(续),machunyan,西北工业大学软件与微电子学院,6,词法分析程序的函数接口： TokenRecord getToken(void);,Token,getToken(),源程序,词法分析程序,语法分析程序,符号表,2.1 词法分析器的作用(续),mach
4、unyan,西北工业大学软件与微电子学院,7,2.1 词法分析器的作用(续),GJC对Java源程序的词法分析举例 public class Point private int x; private int y; public Point(int initialX, int initialY) x = initialX; y = initialY; ,词法分析的输出（仅包括单词的类型，词值参照左边）： EOF PUBLIC CLASS IDENTIFIER LBRACE PRIVATE INT IDENTIFIER SEMI PRIVATE INT IDENTIFIER SEMI PUBLIC
5、 IDENTIFIER LPAREN INT IDENTIFIER COMMA INT IDENTIFIER RPAREN LBRACE IDENTIFIER EQ IDENTIFIER SEMI IDENTIFIER EQ IDENTIFIER SEMIR BRACE RBRACE EOF,machunyan,西北工业大学软件与微电子学院,8,第2章 词法分析,单词的描述工具,单词的识别系统,设计和实现词法分析程序,作业,课程设计1,2.1 词法分析器的作用 2.2 正规表达式 2.3 有穷自动机 2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机 2.6 自动生成词法分析程序,ma
6、chunyan,西北工业大学软件与微电子学院,9,2.2正规表达式 单词的描述工具,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,machunyan,西北工业大学软件与微电子学院,10,2.2.1 基本概念和术语,字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限非空集合称为字母表。 不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。 符号串 由字母表中的符号组成的任何有穷序列称为符号串。 字母表A=a，b，c上的符号串有： a，b，c，ab，aa
7、ca。 在符号串中，符号的顺序是很重要的，符号串ab不同于ba。,machunyan,西北工业大学软件与微电子学院,11,2.2.1 基本概念和术语(续),符号串的长度 如果某符号串x中有m个符号，则称其长度为m，表示为x=m，如001110的长度是6。 空符号串，不包含任何符号的符号串，其长度为0，即=0。 符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。 例如 x=ST，y=abu，则它们的连接 xy=STabu。 由于的含义，有x=x=x。,machunyan,西北工业大学软件与微电子学院,12,符号串的方幂：符号串自身连接n次得到的符号串xn 定
8、义为 xxxx； x1=x, x2=xx，且规定x0=。 符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 符号串集合的和与积 设A，B为两个符号串集合，定义 和 A+B(或AB) =w|wA，或wB 积 AB=xy|xA，yB,2.2.1 基本概念和术语(续),machunyan,西北工业大学软件与微电子学院,13,若用表示空集，A表示任意非空的符号串的集合，则有： A+ = +A = A A = A = A = A 例：若集合A=ab，cde ，集合B = 0，1，则AB =ab1，ab0，cde0，cde1；,2.2.1 基本概念和术语(续),空符号串
9、形成的集合,= A,machunyan,西北工业大学软件与微电子学院,14,2.2.1 基本概念和术语(续),的闭包：用*表示上的一切符号串(包括)组成的集合，*称为的闭包。 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 的正闭包：上除外的所有符号串组成的集合记为+ ，+称为的正闭包。 例如：=a,b +=a,b,aa,ab,ba,bb,aaa,aab,machunyan,西北工业大学软件与微电子学院,15,2.2正规表达式 单词的描述工具,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.
10、2.5 单词的正规表达式举例,machunyan,西北工业大学软件与微电子学院,16,每个正规表达式匹配（或代表、或表示）一个字符串的集合（称为正规集）； 作用： 它是描述语言词法规则的形式化工具,2.2.2正规表达式的定义,设计正则表达式匹配满足类型要求的字符串，以对源文件进行解析 (例C#：Regex reg = new Regex(“http:/w+-/.*.jpgs“*“); ),例如：可以用正规表达式描述C或Java语言标示符的词法规则（C或Java语言的标示符是字母和数字组成的序列，第一个字符必须是字母，下划线视为字母，且大小写字母不同）。,正规表达式（也称正则表达式）：是用特定的
11、运算符及运算对象按规则构造的表达式；,machunyan,西北工业大学软件与微电子学院,17,设有字母表为，辅助字母表=, , | , . , * , ( ) ，正规表达式和它所表示的正规集(字符串的集合)的递归定义如下： 和是上的正规式，它们所表示的正规集分别为 和 ； 若a，则a是上的正规式，它所表示的正规集为a；,2.2.2正规表达式的定义,举例,machunyan,西北工业大学软件与微电子学院,18,2.2.2正规表达式的定义(续),若r和s是上的正规式，它们所表示的正规集分别为L(r)和L(s)，则： r|s是正规式，表示的正规集为L(r|s)=L(r)L(s) ； rs是正规式，表
12、示的正规集为L(rs)=L(r)L(s) ； r*是正规式，表示的正规集为(L(r)*。 (r)是正规式，表示的正规集为L(r)；,“.”运算符常省略,定义(续),举例,machunyan,西北工业大学软件与微电子学院,19,2.2.2正规表达式的定义(续),有限次使用上述步骤3而定义的表达式是上的正规式，由这些正规式所表示的符号串集合是上的正规集。 注：算符的优先级为先“ ( ) ”“ * ”，再“ . ”最后“ | ” ，它们满足左结合律。,定义(续),举例,machunyan,西北工业大学软件与微电子学院,20,正规表达式和正规集举例,2.2.2正规表达式的定义(续),machunyan
13、,西北工业大学软件与微电子学院,21,2.2.2正规表达式的定义(续),语言(Language)是字符串组成的集合； 正规表达式表示的正规集也可以称为该正规表达式表示的语言。,举例： c-语言的词法,machunyan,西北工业大学软件与微电子学院,22,正规式(a)| (b) * (c) 所表示的正规集为： 根据运算符的优先级，上述正规式可以表示成 a|b*c a|b*c所表示的正规集为：字符串a以及由零个或多个b后跟一个c 形成的字符串的集合。 或写成L(a|b*c)=a b*c= a bnc | n是大于或等于0的整数,2.2.2正规表达式的定义(续),machunyan,西北工业大学软
14、件与微电子学院,23,aa,a|aa,2.2.2正规表达式的定义(续),给定一个正规式，它唯一确定一个正规集； 给定一个正规集，则可由多个不同的正规式表示。例如：集合a,aa, aaa,任意个a的串对应的正规式有：,machunyan,西北工业大学软件与微电子学院,24,2.2.2正规表达式的定义(续),若二正规式描述同一正规集，则称二式等价(相等)。 判断下列正规表达式e1和e2是否等价？ e1= (ab)， e2 = ba e1= b(ab) ，e2 =(ba)b e1= (ab)，e2 =(ab),machunyan,西北工业大学软件与微电子学院,25,小结 正规表达式（也称正则表达式）
15、是表示模式的一种重要方法，每个模式匹配一个字符串集合（即正规集）。 正规集是正规表达式所定义的语言。 正规表达式可以作为字符串集合（即正规集）的名字。,2.2.2正规表达式的定义(续),machunyan,西北工业大学软件与微电子学院,26,2.2正规表达式 单词的描述工具,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,machunyan,西北工业大学软件与微电子学院,27,r和s是正规表达式，则有如下关系成立： A1. r|s=s|r A2. r|r=r A3. r|=r A4. (r|s)|t=r|(s|t) A5. (rs)t=r(st) A6. r(s|t)=rs|rt A7. (s|t)r=sr|tr A8. r=r= A9. r=r=r A10. r*=(|r)*=|rr*,2.2.3 正规式基本等价关系,machunyan,西北工业大学软件与微电子学院,28,2.2正规表达式 单词的描述工具,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,machunyan,西北工业大学软件与微电子学院,29,2.
