1、词法分析词法分析正则表达式正则表达式授课：胡静授课：胡静2022年12月17日编译原理2目录目录编译器的结构编译器的结构编译的例子编译的例子什么是词法分析什么是词法分析如何编写一个词法分析器如何编写一个词法分析器正则表达式正则表达式用来描述用来描述tokens编写一个词法分析器的生成器编写一个词法分析器的生成器2022年12月17日编译原理3编译器的应用模型编译器的应用模型出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理编译的前端编译的前端（Front
2、 End）编译的后端编译的后端（Back End）2022年12月17日编译原理4以语法分析器为核心的编译器模型以语法分析器为核心的编译器模型语法分语法分析器析器词法分词法分析器析器中间代码中间代码生成器生成器语义分析器语义分析器一部分中一部分中间代码间代码输入字输入字符串符串程序入口程序入口初始化工作初始化工作2022年12月17日编译原理5一个简单的编译器结构一个简单的编译器结构2022年12月17日编译原理6这个结构是如何进行工作的这个结构是如何进行工作的2022年12月17日编译原理7这个结构是如何进行工作的这个结构是如何进行工作的2022年12月17日编译原理8第一步：词法分析第一步
3、：词法分析2022年12月17日编译原理9tokensIdentifiers:x y11 elsen _i00Integers:2 1000 -500 5LFloating point:2.0 0.00020 .02 1.1e5 0.e-10Strings:“x”“He said,“Are you?”Comments:/*dont change this*/Keywords:if else while breakSymbols:+*+=2022年12月17日编译原理10特别的词法分析器特别的词法分析器手写代码来产生手写代码来产生tokens如何读取标识符如何读取标识符tokens？2022年1
4、2月17日编译原理11Look-ahead Character一次扫描一个字符一次扫描一个字符使用向前看字符使用向前看字符(next)的方法来决定将要读到的是什的方法来决定将要读到的是什么类型的么类型的token，以及当前这个，以及当前这个token的结尾在何的结尾在何处。处。2022年12月17日编译原理12特别的词法分析器：高层循环特别的词法分析器：高层循环2022年12月17日编译原理13问题的提出问题的提出如果只向前看一个字符，不能够确定我们将要读入的是哪种如果只向前看一个字符，不能够确定我们将要读入的是哪种类型的类型的token如果如果token的开头是的开头是“i”，那么它一定是标
5、识符么？，那么它一定是标识符么？如果如果token的开头是的开头是“2”，那么它一定是一个整型的常数么？，那么它一定是一个整型的常数么？如果我们通过上面的类似如果我们通过上面的类似“插入插入”式的方法来写识别式的方法来写识别token的程的程序，这样的程序不容易写正确，而且也不容易维护序，这样的程序不容易写正确，而且也不容易维护因此需要一个更加有原理性的方法：词法分析器的生成器，因此需要一个更加有原理性的方法：词法分析器的生成器，可以自动产生有效的词法分析器。（例如可以自动产生有效的词法分析器。（例如lex，flex，Jlex）一般说来，没有限制的向前看是必要的一般说来，没有限制的向前看是必要
6、的2022年12月17日编译原理14一些问题一些问题如何明确的描述如何明确的描述tokens2.e0 20.e-01 2.0000“”“x”“”“”如何将文本分割成如何将文本分割成tokensif(x=0)a=x1;if(x=0)a=x1;2022年12月17日编译原理15如何描述如何描述tokens我们可以使用我们可以使用正则表达式正则表达式来描述程序设计语言中的来描述程序设计语言中的tokens正则表达式正则表达式(RE,Regular Expression)的定义如下：的定义如下：a ordinary character stands for itself the empty strin
7、gR|S either R or S(alternation),where R,S=RERS R followed by S(concatenation),where R,S=RER*concatenation of a RE R zero or more times(R*=|R|RR|RRR|RRRR)在实际形式中，会有优先级的限制，因此可以加入一些括号。在实际形式中，会有优先级的限制，因此可以加入一些括号。2022年12月17日编译原理16简单的例子简单的例子正则表达式正则表达式R描述的字符串的集合表示为描述的字符串的集合表示为L(R)L(R)=由由R定义的定义的“语言语言”L(abc)=
8、abc L(hello|goodbye)=hello,goodbyeL(1(0|1)*)=所有的非零二进制数所有的非零二进制数我们可以用正则表达式来定义每种类型的我们可以用正则表达式来定义每种类型的token2022年12月17日编译原理17一些一些RE的简写的简写R+one or more strings from L(R):R(R*)R?optional R:(R|)abce one of the listed characters:(a|b|c|e)a-z one character from this range:(a|b|c|d|e|y|z)ab anything but one o
9、f the listed charsa-z one character not from this range2022年12月17日编译原理18简单的例子简单的例子正则表达式正则表达式digit=0-9 posint=digit+int=-?posintreal=int(|(.posint)=-?0-9+(|(.0-9+)a-zA-Z_a-zA-Z0-9_*在在L(R)中的字符串中的字符串“0”“1”“2”“3”“8”“412”“-42”“1024”“-1.56”“12”“1.0”C identifiers这种简写方式不支持递归这种简写方式不支持递归2022年12月17日编译原理19如何切分文
10、本如何切分文本只有只有RE是不够的，还需要一些进行选择的规则是不够的，还需要一些进行选择的规则大部分的语言，优先选择最长的匹配大部分的语言，优先选择最长的匹配当最长匹配长度相同时，由优先级决定当最长匹配长度相同时，由优先级决定REs+优先级优先级+最长匹配规则最长匹配规则=词法分析器的定义词法分析器的定义2022年12月17日编译原理20小结小结词法分析器将文本流转换成词法分析器将文本流转换成tokens特殊的词法分析器不容易写的正确，而且不易维护特殊的词法分析器不容易写的正确，而且不易维护对大部分语言来说，合法的对大部分语言来说，合法的tokens都可以由正则表都可以由正则表达式方便的精确的定义。达式方便的精确的定义。2022年12月17日编译原理21
