编译原理

第三章 词法分析

2020-02-18 11:00 CST
2020-03-27 23:21 CST
CC BY-NC 4.0

词法分析器的作用

  • 读入字符流,组成词素,输出词法单元序列
  • 过滤空白、换行、制表符、注释等
  • 将词素添加到符号表中

为什么要设计独立的词法分析器?

  • 简化编译器的设计
  • 提高编译器效率
    • 词法分析必语法分析更加简单
    • 下推自动机 v.s. 有限自动机
  • 增强编译器的可移植性

概念定义

  • 词法单元(Token)
    • <token_name, attribute_name>
    • 单元名:表示词法单位种类的抽象符号,语法分析器通过单元名即可确定词法单元序列的结构
    • 属性值:用于语义分析以后的阶段
  • 模式(Pattern)
    • 描述了一类语法单元的词素可能具有的形式
  • 词素(Lexeme)
    • 源程序中的字符序列
    • 和某个词法单元的模式匹配,被词法分析器识别为该词法单元的实例

E.g. 人和鬼

  • 人和鬼是两种不同的词法单元
  • 用两条腿走路是人的一种模式
  • 张三、李四是两个词素

E.g. printf("Total = %d\n", score);

  • literal是一种语法单元
  • 双引号之间的字符串(不含双引号)是literal的模式
  • Total = %d\n是一个literal的实例

词法单元的属性

有的模式可能会出现多次,需要额外属性来进行区分:

  • 一个模式匹配多个词素时,通过属性来传递附加的信息
  • 不同的目的需要不同的属性
  • 属性值通常是一个结构化数据
    • 词素
    • 类型
    • 第一次出现的位置
    • ……

词法单元的规约(正则表达式)

  • 正则表达式可以高效、简洁地描述处理词法单元时用到的模式类型

串和语言

  • 字母表(Alphabet):一个有穷的符号集合
  • 字符表上的串(String):该表中符号的有穷序列
    • 串的长度$|s|$
    • 空串:长度为0的串$\varepsilon$
  • 语言(Language):某个给定字母表上的串的可数集合
  • 前缀:从串的尾部删除0或多个符号后得到的串
  • 后缀:从串的首部删除0或多个符号后得到的串
  • 子串:删除串的某个前缀和后缀得到的串
  • 真前缀、真后缀、真子串:既不等于原串也不等于空串的前缀、后缀、字串
  • 串的运算:
    • 连接(Concatenation):$xy$即为将$y$附加到$x$的后面
    • 指数运算(幂运算):通过递归定义,特殊地,$s^0 = \varepsilon$
  • 语言的运算:
    • 并:$L \cup M = \lbrace s | s \in L \vee s \in M \rbrace$
    • 连接:$LM = \lbrace st | s \in L \wedge t \in M \rbrace$
    • Kleene闭包:$L^* = \bigcup\limits_{i=0}^{\infty} L^i$
    • 正闭包:$L^+ = \bigcup\limits_{i=1}^{\infty} L^i$

正则表达式和正则定义

基础部分:

  • $\varepsilon$是一个正则表达式,$L(\varepsilon) = \lbrace \varepsilon \rbrace$
  • 如果$a$是$\Sigma$上的一个符号,那么$a$是正则表达式,$L(a) = \lbrace a \rbrace$

递归定义:

  • 选择:$(r) | (s)$,$L((r) | (s)) = L(r) \cup L(s)$
  • 连接:$(r)(s)$,$L((r)(s)) = L(r)L(s)$
  • 闭包:$(r)^*$,$L((r)^*) = (L(r))^*$
  • 括号:$(r)$,$L((r)) = L(r)$

运算的优先级:* > 连接 > |

正则集合:可以用一个正则表达式定义的语言

例子:C语言表示符的正则定义

  • $letter\_ \rightarrow A\ |\ B\ |\ \dots\ |\ Z\ |\ a\ |\ b\ |\ \dots\ |\ z\ |\ \_$
  • $digit \rightarrow 0\ |\ 1\ |\ \dots\ |\ 9$
  • $id \rightarrow letter\_ (letter\_\ |\ digit)^*$

