第4章 章词法分析6.pdf

《第4章 章词法分析6.pdf》由会员分享，可在线阅读，更多相关《第4章 章词法分析6.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章词法分析第4章词法分析伍 春 香武汉大学计算机学院伍 春 香武汉大学计算机学院内容简介内容简介词法分析器词法分析器单词符号单词符号词法分析程序设计词法分析程序设计词法分析器的自动生成词法分析器的自动生成学习目标学习目标?掌握掌握?词法分析程序设计的基本思想词法分析程序设计的基本思想?单词符号的表示方法与识别方法单词符号的表示方法与识别方法?由由DFA转换到程序的方法转换到程序的方法?了解了解?词法分词程序自动生成的原理词法分词程序自动生成的原理?LEX词法分析程序简介词法分析程序简介?词法分析程序的作用与地位词法分析程序的作用与地位?单词符号单词符号4.1 词法分析器与单词符号4.1 词

2、法分析器与单词符号依据语言词法规则，分析由字符组成的源程序：依据语言词法规则，分析由字符组成的源程序：1.1.词法分析程序的作用词法分析程序的作用删除注解、空格、回车符、换行符之类非必要信息，把标识符登录入符号表及某些预加工处理等。把它识别为一个一个具有独立意义的最小语法单位，即删除注解、空格、回车符、换行符之类非必要信息，把标识符登录入符号表及某些预加工处理等。把它识别为一个一个具有独立意义的最小语法单位，即“单词单词”；识别出与单词相关的属性(是标识符、界限符、数，；识别出与单词相关的属性(是标识符、界限符、数，)；转换成长度上统一的标准形式)；转换成长度上统一的标准形式属性字，以供其它部

3、分使用。属性字，以供其它部分使用。4.1 词法分析器与单词符号4.1 词法分析器与单词符号1.1.词法分析程序的作用词法分析程序的作用输入数据：输入数据：program ex1；begin M:=3.1415/4*(d1*d1-d2*d2)end.字符串形式的源程序program ex1；begin M:=3.1415/4*(d1*d1-d2*d2)end.字符串形式的源程序4.1 词法分析器与单词符号4.1 词法分析器与单词符号1.1.词法分析程序的作用词法分析程序的作用输入数据：输入数据：字符串形式的源程序字符串形式的源程序处理：处理：将源程序分割成一个一个具有独立意义的最小语法单位；将源

4、程序分割成一个一个具有独立意义的最小语法单位；begin M:=3.1415/4*(d1*d1-d2*d2)end4.1 词法分析器与单词符号4.1 词法分析器与单词符号1.1.词法分析程序的作用词法分析程序的作用输入数据：输入数据：字符串形式的源程序字符串形式的源程序处理：处理：将源程序分割成一个一个具有独立意义的最小语法单位；将源程序分割成一个一个具有独立意义的最小语法单位；识别出相关的属性(保留字、标识符、常数、界限符、运算符)识别出相关的属性(保留字、标识符、常数、界限符、运算符)begin M:=3.1415/4*(d1*d1-d2*d2)endbegin M:=3.1415/4*(

5、d1*d1-d2*d2)end4.1 词法分析器与单词符号4.1 词法分析器与单词符号1.1.词法分析程序的作用词法分析程序的作用输入数据：输入数据：字符串形式的源程序字符串形式的源程序处理：处理：将源程序分割成一个一个具有独立意义的最小语法单位；将源程序分割成一个一个具有独立意义的最小语法单位；识别出相关的属性(保留字、标识符、常数、界限符、运算符)识别出相关的属性(保留字、标识符、常数、界限符、运算符)转换成长度上统一的标准形式转换成长度上统一的标准形式begin M:=3.1415/4*(d1*d1-d2*d2)endbegin M:=3.1415/4*(d1*d1-d2*d2)end1

