编译原理 第三章 词法分析

《编译原理 第三章 词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章词法分析3.1对于词法分析器的要求3.2词法分析器的设计3.3正规表达式与有限自动机3.4词法分析器的自动产生3.1对于词法分析器的要求词法分析的功能和输出形式：词法分析器的功能是接收输入源程序，输出单词符号。单词符号分五种：关键字；标识符；常数；运算符；界符。词法分析器所输出的单词符号常常表示成如下的二元式：(单词种别，单词符号的属性值)单词种别：本书假定关键字、运算符和界符都是一符一种，标示符单列一种，常数按类型分种。单词符号的属性信息：属性信息（值）是指单词符号的特性或特征值。本书仅给出标示符、常量的属性信息

2、，即存放它们的符号表表项的指针。例子：While(i>=j)i--;经词法分析器处理后的结果为：<(,-><>=,-><),-><--,-><;,->3.2词法分析器的设计输入缓冲区预处理子程序扫描缓冲区扫描器图3.1词法分析器列表输入单词符号3.2.1输入、预处理输入：源程序。输入缓冲区：存放输入串。预处理子程序：对输入串进行预处理，其主要工作是去掉注释行，合并空白符等。扫描缓冲区：存放整理好的符号串。扫描

3、器：不断地从扫描缓冲区读入字符串，并进行识别。扫描器设计扫描缓冲区分为两部分：基本缓冲区和补充缓冲区，如果基本缓冲区不够，则要求输入串一定在补充缓冲区内结束，所以高级语言的符号串长度有限制。搜索指示器起点指示器扫描缓冲区3.2.2超前搜索超前搜索：由于符号串需要结合后面的符号明确语义，所以需要向前读取多个符号后，判断其含义，这种向前读取符号的机制称为超前搜索。超前搜索应用：关键字识别标示符的识别常数的识别算符和界符识别例子：While(i>=j)i--;While(i>=j)i--起点指示器搜索指示器While(i>=j

4、)i--起点指示器搜索指示器While(i>=j)i--起点指示器搜索指示器3.2.3状态转换图状态转换图定义：转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。1X23Y(a)(a)一个简单转换图2数字0其它1数字(c)整数识别*2数字或字母0其它1字母(b)标示符识别*60123457●●数字数字数字E或DE或D数字数字数字+或-数字其它其它(d)识别实型常数*简单语言符号表单词符号种别编码助忆符内

5、码值DIM1$DIM-IF2$IF-DO3$DO-STOP4$STOP-END5$END-标识符6$ID内部字符串常数（整）7$INT标准二进制式=8$ASSIGN+9$PLUS-＊10$STAR-＊＊11$POWER-，12$COMMA-（13$LPAR-）14$RPAR-转换规则：关键字（如IF、WHILE等）都是“保留字”。所谓保留字的意思是，用户不得使用它们作为自己定义的标识符。例如，下面的写法是绝对禁止的：IF（5）=X因为，我们的分析器在识别出IF时就认定它是一个关键字。如果不采用保留字的办法，就必须使用超前

6、搜索技术。由于把关键字作为保留字，故可以把关键字作为一类特殊标识符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫做保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的）。例如，一个条件语句应写为IFi>0i=1;而绝对不要写成IFi>0i=1;因为对于后者，我们的分析无条件地将IFi看成一个标识符。数字100135672489

7、131211字母字母或数字数字非字母与数字非数字=+*●●●,()其它非*****3.2.4状态转换图的实现算法主要思想：让每个状态结点对应一小段程序。对不含回路的分支结点，可以对应一个switch或一组if语句。对含回路的状态结点，可以对应一个while语句和if语句。终态结点对应一个return(code,value)语句。Ch-字符变量，存放最新读进的源程序字符。strToken-字符数组，存放构成单词符号的字符串。GetChar-子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。GetBC-子程序过

8、程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。Concat-子程序过程，将ch中的字符连接到strToken之后。例如，假定，strToken原来的值为“AB”,而ch中存放着‘C’,经调用Concat后，strToken的值就变为“ABC”.IsLetter和IsDigit