正则表达式的扩展

  • 一个或多个实例:单目后缀$^+$:$r^+ = r r^*$
  • 零个或一个实例:$r? = \varepsilon | r$
  • 字符类:
    • $[a_1a_2 \dots a_n]$
    • $[a-z]$

正则表达式的扩展不会提高正则表达式的表达能力。

词法单元的识别(状态转换图)

词法分析器要求能够检查输入字符串,在其前缀中找出和某个模式匹配的词素,并存储到词汇表里。

定义空白:$ws \rightarrow (\texttt{blank}\ |\ \texttt{tab}\ |\ \texttt{newline})^+$,当词法分析器识别出这个模式时,不返回词法单元。

状态转换图

  • 状态(State):表示在识别词素时可能出现的情况
  • 边(Edge):从一个状态指向另一个状态

保留字和标识符的识别

保留字也符合标识符的模式,识别标识符的状态转换图也会识别保留字。

解决方法:

  • 在符号表中先填保留字,并指明他们不是普通标识符。
  • 为保留字建立独立的、高优先级的状态转换图。

词法分析器的体系结构

  • 从转换图构造词法分析器的方法
    • 变量state记录当前状态
    • 一个switch根据state的值转到相应的代码
    • 每个状态对应于一段代码
      • 根据读入的符号,确定下一个状态
      • 如果找不到相应的边,则调用fail()进行错误处理
    • 进入某个接受状态时,返回相应的词法单元,可能需要回退forward指针
  • 实际是在模拟状态转换图的运行

有穷自动机

  • 本质上和状态转换图相同,但有穷自动机只回答Yes/No
    • 不确定的有穷自动机(NFA):边上的标号没有限制,一个符号可出现在离开同一个状态的多条边上,$\varepsilon$可以做标号
    • 确定的有穷自动机(DFA):对于每个状态和没个符号,有且只有一条边
  • 两种自动机都识别正则语言
    • 对于每个可以用正则表达式描述的语言,均可用某个NFA或DFA来识别;反之亦然

NFA的定义:

  • 一个有穷的状态集合$S$
  • 一个输入符号集合$\Sigma$
  • 转换函数:对于每个状态和符号,给出相应的后继状态集合
  • $S$中的某个状态$s_0$被指定为开始状态/初始状态
  • $S$的一个子集$F$被指定为接受状态集合

NFA的表示方式:

  • 状态转换图
  • 转换表

一个NFA能够接受字符串,当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径,且该路径各条边上的标号按顺序组成该字符串。

NFA接受的语言:从开始状态到达接受状态的所有路径的标号串的集合,即该NFA接受的字符串的集合。

一个NFA被称为DFA,如果

  • 没有标号为$\varepsilon$的转换,并且
  • 对于每个状态$s$和每个输入符号$a$,有且仅有一条标号为$a$的离开$s$的边

NFA到DFA

算法中的基本操作:

  • $\varepsilon-closure(s)$:从NFA状态$s$开始,只通过$\varepsilon$转换能到达的NFA状态集合
  • $\varepsilon-closure(T)$:从$T$中某个状态$s$开始,只通过$\varepsilon$转换能到达的NFA状态集合
  • $move(T, a)$:从$T$中某个状态$s$开始,通过一个标号$a$的转换能够到达的NFA状态集合

状态的可区分:

  • 如果存在串$x$,使得从$s_1$和$s_2$一个到达接收状态而另一个到达非接受状态,那么$x$就区分了$s_1$和$s_2$。
  • 如果存在一个串区分$s$和$t$,那么$S$和$t$就是可区分的。
  • 不可区分的两个状态就是等价的,可以合并。

DFA最小化算法:

  • 通过迭代把所有可区分的状态分开:
    • 基本步骤:$\varepsilon$区分了接收状态和非接受状态
    • 归纳步骤:如果$s$和$t$是可区分的,且$s'$到$s$、$t'$到$t$有标号为$t$的边,那么$s'$和$t'$也是可区分的
  • 最终没有区分开的状态就是等价的
  • 从划分得到的等价类中选取代表,并重建DFA