6、begin2M33.14155:=4.1 词法分析器与单词符号4.1 词法分析器与单词符号1.1.词法分析程序的作用词法分析程序的作用输入数据：输入数据：字符串形式的源程序字符串形式的源程序处理：处理：将源程序分割成一个一个具有独立意义的最小语法单位；将源程序分割成一个一个具有独立意义的最小语法单位；识别出相关的属性(保留字、标识符、常数、界限符、运算符)识别出相关的属性(保留字、标识符、常数、界限符、运算符)转换成长度上统一的标准形式转换成长度上统一的标准形式词法分析举例词法分析举例输出结果：输出结果：一个一个“单词单词”或或“单词串单词串”2.2.词法分析程序的地位词法分析程序的地位4.1

7、 词法分析器与单词符号4.1 词法分析器与单词符号 作为一个独立阶段 作为一个独立阶段能能独立独立地研究词法与语法两方面的特性。词法规则简单，可建立地研究词法与语法两方面的特性。词法规则简单，可建立特别适用特别适用的有效分析技术，易于实现词法分析程序生成的有效分析技术，易于实现词法分析程序生成自动化自动化。可以就同一语言，为每种不同的应用情形编写一个词法分析程序，而只编写一个。可以就同一语言，为每种不同的应用情形编写一个词法分析程序，而只编写一个共同的共同的语法分析程序，只要每个词法分析程序产生相同的语法分析程序，只要每个词法分析程序产生相同的内部表示内部表示供语法分析程序使用即可。供语法分析

8、程序使用即可。编译程序的结构编译程序的结构表 格 处 理表 格 处 理出 错 处 理出 错 处 理源程序源程序目标程序目标程序词法分析词法分析语法分析语法分析语义分析语义分析代码优化代码优化代码生成代码生成2.2.词法分析程序的地位词法分析程序的地位4.1 词法分析器与单词符号4.1 词法分析器与单词符号 作为一个独立阶段 作为一个独立阶段能能独立独立地研究词法与语法两方面的特性。词法规则简单，可建立地研究词法与语法两方面的特性。词法规则简单，可建立特别适用特别适用的有效分析技术，易于实现词法分析程序生成的有效分析技术，易于实现词法分析程序生成自动化自动化。可以就同一语言，为每种不同的应用情形

9、编写一个词法分析程序，而只编写一个。可以就同一语言，为每种不同的应用情形编写一个词法分析程序，而只编写一个共同的共同的语法分析程序，只要每个词法分析程序产生相同的符号内部表示供语法分析程序使用即可。语法分析程序，只要每个词法分析程序产生相同的符号内部表示供语法分析程序使用即可。每当语法分析程序每当语法分析程序需要一个单词符号时需要一个单词符号时就调用词法分析子程序，就调用词法分析子程序，每一次调用每一次调用，词法分析子程序就从源程序中，词法分析子程序就从源程序中识别出一个单词符号识别出一个单词符号交给语法分析程序。交给语法分析程序。4.1 词法分析器与单词符号4.1 词法分析器与单词符号 作为

10、一个独立阶段 作为一个独立阶段 安排为一个子程序 安排为一个子程序2.2.词法分析程序的地位词法分析程序的地位 语法分析程序 词法分析程序 语义分析程序 送单词返回调用取单词源程序代码生成程序 目标程序 单遍扫描的编译程序单遍扫描的编译程序4.1 词法分析器与单词符号4.1 词法分析器与单词符号3.单词符号3.单词符号程序语言的单词符号一般可分为五种：保留字、标识符、常数、运算符、界限符。程序语言的单词符号一般可分为五种：保留字、标识符、常数、运算符、界限符。单词形式单词形式单词类别编码单词类别编码单词自身值单词自身值单词种别单词种别：一类一码；一符一码。：一类一码；一符一码。单词符号的属性值

11、单词符号的属性值：反映单词符号特征或特性的值。如标识符的符号表指针，常数的常数表指针等。：反映单词符号特征或特性的值。如标识符的符号表指针，常数的常数表指针等。词法分析程序的设计词法分析程序的设计?预处理预处理?单词符号的识别单词符号的识别?状态转换图的作用状态转换图的作用?词法分析程序的设计步骤词法分析程序的设计步骤1预处理预处理4.2 扫描程序的设计4.2 扫描程序的设计如删除注解、空格、回车符、换行符之类非必要信息。如删除注解、空格、回车符、换行符之类非必要信息。C/C+的预处理：的预处理：宏展开宏展开 包含文件包含文件 条件编译条件编译源程序不能一次性读入，怎么办？源程序不能一次性读入

