大连理工大学编译原理PPT讲义课件.ppt

《大连理工大学编译原理PPT讲义课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、温故知新正规式计算机实现状态转换图不确定有限自动机确定有限自动机等价子集构造法最简确定有限自动机等价非形式化描述的语言状态列举法合并不可区别状态手工实现用正规式语法结构来指导构造过程？词法分析器的生成器Lex是LEXicalcompiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器的C源码,描述规则采用正规式。描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c的文件，然后由C编译器编译生成一个词法分析器。LEX源程序经过LEX处理，并经过编译，可以生成一个词法分析器

2、。这个词法分析器的作用就好像有限自动机一样，可以用来识别和产生单词符号。2.5词法分析器的生成器2.5词法分析器的生成器用Lex建立词法分析器的步骤Lex编译器Lex源程序lex.llex.yy.cC编译器lex.yy.ca.outa.out输入流记号序列2.5词法分析器的生成器LEX将用户输入的表达式和动作序列转化为宿主语言的源程序，经过编译后的程序即是词法分析程序，被称为yylex。LEX不是一种完整的语言，但是它可以嵌入到其他程序设计语言的源程序中。嵌入到LEX中的程序设计语言被称为宿主语言。宿主语言用来

3、处理LEX的输出代码，同时也可以由用户添加一些必要的代码辅以词法分析。目前，LEX支持的宿主语言通常是C语言。2.5词法分析器的生成器Lex程序包括三个部分声明％％翻译规则％％辅助过程Lex程序的翻译规则p1{动作1}p2{动作2}……pn{动作n}2.5词法分析器的生成器例---声明部分%{/*常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定义*/%}/*正规定义*/delim[t]ws{delim}+letter[AZaz]digit[09]id{le

4、tter}({letter}

5、{digit})*number{digit}+(.{digit}+)?(E[+]?{digit}+)?2.5词法分析器的生成器例---翻译规则部分{ws}{/*没有动作，也不返回*/}while{return(WHILE);}do{return(DO);}{id}{yylval=install_id();return(ID);}{number}{yylval=install_num();return(NUMBER);}“<”{yylval=LT;return(RELOP);}

6、“<=”{yylval=LE;return(RELOP);}“=”{yylval=EQ;return(RELOP);}“<>”{yylval=NE;return(RELOP);}“>”{yylval=GT;return(RELOP);}“>=”{yylval=GE;return(RELOP);}2.5词法分析器的生成器例---辅助过程部分install_id(){/*把词法单元装入符号表并返回指针。yytext指向该词法单元的第一个字符，yyleng给出的它的长度*/}install_num(){/*类似上面的

7、过程，但词法单元不是标识符而是数*/}用Lex定义常规表达式.匹配任意字符，除了-指范围[A-Za-z0-9]$行的结尾{}模式可能出现的次数，例如A{1,3}表示可能出现1次或3次^(1)行的开始；(2)否定,操作符^只能出现在左中括号后的第一个字符位置处[^abc]*

8、?+等常用的闭包，逻辑或等操作2.5词法分析器的生成器Lex中重要的外部变量yytext:外部字符数组，其内容是当前被某个规则匹配的字符串yyleng:当前yytext中的字符的个数例：[a-zA-Z]+printf(“word=%s,l

9、ength=%d”,yytext,yyleng)；另外[a-zA-Z]+printf(“%s”,yytext);可以简写成[a-zA-Z]+ECHO;2.5词法分析器的生成器Lex中识别规则二义性处理能匹配最多字符的规则优先能匹配相同数目的字符的规则，书写顺序在前的优先eg：integerkeywordaction...;[a−z]+identifieraction...;当输入为integers时，匹配[a−z]+Lex中识别规则二义性处理Lex程序分割输入流同时不搜索每个表达式的所有可能匹配。每个字符计算一

10、次且仅一次。例如，计算she和he在输入文本中的出现次数：shes++heh++

11、/*规则同下一行*/.;在这里最后两个规则忽略除了he和she的所有东西。然而，因为she包含he，Lex不识别包含在she中的he的情况。Lex中识别规则二义性处理假设需要计算输入文本中she中he的个数she{s++;REJECT;}he{h++;}

12、/*规则同下一行*/.;因为she包括he