编译原理 词法分析课件

1、第二章词汇分析，词汇分析概述词法分析概述词法分析器手动实现正则表达式和有限自动机词法分析器自动生成，1，学习交换PPT，2.1词法分析是编译过程的第一步，主要按从左到右的字符扫描源程序并生成单词符号，通常用令牌(token)表示。最后，生成单词符号序列并输出，或直接使用单词符号作为解析模块的输入。源程序(字符串格式)、输出词序列(令牌格式)、词法分析、语法分析、token、token、get next token、2、学习交换PPT、问题：1、2、如何说明标记？如何识别标记？词汇分析的其他作用：1，词汇分析器发现标识符类型的单词时，将其添加到符号表；2、过滤注释和空格等文字；3、记录换行符数，

2、并为每个错误消息提供行号，从而将编译器生成的错误信息与源程序的位置相关联。3，学习交换PPT，1，令牌(token)和说明，令牌(单词符号)是程序语言的基本语法单位。一般分为常数、数组、变量、过程或函数名称的7个关键字(基本单词)标识符。常数：各种类型的常数。运算符：*、/、等。分隔符：例如，(、)等。空格字符：空格字符、换行符等。意见，4，沟通PPT学习，注意：如何分类一种语言的单词，如何编码主要取决于技术实现的方便性。5，可以使用学习交换PPT，2，标记识别，词汇分析中识别单词的状态转换图。例如，状态转换图是有限的直接图，节点表示状态，用圆表示。节点点之间可以通过乳香边缘连接，乳香边缘有可

3、标记的字符。6，学习通信PPT，q1，q2，q3，q0，示例1:字符串100101识别过程，7，学习通信PPT，q2，q3，q0，q1，示例1:字符串14，学习通信PPT，q1，q3，q0，q2，实例2:字符串00识别流程，15，学习通信PPT，q1，q2，q3，q0，实例2:字符串00 学习通信PPT、状态转换图示例、示例1:字符串必须以空格开始和结束，中间可以包含零个或多个az的字符串。23，学习通信PPT，示例2: Pascal语言中关系运算符识别的状态转换图。24，学习交换PPT，示例3:识别标识符状态转换图。25，学习通信PPT，示例4:无符号整数的状态转换。26，学习通信PPT，对

4、于没有2.2电路的分支状态，与switch()语句或if-else语句集相对应的简单词法分析器示例。对于回路存在的状态，对应于while语句。最终状态通常对应于return()语句。对于词法分析器，通常返回到解析器。以c语言子集为例。，27，学习通信PPT，单词符号，种类编码，助记符，内部代码值，while，if，else，switch，case，标识符，常量，-，*，1，2，3，4，5，6，7，8，9，10，11，11，12，13，while，if，else，switch，case，id，num，-，*，relop，-，-，-，-，-，num在符号表中的位置，-，-，-，LE，LT，EQ，-