12、，怎么办？1预处理预处理4.2 扫描程序的设计4.2 扫描程序的设计如删除注解、空格、回车符、换行符之类非必要信息。从源程序中处理出如删除注解、空格、回车符、换行符之类非必要信息。从源程序中处理出一串确定长度一串确定长度的输入字符，并将其装进词法分析程序指定的缓冲区的输入字符，并将其装进词法分析程序指定的缓冲区扫描缓冲区中。扫描缓冲区中。1预处理预处理4.2 扫描程序的设计4.2 扫描程序的设计2单词符号的识别单词符号的识别超前搜索超前搜索 保留字的识别 标识符的识别 常数的识别 算符和界限符的识别 保留字的识别 标识符的识别 常数的识别 算符和界限符的识别DO99K=1，10 DO99K=1

13、.10 5.EQ.M 5.E08 3HABC 单词的单词的构成特点构成特点：4.2 扫描程序的设计4.2 扫描程序的设计非常有规律，可以用非常有规律，可以用正规文法正规文法描述其构成规则。描述其构成规则。3利用有穷自动机识别单词利用有穷自动机识别单词4.2 扫描程序的设计4.2 扫描程序的设计0 01 10 01 10 01 10 01 1q q3 3q q1 1startstartq q2 2q q4 4状态转换图中的每一个状态实际上对应着分析过程的某一个时刻。状态转换图中的每一个状态实际上对应着分析过程的某一个时刻。状态转换图的实现状态转换图的实现：将状态转换图看作是通常的程序框图。将状态

14、转换图看作是通常的程序框图。4.2 扫描程序的设计4.2 扫描程序的设计每个状态构造一段代码每个状态构造一段代码，代码的功能为：从输入串中读一个字符；判明读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配的那条弧所指向的状态；均不匹配时便失败，代码的功能为：从输入串中读一个字符；判明读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配的那条弧所指向的状态；均不匹配时便失败(不能到达正常出口不能到达正常出口)。有些词法分析程序还会在这些代码段中加上一些其它。有些词法分析程序还会在这些代码段中加上一些其它语义处理语义处理(如对数值进行如对数值进行10进制到进制到2进制的转换等进制

15、的转换等)。扫描程序构造方法扫描程序构造方法无回路的分叉结点，对应无回路的分叉结点，对应switchswitch语句或一组语句或一组ififthenthenelseelse语句；含回路的结点，对应于一个语句；含回路的结点，对应于一个whilewhile和和ifif语句构成的程序段；终态结点，对应一个形如语句构成的程序段；终态结点，对应一个形如return(code,value)return(code,value)的语句,code为单词种别编码；value为单词属性值或无定义，意为返回到调用者。的语句,code为单词种别编码；value为单词属性值或无定义，意为返回到调用者。注意回退指针：注意回

16、退指针：有些状态多读进的不属于本单词的字符(如标识符或保留字后的有些状态多读进的不属于本单词的字符(如标识符或保留字后的“；”等)应退回等)应退回搜索指示器回调(Retract)一个字符。搜索指示器回调(Retract)一个字符。4.2 扫描程序的设计4.2 扫描程序的设计步骤步骤 分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;细化DFA;编码。分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;细化DFA;编码。构造流程图构造流程图4.2 扫描程序的设计4.2 扫描程序的设计举例举例 分析单词特征、确定单词类别编码；分析单词特征、确定单词类别编码

17、；自然语言正规文法正规表达式有穷自动机：形式化描述、状态转换图其它形式自然语言正规文法正规表达式有穷自动机：形式化描述、状态转换图其它形式4.2 扫描程序的设计4.2 扫描程序的设计举例举例 分析单词特征、确定单词类别编码；分析单词特征、确定单词类别编码；GE：EE+T|T TT*F|FF(E)|i单词单词+*（）（）i类别编码类别编码123454.2 扫描程序的设计4.2 扫描程序的设计举例举例 分析单词特征、确定单词类别编码；分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;构造NFA；NFA确定化;DFA最小化;17/()+-数字数字*非数字非数字字母字母:非=非=

