1. 词法分析的作用

image.png|800

1.1 常见的概念

  • 词素
    image.png|800
  • 词法单元
    image.png|800

1.1.2 词法单元的属性

一个模式匹配多个词素时，必须通过属性来传递附加的信息。属性值会被用于语义分析、代码生成等阶段

  • 不同的目的需要不同的属性，所以属性值通常是一个结构化数据
    image.png|800

2. 词法单元的规约（正则表达式）

  • 模式：词法单元对应的词素可能具有的形式
  • 可以用正则表达式来表示

2.1 相关概念

字母表：所有合法输入的集合
串：字母表中符号组成的又穷序列
image.png|800

  • 串的运算
    image.png|800

2.2 正则表达式

是一种描述词素模式的重要表示方法
image.png|800

  • 正则表达式可以由较小的正则表达式递归构建
    image.png|800
例子：

image.png|750

性质：
  • 如果两个正则表达式表示同样的语言，则r = s
    image.png|700
  • 扩展运算符
    image.png|800

image.png|800

3. 词法单元的识别

词法分析器要求能够检查舒服的字符串，在前缀中找出和某个模式匹配的词素
image.png|800

3.1 状态转换图

状态转换图：实现模式匹配的最好的方法
|800

例子

image.png|700

保留字和标识符的识别
  • 很多时候程序设计语言的保留字也符合标识符的匹配模式
  • 所以需要在符号表中预先填写保留字，指明它们并不是普通的标识符
  • 为保留字建立单独的状态转换图，并设定保留字的优先级高于标识符

3.2 有穷自动机

本质上等价于状态转换图
区别在于：

  • 自动机是识别器，对每个输入串回答 yes or no

分为两类：

NFA：不确定
DFA：确定

image.png|800|700

3.2.1 不确定的有穷自动机

NFA 由以下几部分组成

  • 一个有穷的状态集合S
  • 一个输入符号集合Σ（input alphabet）
  • 转换函数（transition function）对于每个状态和Σ ∪ {ε}中的符号，给出相应的后继状态集合
  • 一个状态S0被指定为开始状态/初始状态
  • S 的一个子集 F 被指定为接受状态
    image.png|700

自动机对输入字符串的接受

判断输入字符串能否到达终点，能到达则代表匹配

3.2.2 确定的有穷自动机DFA

  1. 对于一个输入，若有一个确定的状态转换，则为 DFA
  2. 没有ε

  3. 每一个 NFA 都有一个与之对应的 DFA

    例子

    image.png|750

4. 正则表达式到自动机

正则表达式可以简洁、精确地描述词法单元的模式
image.png|700

  • 所以需要将正则表达式转换为自动机

  • 步骤：

    1. 正则表达式到 NFA
    2. NFA 到 DFA

4.1 NFA 转换为 DFA——子集构造法

对 NFA 的模拟往往不如对 DFA 的模拟直接，除非转换花费更多的时间
image.png|800

  • 理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个。但是对于大部分应用，NFA和相应的DFA的状 态数量大致相同

image.png|800

4.2 正则表达式到 NFA

输入：字母表Σ上的一个正则表达式 r
输出：一个接受 L (r) 的 NFA N

  • 基本思想
    image.png|700
  • 归纳规则
    image.png|700

4.3 基于 DFA 的模式匹配器的优化

  • DFA 化简：状态数最小化
  • 等价的 DFA 可能具有不同的状态个数

  • 任何正则语言都有一个唯一的状态数目最少的 DFA

    DFA 状态最小化

    image.png|700

  • 最小化算法
    image.png|700
    image.png|700