5、，-，id在符号表中的位置，28，学习通信PPT，2，0，14，15，其他，12，=，格式转换图表范例，*，*，*，8，*，11，13，其他，*，空格(2)判断读取的文字与从此状态开始的弧的标记相符时，移动到指向重合弧的状态。(3)不匹配将失败。词法分析器手动实现，30，学习通信PPT，程序实现子程序token()输入：字符流输出：单词符号的二进制形式，31，学习通信PPT，数据结构和子程序(实现)数据结构character当前输入字符令牌输入缓冲区(字符数组从关键字类别或0 getchar():返回输入缓冲区中读取一个字符，将其放入ch letter()和digit():中，并在确定当前输入

6、字符是字符还是数字retract():扫描指针中的一个字符的同时清空character。Error():错误处理，33，学习AC PPT，character=getchar()whilet character跳过空格/空格DO getchar()；case character of digit(character): character token；getchar()；while digit(character)do character token；getchar()；Build list(令牌)；retract()；返回(NUM，NUM的常量表入口指针)；34，学习通信PPT，letter(

7、character): character token；getchar()；while letter(character)| digit(character)do character token；getchar()；retract()；key=reserve(token)；IF key0 THEN返回(key，null)build list(token)；返回(id，id的符号表入口指针)=: getchar()；IF character返回=THEN(relop，EQ)retract()；返回(=，null)，35，学习AC PPT，返回(，null)-:返回(-，null) * :返回(*

8、，null) :IF character返回=THEN(relop，LE)retract()；返回(relop，LT)；返回：(；null)其他： retract()；error()；END OF CASE，36，学习AC PPT，需要进一步考虑的问题1，缓冲预处理，高级搜索2，关键字处理，符号表实现3，符号表查找效率，算法优化实现4，词汇错误处理，37，学习AC PPT，源程序的输入，内存另一个用于向前搜索以查找单词的结尾，称为扫描指针。开始指针，搜索指针，38，学习通信PPT，高级搜索，词汇分析程序是所谓的高级搜索技术，用于确定在阅读单词时是否阅读了整个单词的全部字符，通过今后大量阅读的文

9、字来判断。39，交换PPT，关键字识别和查找算法，对于关键字，首先检查标识符，然后检查关键字表。在表中找到的关键字，用于获取其类别代码。否则，会将其视为标识符。查找算法：线性查找前缀查找散列函数，40，学习交换PPT，错误处理，处理定义外的单词(例如，第一个字符不是字符，不是数字，不是运算符和分隔符的单词)错误。41，学习通信PPT，正则表达式是用于描述可定义正则集的符号字符串的合适表示法。正则集是用正则表达式描述的字符串集合。通常用l()表示。使用正则表达式的原因：词汇规则简单易懂。轻松配置高效的标识过程。词汇分析程序可以由正则表达式自动配置。可用于其他各种信息流处理。2.3正则表达式和有限

10、自动机简介，42，学习通信PPT，1，正则表达式的定义，如果设置为字母，则正则表达式将按照以下规则递归定义：基本：(1)为l()=；(2)是的正则表达式，l()=；(3)对于a，a是以前的正则表达式，表示为l (a)=a。归纳：(4)(递归定义)如果r和s都是正则表达式，(r)则是正则表达式，集合l(r)=l(r)；Rs是表示集l (r | s)=l (r) l (s)的正则表达式。Rs是表示集l (RS)=l (r) l (s)的正则表达式。R*是的正则表达式，表示集l (r *)=(l (r)。43，学习通信PPT，计算优先级*高于连接|()指定优先级关系，44，学习通信PPT，例如顺序=

11、a，b，的正则表达式及其正则集的示例，正则表达式正则表达式a ab a，b ab ab(a、b、aa、ab包含a和b的所有字符串(ab)(aabb)(ab)包含正则集中两个连续的a或两个连续的b的所有字符串、46、学习通信PPT、思维：1、命令=a、 如果是2，a，b，字符串集S=anban|n0是否可以用正则表达式描述？47，学习通信PPT，2，编程语言的常规实例=letter，对于digit，可以使用的常规r=letter(letter|digit)*表示标识符。命令=d，e，-，的常规r=d *(.DD * |) (e (| | |) DD * |)可用于表示无符号浮点数。其中d表示数字

12、digit，即0-9。48，学习通信PPT，3，正则表达式的等价性，如果正则表达式r与s表示的正则集相同，即说明的字符串的集合相同。 r=s，49，学习通信PPT，例如，判断以下正则表达式是否相同。1)(a|b)*和a*|b* 2)(ab)*和a*b* 3)(a|b)*和(a*b*)*，aa .按单词种类分类的代码b .在符号表中单词的位置c .按单词种类编码和自身值d .单词本身值(2)相当于正则表达式M1和M2。A. M1和M2的状态数确定为B. M1和M2的有向栏数相同的C. M1和M2的语言集具有相同的D. M1和M2的状态数和有向栏数，52，学习通信PPT，(3) DFA M(参见图

13、2-1)接收的字符集如下：a .由以0开头的二进制数组成的集合B. 0结尾的二进制数组成的集合c .由具有奇数0的二进制数组成的集合d .偶数0的二进制数组成的集合回答 (1) c (2) c (3) d，53，学习AC PPT，状态转换映射DFA(llan)可以用状态转换图表示。有限自动机是通用结构的实例，例如在动态数据结构和高级搜索中有很多应用程序的直接映射。，顺序，55，学习通信PPT，1，状态转换图，直接图，节点显示状态，显示为圆；节点之间可以通过边连接，以显示影响状态更改的可输入文字。56，学习交换PPT，2，确定的有限状态机器人，一个确定有限自动机(DFA)D为5元组D=(K，m，s，z)。其中k:有限非空状态集合；具有非空输入符号字母表