编译原理(2)词法_1(正规表达式与有限自动机简介)VIP免费

第2讲西北农林科技大学本科教程主讲教师：赵建邦第二章《词法分析》前三节2.1词法分析器的设计方法2.2一个简单的词法分析器2.3正规表达式与有限自动机简介重点掌握状态转换图的概念正规表达式的概念和运算本讲目标第二章词法分析2.1词法分析器的设计方法2.2一个简单的词法分析器2.3正规表达式与有限自动机简介2.4正规表达式到有限自动机的构造2.5词法分析器的自动生成回顾词法分析器：定位–词法分析是编译的第一个阶段任务–从左至右逐个字符地对源程序进行扫描，产生一个个单词（Token）符号功能–输入源程序，输出单词符号（流）–不断访问、更新符号表2.1词法分析器的设计方法词法分析器的处理结构（2种）：第一种：词法分析器和语法分析器完全分开–词法分析器的输出（单词符号流）作为语法分析器的输入将词法分析工作作为独立的一遍来完成，在这个过程中不断查询和完善符号表2.1词法分析器的设计方法图2-1(a)词法分析程序作为主程序词法分析器的处理结构（2种）：第二种：词法分析器作为语法分析器调用的子程序–每当语法分析器需要一个单词时便调用词法分析器–词法分析和语法分析交替进行2.1词法分析器的设计方法图2-1(b)词法分析程序作为子程序2.1.1：单词符号的分类与输出形式–分类：单词符号是程序语言的基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：•保留字：如C语言中的if、else、while和do等–几乎所有的程序语言都禁止用户使用保留字作为标识符•标识符：用户自己定义的常量名、变量名、方法名等•常数：布尔常数（true/false）和其它常数•运算符：“+”、“-”、“*”、“/”、“>”、“<”等•界符：在语言中是作为语法上的分界符号使用的，如“,”、“;”、“(”、“)”、“=”等2.1词法分析器的设计方法2.1.1：单词符号的分类与输出形式–输出形式：单词符号通常表示成如下的二元式：（单词种别，单词自身的值/内码值）1、单词种别：即单词的种类。为了处理方便，通常让每种单词对应一个整数码，可以最大限度地将每个单词区别开来•保留字：可以统一视为一种，也可一字一种（后一种较常用）•标识符：统一归为一种•常数：可统一归为一种或按照整型、实型、布尔型等分为几种•运算符和界符可统一归为一种或采用一符一种2.1词法分析器的设计方法2.1.1：单词符号的分类与输出形式2、单词自身的值•如果一个种别只含一个单词符号，对于这个单词符号，种别编码就完全代表它自身的值•如果一个种别含有多个单词符号，除了给出种别编码之外，还应给出单词符号自身的值，以便区分同一种类的单词2.1词法分析器的设计方法注意，标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值（第一种）。也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值（第二种）。例如：if(a>1)b=100;如果采用每种单词对应一个整数码，对应的二元式序列？假如五类单词的种别规定如下：保留字if种别：2标识符种别：10常量种别：11“=”种别：17“>”种别：23“;”种别：26“(”种别：29“)”种别：30102.1单词符号分类举例上面的子程序输出的二元式序列：(2,）if(29,)((10,’a’)a(23,)>(11,’1’的二进制）1(30,))(10,’b’)b(17,)=(11,’100’的二进制)100（26，);采用第一种表示2.1.2：状态转换图（概念）–上一小节解决了单词符号的表示，但是如何识别单词呢？答：借助“状态转换图”在词法分析中，可以用状态转换图来识别单词。状态转换图是状态有限的有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，代表状态转换关系，有向边上可标记字符，表示前一状态接受某一个字符之后的状态转移2.1词法分析器的设计方法例如，右图表示在状态i下的状态转换：若输入字符为x，则读入x并转换到状态j；若输入字符为y，则读入y并转换到状态k。2.1.2：状态转换图（表示）–状态转换图的要求•状态（即结点）个数有限•至少一个初始状态，若干终止状态•每...