第三章: 词法分析

词法分析器作用(正则表达式)

  • 读入: 字符流
  • 处理: 组成词素
    • 过滤: 空白, 换行, 制表符, 注释
    • 符号: 词素添加到符号表
  • 输出: 词法单元序列
  • 独立的词法分析器
    • 逻辑上独立于语法分析, 实践上与语法分析在同一趟
    • 好处
      • 简化编译器设计: 由词法分析器完成简单处理
      • 提高效率: 词法简单, 高效实现, 用有穷自动机
      • 可移植: 组合多个语法分析器
  • 词法单元: <单元名, [属性值]>
    • 单元名: 种类
    • 属性: 用于语义分析/代码生成等, 是结构化数据
  • 模式: 描述词素的形式
  • 词素: 源程序的字符序列, 匹配于模式, 被识别为词法单元的实例

词法单元的归约(状态转换图)

串和语言

  • 字母表: 有穷的符号集合(任意的有限集)
  • (字母表上的)串$s$: 符号的有穷序列
    • 长度: $|s|$, $s$中的符号出现次数, 可重复
    • 空串$\varepsilon$
  • 语言: 串的可数集合
  • 串术语
    • 前缀: 从尾部删除0或多个符号, 得到的串(可为原串或空串)
    • 后缀: 从前部删除0或多个符号, 得到的串(可为原串或空串)
    • 字串: 删除某个前缀和某个后缀得到的串(可为原串或空串)
    • 真前缀, 真后缀, 真子串: 不等于原串, 不为空串
    • 子序列: 任意删除0或多个符号
  • 串运算
    • 连接: $xy$
    • 幂运算: $s^0=\varepsilon$, $s^1=s$, $s^i=s^{i-1}s$

语言上的运算

  • $L$和$M$的并: $L\cup M=\{s|s\in L \vee s\in M\}$
  • $L$和$M$的连接: $LM=\{st|s\in L \wedge t\in M\}$
  • $L$的Kleene闭包: $L^*=\bigcup_{i=0}^\infty L^i$
  • $L$的正闭包: $L^+=\bigcup_{i=1}^\infty L^i$

正则表达式和正则定义

  • 正则表达式的定义
    • 基本部分
      • $\varepsilon$是正则表达式, $L(\varepsilon)=\{\varepsilon\}$
      • $a$是$\Sigma$中的符号, $a$是正则表达式, $L(a)=\{a\}$
    • 归纳步骤
      • 选择: $(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)$
    • 优先级: 闭包>连接>选择
    • 正则集合: 可以用一个正则表达式定义的语言
  • 正则定义
    • 书写方便, 将一个表达式定义为变量: $d_i\to r_i$
    • 其中
      • $d_i\notin \Sigma$
      • $r_i$定义于$\Sigma\cup\{d_1, \cdots , d_{i-1}\}$

正则表达式的拓展

  • 基本运算符: 选择, 连接, Kleene闭包
  • 拓展运算符
    • 一个或多个: $r^+\equiv rr^*$
    • 零个或一个: $?\equiv \varepsilon | r$
    • 字符类: $[a_1a_2\cdots a_n]\equiv a_1|a_2|\cdots|a_n$, $[a-e]\equiv a|b|c|d|e$
    • 表示更简洁, 不增强表达能力(语法糖?)

词法单元的识别

  • 在源代码的前缀中, 找出与某个模式匹配的词素
    • 正则定义模式
  • 状态转换图
    • 状态: 识别词素过程中, 阶段性的情况
      • 开始状态
      • 接受状态/最终状态: 找到词素
      • 带*的接受状态, 则最后读入的符号不在词素中
    • 边: 状态到状态
      • 边上的符号: 遇到该符号, 则沿该边走
  • 保留字和标识符的识别
    • 符号表中先填保留字, 并指明他们不是普通标识符
    • 专门为保留字建立的, 独立高优先级的状态转换图
  • 从转换图构造词法分析器(模拟状态转换图的运行)
    • 变量state记录当前状态
    • 一个switch根据State值转到相应代码
      • 状态的代码: 根据读入符号, 确定下一个状态(边), 找不到则fail(), 进行错误恢复
    • 进入接受状态时, 返回相应词法单元
      • 有*标记, 则回退forward指针

词法分析器生成工具及设计

  • 词法分析工具: Lex
    • 声明部分
      • 常量: 表示常数的标识符
      • 正则定义
    • 转换规则
      • 模式{动作}
        • 模式是正则表达式, 动作是表示识别到相应模式时采取的处理方式, C语言代码表示
    • 辅助函数
      • 动作中使用的函数

