文档介绍：《编译原理》
——词法分析器

学院:
专业:
姓名:
学号:

序言
编译,简单的说,就是把源程序转换为可执行程序。编译程序的工作,从输入源程序开始到输出目标程序为止的整个过程,是非常复杂的。而此法分析是编译程序工作过程的第一环节。这篇报告主要讲了词法分析器的原理,最后会给出一个词法分析器的简单实现。
实验目的
设计一个词法分析程序,理解词法分析器实现的原理,掌握程序设计语言中的各类单词的词法分析方法,加深对词法分析原理的理解。
词法分析原理
词法分析的任务是:输入源程序,对构成源程序的字符串进行扫描和分解,识别出一个个的单词(亦称为单词符号或简称符号),如基本字(begin、end、for、if、while等),标识符、常数、算符、和界符(标点符号、左右括号等等)。例如,对于pascal的循环语句
For I:=1 to 100 do
词法分析的结果是识别出如下的单词符号:
基本字 for
标识符 I
赋值号:=
整常数 1
基本字 to
整常数 100
基本字 do
输出:词法分析器所输出单词符号常常表示成如下的二元式:
(单词种别,单词符号的属性值)
单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型(整、实、布尔等)分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号,除了给出了种别编码之外,还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。
例子:C++代码段:
while(i>=j) i--
经词法分析器处理后,它将被转为如下的单词符号序列:
<while, _>
<(, _>
<id, 指向i的符号表项的指针>
<>=, _>
<id, 指向j的符号表项的指针>
<), _>
<id, 指向i的符号表项的指针>
<--, _>
<;, _>
词法分析分析器作为一个独立子程序
词法分析是编译过程中的一个阶段,在语法分析前进行。词法分析作为一遍,可以简化设计,改进编译效率,增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
实验说明
(1)关键字:"begin","end","if","then","else","while","write","read",
"do", "call","const","char","until","procedure","repeat"
(2)运算符:"+","-","*","/","="
(3)界符:"{","}","[","]",";",",",".","(",")",":"
(4)其他标记如字符串,表示以字母开头的标识符
(5)空格、回车、换行符跳过
(6)运行结果在屏幕上以如下格式显示:
1 $无符号整数
begin $关键字
if $关键字
+ $运算符
; $界符
a $普通标识符//“$“为美元符号,不是大写字母S
词法分析器的设计
输入、预处理
词法分析器工作的第一步是输入源程序文本。把输入串预处理一下,对单词符号的识别工作将是比较方便的。预处理可以剔掉空白符、跳格符、回车符和换行符等编辑性字符。
单词符号的识别:超前搜索
单词符号识别的一个简单方法——超前搜索。
在FORtRAN语言中,关键字不加特殊保护,可用作普通标识符。为确定词性,需超前搜索若干个字符。
在FORTRAN中
1 DO99K=1,10
2 IF() I=10
3 DO99K=
4 IF(5)=55
这四个语句都是正确的语句。语句1和2 分别是DO和IF语句,语句3和4是赋值语句。为了正确区别1和3,2和4语句,需超前扫描若干个字符。
1 DO99K=1,10 2 IF() I=10
3 DO99K= 4 IF(5)=55
语句1和3的区别在于符号之后的第一个界符:一个为逗号,另一个为句末符。语句2和4的主要区别在于右括号后的第一个字符:一个为字母,另一个为等号。为了识别1、2中的关键字,必须超前扫描多个字符。超前到能够肯定词性的地方为止。为了区别1和3,必须超前扫描到等号后的第一个界符处。对于语句2、4来说,必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。
状态转换图
词法分析器使用状态转换图来识别单词符号。状态转换图是一张有限方向图。在状态转换图中,有一个初态,至少一个终态。
其中0为初态,2为终态。这个转换图识别(接受)标识符的过程是:从初态0开始