编译原理期中复习词法分析

词法分析的作用

扫描源程序字符流
按照原语言的词法规则识别出各类单词符号
产生用于语法分析的记号序列
词法检查
与用户接口的任务
- 跳过源程序的空白和注释
- 把错误信息与源程序联系起来
创建符号表（如果需要的话）

把识别出来的标识符插入符号表中

词法分析程序与语法分析程序的关系

作为独立的一遍
输出需要放入一个中间文件
- 磁盘文件
- 内存文件
作为语法分析程序的子程序
- 避免了中间文件
- 省去了取送符号的工作
- 有利于提高编译程序的效率
- 符号表是否需要创建以是否为块结构语言决定，非块结构变量均为全局变量，需要创建
与语法分析程序作为协同程序

词法分析程序与语法分析程序在同一遍中，以生产者和消费者的关系同步运行

分离词法分析程序的好处

简化设计
改进编译程序效率
加强编译程序的可移植性

词法分析程序的输入输出

词法分析程序的实现方法

词法分析程序自动生成器
传统的系统程序设计语言编写
汇编语言编写

缓冲区

为了得到某一个单词符号的性质，需要超前扫描若干个字符

配对缓冲区

将一个缓冲区分为大小相同的两半，各含N个字符，N=1KB或4KB

原因在于只有一个缓冲区时，单词可能会被截断，需要另外一个配对缓冲区进行接续

词法分析程序的输出：记号

记号模式单词

记号 - 某一类单词符号的类别编码，如标识符的记号为id，常数的记号为num等

模式 - 某一类单词符号的构词规则，如标识符的模式是“由字母开头的字母数字串”

单词 - 某一类单词符号的一个特例，如position是标识符

记号的属性

词法分析程序在识别出一个记号后，要把与之有关的信息作为它的属性保留下来

记号影响语法分析的决策，属性影响记号的翻译

在词法分析阶段，对记号只能确定一种属性

标识符 - 单词在符号表中的入口指针
常数 - 它所表示的值
关键字 - （一符一种、或一类一种）
运算符 - （一符一种、或一类一种）
分界符 - （一符一种、或一类一种）

Eg.

total := total + rate * 4


<id,指向标识符total在符号表中的入口的指针>
<assign_op,-> (一符一种)
<id,指向标识符total在符号表中的入口的指针>
<plus_op,-> (一符一种)
<id,指向标识符rate在符号表中的入口的指针>
<mul_op,-> (一符一种)
<num,整数值4>

记号的描述和识别

识别单词是按照记号的模式进行的，一种记号的模式匹配一类单词的集合

正规表达式和正规文法（即3型文法也就是线性文法）是描述模式的重要工具

详见形式语言与自动机

文法书写约定

终结符号
- 次序靠前的小写字母，a，b，c
- 运算符号，+，-，*，/
- 各种标点符号，括号，逗号等等
- 数字1，2，。。。
- 黑体字符串id，begin，if，then
非终结符号
- 次序靠前的大写字母
- 大写字母S常作为起始符
- 斜体字符串
文法符号

次序靠后的大写字母
终结符号串

次序靠后的小写字母
文法符号串

罗马字符

记号的文法

标识符

定义为由字母打头的，由字母或数字组成的符号串

描述标识符集合的正规表达式为

$letter(letter|digit)^*$

常数

整数部分

$(digit)^+$

无符号数

$(digit)^+(.(digit)^+)?(E(+|-)?(digit)^+)?$

运算符

状态转换图与记号识别

见形式语言与自动机

词法分析程序的设计与实现

文法与状态转换图

最终得到状态转移图

词法分析程序的构造

把语义动作添加到状态转换图中，使每一个状态都对应一小段程序，就可以构造出相应的词法分析程序
如果某一状态有若干条射出边，则程序段：读一个字符，根据读到的字符，选择标记与之匹配的边到达下一个状态，即程序控制转去执行下一个状态对应的语句序列
在状态0，首先要读进一个字符。若读入的字符是一个空格（包括blank、tab、enter）就跳过它，继续读字符，直到读进一个非空字符为止。接下来的工作就是根据所读进的非空字符转相应的程序段进行处理
在标识符状态，识别并组合出一个标识符之后，还必须加入一些动作，如查关键字表，以确定识别出的单词符号是关键字还是用户自定义标识符，并输出相应的记号
在“<”状态，若读进的下一个字符是“=”，则输出关系运算符“<=”；
若读进的下一个字符是“>”，则输出关系运算符“<>”；
否则输出关系运算符“<”。