词法分析正则表达式课件

词法分析——正则表达式授课：胡静10/14/20232004年12月28日1编译原理词法分析——正则表达式10/9/20232004年12月28目录编译器的结构编译的例子什么是词法分析如何编写一个词法分析器正则表达式——用来描述tokens编写一个词法分析器的生成器10/14/20232编译原理目录编译器的结构10/9/20232编译原理编译器的应用模型出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理编译的前端（FrontEnd）编译的后端（BackEnd）10/14/20233编译原理编译器的应用模型出语法分析程序语义分析程序目标代码生成程序词以语法分析器为核心的编译器模型语法分析器词法分析器中间代码生成器语义分析器一部分中间代码输入字符串程序入口初始化工作10/14/20234编译原理以语法分析器为核心的编译器模型语法分析器词法分析器中间代码生一个简单的编译器结构10/14/20235编译原理一个简单的编译器结构10/9/20235编译原理这个结构是如何进行工作的10/14/20236编译原理这个结构是如何进行工作的10/9/20236编译原理这个结构是如何进行工作的10/14/20237编译原理这个结构是如何进行工作的10/9/20237编译原理第一步：词法分析10/14/20238编译原理第一步：词法分析10/9/20238编译原理tokensIdentifiers:xy11elsen_i00Integers:21000-5005LFloatingpoint:2.00.00020.021.1e50.e-10Strings:“x”“Hesaid,\“Areyou?\””Comments:/**don’tchangethis**/Keywords:ifelsewhilebreakSymbols:+*{}++<<<[]>=10/14/20239编译原理tokensIdentifiers:x特别的词法分析器手写代码来产生tokens如何读取标识符tokens？10/14/202310编译原理特别的词法分析器手写代码来产生tokens10/9/2023Look-aheadCharacter一次扫描一个字符使用向前看字符(next)的方法来决定将要读到的是什么类型的token，以及当前这个token的结尾在何处。10/14/202311编译原理Look-aheadCharacter一次扫描一个字符10特别的词法分析器：高层循环10/14/202312编译原理特别的词法分析器：高层循环10/9/202312编译原理问题的提出如果只向前看一个字符，不能够确定我们将要读入的是哪种类型的token如果token的开头是“i”，那么它一定是标识符么？如果token的开头是“2”，那么它一定是一个整型的常数么？如果我们通过上面的类似“插入”式的方法来写识别token的程序，这样的程序不容易写正确，而且也不容易维护因此需要一个更加有原理性的方法：词法分析器的生成器，可以自动产生有效的词法分析器。（例如lex，flex，Jlex）一般说来，没有限制的向前看是必要的10/14/202313编译原理问题的提出如果只向前看一个字符，不能够确定我们将要读入的是哪一些问题如何明确的描述tokens2.e020.e-012.0000“”“x”“\\”“\”\’”如何将文本分割成tokensif(x==0)a=x<<1;if(x==0)a=x<1;10/14/202314编译原理一些问题如何明确的描述tokens10/9/202314编译如何描述tokens我们可以使用正则表达式来描述程序设计语言中的tokens正则表达式(RE,RegularExpression)的定义如下：a ordinarycharacterstandsforitselfε theemptystringR|S eitherRorS(alternation),whereR,S=RERS RfollowedbyS(concatenation),whereR,S=RER* concatenationofaRERzeroormoretimes (R*=ε|R|RR|RRR|RRRR…)在实际形式中，会有优先级的限制，因此可以加入一些括号。10/14/202315编译原理如何描述tokens我们可以使用正则表达式来描述程序设计语言简单的例子正则表达式R描述的字符串的集合表示为L(R)L(R)=由R定义的“语言”L(abc)={abc}L(hello|goodbye)={hello,goodbye}L(1(0|1)*)=所有的非零二进制数我们可以用正则表达式来定义每种类型的token10/14/202316编译原理简单的例子正则表达式R描述的字符串的集合表示为L(R)10/一些RE的简写R+

oneormorestringsfromL(R):R(R*)R?optionalR:(R|ε)[abce]oneofthelistedcharacters:(a|b|c|e)[a-z]onecharacterfromthisrange:(a|b|c|d|e|…|y|z)[^ab]anythingbutoneofthelistedchars[^a-z]onecharacternotfromthisrange10/14/202317编译原理一些RE的简写R+ 10/9/202317编译原理简单的例子正则表达式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”Cidentifiers这种简写方式不支持递归10/14/202318编译原理简单的例子正则表达式在L(R)中的字符串这种简写方式不支持递如何切分文本只有RE是不够的，还需要一些进行选择的规则大部分的语言，优先选择最长的匹配当最长匹配长度相同时，由优先级决定RE’s+优先级+最长匹配规则=词法分析器的定义10/14/202319编译原理如何切分文本只有RE是不够的，还需要一些进行选择的规则10/小结词法分析器将文本流转换成tokens特殊的词法分析器不容易写的正确，而且不易维护