《软件技术基础》之《词法分析》
《软件技术基础》之《词法分析》
词法分析的功能
功能
- 扫描源程序的字符串；
- 按照词法规则识别出单词符号作为输出；
- 对识别过程中发现的词法错误，则输出有关的错误信息。
词法分析器在编译器负责：
- 读取源程序；
- 识别单词；
- 过滤掉源程序的注释和空白；
- 将编译器生成的错误信息与源程序的位置关联（记录遇到的换行符的个数、给出错信息赋予一个行号）。
词法分析器和语法分析器的关系
词法分析器作为单独的一遍
词法分析器不断地读取输入串（源文件），直到识别出下一个符合单词模式的字符串（词素），词法分析器根据此“符合单词模式的字符串”生成下一个单词，将单词流的输出形成一个输出文件，作为语法分析器的输入。
词法分析器作为子程序
语法分析器调用词法分析器，指示词法分析器从它的输入不断读取字符，直到识别出下一个“符合单词模式的字符串”为止，词法分析器根据其生成下一个单词（token），返回给语法分析器。
示例：
上面的语句可以分成：
词法分析器的输出形式
单词的种类
- 标识符：用来命名程序中出现的变量、数组、函数、过程、标号等
- 基本字：也可称关键字或保留字，如if、while、for、do、goto等
- 常数：各种类型的常数，如233、3.1415、true等
- 运算符：如+、-、*、/等
- 界符：如；、：、（、）等
单词的输出形式：二元式
单词类型的划分
- 基本字、运算符、界符：一字一码；
- 标识符：单列一种；
标识符是以字母开头的的“字母/数字”串。用来表示各种名字，如变量名、函数名等。 - 常数：按类型分类，如整型、布尔型、字符型等。
词法分析器的结构
扫描缓冲区
- 输入缓冲区：源程序进入输入缓冲区；
- 预处理程序：取消注释、剔除无用的空白、回车、换行等；
- 扫描缓冲区：从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别
扫描缓冲区的结构：双缓冲区
设置左右两个缓冲区，当左缓冲区读完后，新读入的字符存入右缓冲区；反之，存放在左缓冲区；
- 起点指针 (lexeme Begin) ：用来指示正在扫描的单词的起点；
- 搜索指针 (forward) ：用于向前搜索，寻找单词的结束；
符号的识别
根据语言规定的词法规则，进行识别。
对不同类型的单词符号，有不同的识别要求
- 基本字：语言的固定格式
- 标识符：读到非字母数字
- 常数：根据常数的格式、大多数常数后都有运算符或界符
- 界符、运算符：需要超前搜索
词法分析技术——超前搜索
为了判定一个单词符号的识别，必须扫描到某一地方，而该单词符号并没有这么长，这种扫描方式叫做超前搜索。
起点指针指向当前单词的开始处。
搜索指针用于向前搜索，寻找单词的结束，搜索指针前移前需要确定是否达到末尾。
如果是，读取N个新字符到另一缓冲区，如果剩余字符不足N个，添加 eof 字符（或其他不会在源程序中的字符）。
单词确定后，搜索指针指向该词素结尾字符。
生成单词并记录或返回给语法分析器后， 生成单词并记录或返回给语法分析器后， 生成单词并记录或返回给语法分析器后起点指针指向下一个字符。
词法分析器的实现
状态转换图
简称转换图（transition diagram），是一张有限方向图，是设计词法分析器的有效工具。
它由如下成分构成：
- 结点（mode）：圆圈表示结点，代表状态（state）
- 有向边（弧）：连接结点，连接结点，边上的标记字符表示该状态下可能接收或识别的字符
特点：
- 有限的有向图；
- 有向边上标记字符；
- 唯一初态，若干终态（至少一个）。
状态转换图识别的串
从初态出发到某一终态路径上字符的连接。
识别标识符的状态转换图：
利用状态转换图识别单词符号的过程
- 从初态开始
- 从输入串中读一个字符
- 判明读入字符与从当前状态出发的哪条弧上的标记相匹配，便转到相应匹配的那条弧所指向的状态；
- 重复3，均不匹配时便告失败；到达终态时便识别出一个单词符号。
在很多程序设计语言中，基本字也符合标识符的模式，如何区分？
解决方法：
-
在符号表中预先填写保留字，并指明它们不是普通标识符；
-
为关键字或保留字建立单独的状态转换图。
其他状态转换图的例子
符号表
在程序中 ,用户用标识符定义了不少名字来代表不同的数据对象，编译程序将这些名字保存在符号表中。
符号表除了记录名字本身而外，还记录了与名字关联的各种属性信息。
符号表在词法分析阶段的角色
- 建立符号表，查填符号表；
- 将不重复的标识符、数字常数和字符常数的性质填入符号表中，如：名字、类型、数值等；
- 并且将变量（或常数）在符号表中的入口地址写到其自身的单词（TOKEN）中。
符号表的一般形式
每个名字对应一个表项，一个表项包括名字域和信息域。
信息域通常设置若干个子域和标志位，其内容可以是与名字有关的任何信息，如类型、种属、长度、相对地址、数组的内情向量、记录与分量的联系、形参标志、说明标志、赋值标志等。
因名字的长度、信息域的组成和长度可能是各不相同的，一般采用间接表技术。
间接符号表的数据结构：