有穷自动机

  • 本质上和状态转换图相同, 但只回答Yes/No
    • NFA 不确定的有穷自动机: 边上的标号无限制, 一个符号可出现在离开同一状态的多条边上, 空字符可做标号
    • DFA 确定的有穷自动机: 每个状态及每个符号, 有且仅有一条边(或最多只有一条边)
  • 两种自动机都识别正则语言

    NFA

  • 定义
    • 有穷状态集合$S$
    • 输入符号集合$\Sigma$
    • 转换函数: 对于每个状态和$\Sigma\cup \{\varepsilon\}$, 给出后继状态的集合
    • $s_0\in S$被定义为初始状态
    • $F\subset S$被定义为接受状态
  • 接受输入
    • 接受$x$, 当且仅当存在从开始状态到结束状态的路径, 边上字符恰好组成$x$
    • 接受的语言: 开始状态到任一结束状态的所有可能路径

      DFA

  • 定义: NFA的特例
    • 没有标号为$\varepsilon$的转换
    • 每个状态的每个标号, 只有一个后继状态(只有一条离开的边)

从正则表达式到DFA

  • 正则->NFA->DFA

NFA到DFA: 子集构造法

  • 基本思想: 得到的DFA的每个状态和NFA的状态子集对应
    • 并行地模拟
    • $\varepsilon$转换, 添加进当前状态子集
    • 对于当前子集, 考虑每个字母$a$:
      • 其中每个NFA状态, 由该字母, 将到达一些状态
      • 这些状态的集合, 即为DFA中, 当前状态子集于字母$a$的后继状态
    • 不断迭代即可
  • 算法操作
    • $\varepsilon-\mathrm{closure}(s)$: 从状态$s$开始, 只通过$\varepsilon$转换能到达的NFA状态集合
    • $\varepsilon-\mathrm{closure}(T)$: 从集合$T$中状态$s$开始, 只通过$\varepsilon$转换能到达的NFA状态集合
    • $\mathrm{move}(T, a)$: 从集合$T$中状态$s$开始, 通过标号为$a$转换能到达的NFA状态集合
  • 算法
    • $\varepsilon-\mathrm{closure}(T)$
      • 实际上是从一个顶点集$T$的图搜索过程, 只考虑标号$\varepsilon$的边
    • 整个算法
      • Dstate: DFA状态集合
      • 初始化: Dstate中仅有$\varepsilon-\mathrm{closure}(s_0)$
      • while Dstate中有未加标记的状态$T$
        • 给$T$加标记
        • for 每个输入符号$a$
          • U=$\varepsilon-\mathrm{closure}(\mathrm{move}(T, a))$
          • if $U$不在Dstate中, 则加入之, 不加标记
          • Dtran[T,a]=U, 为新的边和状态
  • 开始与接受
    • 含有NFA开始状态的状态子集, 为DFA开始状态
    • 含有NFA接受状态的状态子集, 为DFA接受状态

正则表达式到NFA

  • 递归构造: 基本规则, 归纳
  • 基本规则部分
    • 表达式$a$或$\varepsilon$: start->(i)–[a]–>((f))
  • 归纳部分
    • 选择$s|t$
      • 新的开始状态, 2个$\varepsilon$, 分别到$s$$t$的表达式开始状态
      • 两个表达式的接受状态, 2个$\varepsilon$, 都到新的接受状态
    • 连接$st$
      • $s$的结束作为$t$的开始
      • $s$开始作为新开始, $t$结束作为新结束
    • 闭包$s^*$
      • 新状态: 新开始状态–[$\varepsilon$]–>$s$开始状态, $s$接受状态–[$\varepsilon$]–>新接受状态
      • 0次匹配: 新开始状态–[$\varepsilon$]–>新接受状态
      • 多次匹配: $s$接受状态–[$\varepsilon$]–>$s$开始状态
  • NFA合并
    • 新开始状态, 到各个表达式的开始状态, 有$\varepsilon$连接
    • 不同的接受状态, 代表不同的模式
  • DFA状态合并: 状态的区分
    • 一个串, 从两个状态, 一个能到接受状态, 一个不能, 则这两个状态不一样
    • 基本步骤: 空串区分接受和其他
    • 如果$s$和$t$可区分, $s->s’$, $t->t’$均有标号$a$的边, 则二者可区分
    • 最终没有被分开的就是等价的
      • 死状态都等价
      • 等价类中的状态, 选取一个代表即可
  • 最小化算法
    • 设置初始划分: 接受跟别的不一样
    • 迭代, 不断划分
      • 对于等价类集合中的每个元素$G$
        • 细分$G$, 使得$G$中$s$, $t$仍在同一组中, iff, 对任意输入$a$, $s$, $t$到达等价类集合中的同一组
        • 新等价类集合, 将$G$换为细分结果
    • 如果结果没变, 则完成, 否则迭代
  • 选代表构造
    • 开始状态: 包含原开始状态的组的代表
    • 接受状态: 原接受状态
    • 转换关系: 原s–[a]–>t, t所在组代表为r, 则新s–[a]–>r
  • 词法分析器: 多个接受状态
    • 这些接受状态之间互相不等价