编译原理及实践-第2章 词法分析

《编译原理及实践-第2章 词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章词法分析2.1词法分析器的作用2.2正则表达式2.3有穷自动机2.4从正则表达式到DFA2.5用代码实现有穷自动机2.6利用lex自动生成词法分析程序单词的描述工具单词的识别系统设计和实现词法分析程序12.1词法分析器的作用词法分析器(词法分析程序)的任务：从源代码中读取输入字符，产生单词序列(生成独立的有意义的逻辑单元称作单词(token))，提交给语法分析使用。2任务：逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符

2、号和常量等。识别出源程序中的单词；删除无用的空白字符及注释（空格、回车等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程序，而对于语法分析是完全无用的。进行词法检查，能够检测出输入中不能形成源语言任何单词的错误字符串。3Thebigelephantatethepeanut.词法分析的结果：<词义，词型>4token表示的字符串（串值或词义）：if,y,>,3,then,x,=,0token的

3、类型（词法）：关键字（if,else,for,int,return…）操作符（+,-,<,>……）数字（3,45,…）标识符（x,y,name…）补充：typedefenum类似宏{IF,THEN,PLUS,MINUS,NUM,ID}TokenType;词法分析器的输出:token序列5ify<3thenx=0词法分析器例如：C源代码:ify<3thenx=0,词法分析器的输出是？<词型

4、，词义>类型串值例ID表示标识符类型x表示具体的标识符串6定义逻辑项token的数据类型：typedefstructunion{char*stringval;intnumval;}attribute;}TokenRecord;{TokenTypetokenval;Token类型Token词义补充：union数据类型7词法分析程序的函数接口：TokenRecordgetToken(void);TokengetToken()源程序词法分析程序语法分析程序符号表8第2章词法分析2.1词法分析器的作用2.

5、2正则表达式2.3有穷自动机2.4从正则表达式到DFA2.5用代码实现有穷自动机2.6利用lex自动生成词法分析程序记号的描述工具记号的识别系统设计和实现词法分析程序9正则表达式：对自动生成词法分析程序而言，正则表达式也是非常有用的工具。所谓正则表达式就是用特定的运算符及运算对象按某种规则构造的表达式。例如：a*匹配空串ε,a,aa,aaa,…其表示的是一个集合，记为L(a*)。正则表达式用来描述单词结构(定义单词)。102.2.1基本概念和术语2.2.2正则表达式的定义2.2.3正则表达式基本等

6、价关系2.2.4正则表达式的扩展2.2.5单词的正则表达式举例2.2正则表达式单词的描述工具112.2.1基本概念和术语字母表（符号表、符号集）由若干元素（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。12符号串由字母表中的符号组成的任何有穷序列称为符号串:例如00，11，10是字母表=｛0，1｝上的符号串。字母表A=｛a，b，c｝上的符号串有：a，b，c，ab，aaca等。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba，a

7、bca和aabc也不同。13符号串的长度如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。14符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如x=ST，y=abu，则它们的连接xy=STabu，｜x｜=2，｜y｜=3，｜xy｜=5由于ε的含义，显然有εx=xε=x。符号串的方幂：符号串自身连接n次得到的符号串xn定义为xx…x；n个xx1=x,x

8、2=xx且x0=ε15例；若x=ab则:x0=εx1=abx2=ababx3=abababxn=xxn-1=xn-1x(n>0)16符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的和与积设A，B为两个符号串集合，定义和A+B(或AB)={w

9、wA，或wB}积AB={xy

10、xA,yB}17若用表示空集，则有：A+=+A=AA=A={}A=A{}=A例：若集合A=ab,cde，集合B=0,1，则AB=