18、其它其它字母/数字字母/数字空格空格数字数字=非*非*0 01 13 31111141424567891012131516非字母与数字非字母与数字4.2 扫描程序的设计4.2 扫描程序的设计举例举例 分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;细化DFA;细化DFA;17/()+-数字数字*非数字非数字字母字母:非=非=其它其它字母/数字字母/数字空格空格数字数字=非*非*0 01 13 31111141424567891012131516非字母与数字非字母与数字4.2 扫描程序的设计4.2 扫

19、描程序的设计举例举例 分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;细化DFA;分析单词特征、确定单词类别编码；构造NFA；NFA确定化;DFA最小化;细化DFA;编码。编码。构造流程图构造流程图17/()+-数字数字*非数字非数字字母字母:非=非=其它其它字母/数字字母/数字空格空格数字数字=非*非*0 01 13 31111141424567891012131516非字母与数字非字母与数字每次识别一个单词每次识别一个单词 一个子程序被调用一个子程序被调用 循环的语句部分循环的语句部分词法分析程序自动构造词法分析程序自动构造?基本原理基本原理?LEX简介简介由正规表

20、达式e由正规表达式ei i构造转换系统(NFA构造转换系统(NFAi i)用m条弧将m个NFA连成一个NFA用子集法将此NFA转换为一个等价的DFA根据此DFA生成词法分析程序(加上操作部分)用m条弧将m个NFA连成一个NFA用子集法将此NFA转换为一个等价的DFA根据此DFA生成词法分析程序(加上操作部分)4.3 词法分析程序自动生成4.3 词法分析程序自动生成基本原理：基本原理：操作部分：一段程序代码，它指出了按正规表达式识别出一个单词后应采取的动作。操作部分：一段程序代码，它指出了按正规表达式识别出一个单词后应采取的动作。4.3 词法分析程序自动生成4.3 词法分析程序自动生成词法分析器

21、词法分析器L L输入源程序输入源程序单词符号串单词符号串LEX(编译程序)LEX(编译程序)LEX源程序LEX源程序词法分析器词法分析器L LLEX是一个词法分析程序生成器。LEX接受：LEX是一个词法分析程序生成器。LEX接受：一组正规表达式一组正规表达式；每个正规表达式相应的；每个正规表达式相应的一组动作(操作)一组动作(操作)。单词的构成规则单词的构成规则识别单词后做的工作识别单词后做的工作Lex接收：一个Lex接收：一个文本文件文本文件，包括，包括正规表达式正规表达式和表达式被匹配时词法分析程序应采取的和表达式被匹配时词法分析程序应采取的动作动作。Lex输出：C语言程序的文件lex.y

22、y.c或者lexyy.c，包含。Lex输出：C语言程序的文件lex.yy.c或者lexyy.c，包含过程yylex(DFA的实现)过程yylex(DFA的实现)编译lex.yy.c或者lexyy.c将编译结果连接到主程序编译lex.yy.c或者lexyy.c将编译结果连接到主程序4.3 词法分析程序自动生成4.3 词法分析程序自动生成过程过程Lex是是UNIX环境下的工具。环境下的工具。Windows环境下的工具是环境下的工具是Flex(Fast Lex)，是，是Free Software Fundation创建的创建的Gnu compiler package的一部分。的一部分。4.3 词法分析程序自动生成4.3 词法分析程序自动生成第4章 内容小结第4章 内容小结词法分析程序的任务词法分析程序的任务单词符号的形式单词符号的形式词法分析程序的构造词法分析程序的构造扫描程序构造方法扫描程序构造方法画框图。画框图。正规表达式正规表达式(NFA)(NFA)子集法子集法正规文法正规文法最小化DFA最小化DFADFADFA状态集划分状态集划分上下文无关文法上下文无关文法自然语言自然语言由特殊的框图由特殊的框图状态图，写出词法分析程序。状态图，写出词法分析程序。状态转换图状态转换图源程序源程序