词法分析正则表达式课件.ppt
词法分析正则表达式,授课：胡静,2023年3月27日,编译原理,2,目录,编译器的结构编译的例子什么是词法分析如何编写一个词法分析器正则表达式用来描述tokens编写一个词法分析器的生成器,2023年3月27日,编译原理,3,编译器的应用模型,出错处理,语法分析程序,语义分析程序,目标代码生成程序,词法分析程序,中间代码生成程序,代码优化程序,表格管理,编译的前端（Front End）,编译的后端（Back End）,2023年3月27日,编译原理,4,以语法分析器为核心的编译器模型,2023年3月27日,编译原理,5,一个简单的编译器结构,2023年3月27日,编译原理,6,这个结构是如何进行工作的,2023年3月27日,编译原理,7,这个结构是如何进行工作的,2023年3月27日,编译原理,8,第一步：词法分析,2023年3月27日,编译原理,9,tokens,Identifiers: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:+*+=,2023年3月27日,编译原理,10,特别的词法分析器,手写代码来产生tokens如何读取标识符tokens？,2023年3月27日,编译原理,11,Look-ahead Character,一次扫描一个字符使用向前看字符(next)的方法来决定将要读到的是什么类型的token，以及当前这个token的结尾在何处。,2023年3月27日,编译原理,12,特别的词法分析器：高层循环,2023年3月27日,编译原理,13,问题的提出,如果只向前看一个字符，不能够确定我们将要读入的是哪种类型的token如果token的开头是“i”，那么它一定是标识符么？如果token的开头是“2”，那么它一定是一个整型的常数么？如果我们通过上面的类似“插入”式的方法来写识别token的程序，这样的程序不容易写正确，而且也不容易维护因此需要一个更加有原理性的方法：词法分析器的生成器，可以自动产生有效的词法分析器。（例如lex，flex，Jlex）一般说来，没有限制的向前看是必要的,2023年3月27日,编译原理,14,一些问题,如何明确的描述tokens2.e0 20.e-01 2.0000“”“x”“”“”如何将文本分割成tokensif(x=0)a=x1;if(x=0)a=x1;,2023年3月27日,编译原理,15,如何描述tokens,我们可以使用正则表达式来描述程序设计语言中的tokens正则表达式(RE,Regular Expression)的定义如下：a ordinary character stands for itself the empty stringR|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)在实际形式中，会有优先级的限制，因此可以加入一些括号。,2023年3月27日,编译原理,16,简单的例子,正则表达式R描述的字符串的集合表示为L(R)L(R)=由R定义的“语言”L(abc)=abc L(hello|goodbye)=hello,goodbyeL(1(0|1)*)=所有的非零二进制数我们可以用正则表达式来定义每种类型的token,2023年3月27日,编译原理,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 of the listed charsa-z one character not from this range,2023年3月27日,编译原理,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,这种简写方式不支持递归,2023年3月27日,编译原理,19,如何切分文本,只有RE是不够的，还需要一些进行选择的规则大部分的语言，优先选择最长的匹配当最长匹配长度相同时，由优先级决定REs+优先级+最长匹配规则=词法分析器的定义,2023年3月27日,编译原理,20,小结,词法分析器将文本流转换成tokens特殊的词法分析器不容易写的正确，而且不易维护对大部分语言来说，合法的tokens都可以由正则表达式方便的精确的定义。,2023年3月27日,编译原理,21,Thanks for your time!Questions&Answers,
