编译原理_第3章_第1节_词法分析、dfa、nfa及其转换

《编译原理_第3章_第1节_词法分析、dfa、nfa及其转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、源程序目标程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理错误检测第三章词法分析主要内容1.介绍词法分析的过程2.讨论词法分析器的设计与实现3.介绍实现词法分析器的主要工具：状态转换图第三章词法分析3.1词法分析器的任务人们理解一篇文章（或程序）起码是先在单词级别上思考。编译程序要分析和翻译源程序，也先要区分一个一个的单词。词法分析程序的任务是：从左到右逐个字符对源程序扫描，产生一个单词序列，把作为字符串的源程序改造为单词符号串的中间程序。词法分析程序又称词法分析器或扫描器。除了识别单词的基

2、本任务外，词法分析还可以完成以下任务：（1）组织源程序的输入（2）删除注释、空格及无用符号（如回车等）（3）行、列计数（4）列表打印源程序（5）发现并定位词法错误（6）建立、查填符号表3.1.1单词符号的表示基本字：也称关键字，如C语言中的int,void,if,while等；标识符：用来表示各种名字，如变量名、常量名、函数名等；常数：如25,3.1415926,‘a’,“hello”,TRUE等；算符：如+,=,~等；界符：如逗号，分号，括号等。基本字、运算符和界符一般确定；标识符和常数的数量一般不加限制。注

3、：（1）程序设计语言单词的分类纯属技术性问题，可以有不同的方法分类；（2）除上述一般分类方法外，还有一字一类或一符一类等方法单词的分类，如：while(i<10)i++;单词的分类单词分类的原则保留字（关键字）：可以看作一类，也可以一字一类；算符和界符：可以一符一类，算符还可以把有一定共性算符分为一类；常数：可以按照数据类型分类；标识符：统一归为一类。3.1.1单词符号的表示单词的分类3.1.1单词符号的表示单词经常表示为二元组：(单词类别,单词值)对某些单词来说，不仅需要它们的值，还需要一些其它信息，这些都记

4、录在符号表中，所以相应表示为：(标识符，指向该标识符所在符号表中位置的指针)(单词类别,单词的属性)区分单词所属的类(整数编码)单词的值单词的表示3.1.1单词符号的表示编号类别1标识符2常数3保留字4算符5界符输出：(3,“while”)(5,“(“)(1,指向i的符号表入口)(4,“>=“)(1,指向j的符号表入口)(5,“)”)(1,指向i的符号表入口)(4,“--”)(5,“;”)数据类型存储地址int3056int3060例：while(i>=j)i--;单词的表示：举例3.1.2词法分析器的结构字符

5、串形式的源程序单词串形式的源程序词法分析器字符词法分析器与语法分析器的联系（1）词法分析作为单独的一遍3.1.2词法分析器的结构将词法分析器分离的考虑使整个编译程序的结构更简洁、清晰和条理化；编译程序效率更高；增强编译程序的可移植性。(2)词法分析作为子程序输入串词法分析器语法分析器符号表取下一单词返回下一单词词法分析器与语法分析器的联系3.1.2词法分析器的结构扫描缓冲区1.预处理程序：取消注解，剔除无用的空白、跳格、回车、换行等2.输入缓冲区：源程序输入缓冲区3.1.2词法分析器的结构主要是为方便单词的识

6、别工作：（1）剔除无用的空白符、跳格符、回车符、换行符。‘‘,‘t’,‘r’,‘’（2）剔除注释：/*…………*/,//（3）合并空白符。预处理程序例：intmax(intx,inty)//求x,y的最大值{intz;z=(x>y?x:y);returnz;}预处理后：intmax(intx,inty){intz;z=(x>y?x:y);returnz;}3.1.2词法分析器的结构预处理程序3.1.2词法分析器的结构缓冲区的设计起点指针：用来指示正在扫描的单词的起点；搜索指针：用于向前搜索，寻找

7、单词的结束；缓冲区结构扫描缓冲区：从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别。扫描缓冲区的结构：假设标识符和常数的最大长度为256缓冲区长度：512标识符起点(500)搜索指示器3.1.2词法分析器的结构标识符起点(252)搜索指示器缓冲区长度：256缓冲区长度：256：设置左右两个缓冲区，当左缓冲区读完后，新读入的字符存入右缓冲区；反之，存放在左缓冲区；缓冲区的设计小结词法分析器的任务；单词符号的分类；单词符号的表示；词法分析预处理；词法分析器的工作

8、方式；扫描缓冲区的双缓冲策略。3.2.1正规式与正规集正规式（正规表达式）：用以描述单词符号的工具，是说明单词的模式的一种重要的表示法,是定义正规集的工具。一个正规式对应一个正规集正规式和正规表达式3.2.1正规式与正规集对字母表∑：(1)ε和Φ都是∑上的正规式，它们所表示的正规集分别为{ε}和Φ；(2)a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；(3)假定U和V都是∑上