Stanford Compiler Week 2 Lexical Analysis and Finite Automata

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

这次回顾第二周的内容，这一周主要介绍词法分析和有限自动机。

词法分析

例子

考虑如下代码：

if (i == j)
	Z = 0;
else
	Z = 1;

代码文本表示为：

\tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1;

我们希望划分成如下形式：

符号

• 符号类

  • 英语中：

    Noun, verb, adjective,...

  • 编程语言中：

    Identifier, Keywords, '(', ')', Numbers,...

• 符号类对应于一组字符串

• 标识符(Identifier)：

  • 以字母开头的字母或数字字符串

• 整数(Integer)：

  • 非空数字串

• 关键词(Keyword)：

  • “else”,”if”,”begin”

• 空白(Whitespace)：

  • 非空的空格、换行符和制表符序列

• 根据符号对程序子串进行分类

• 向解析器传递符号

  

• 实现必须做两件事：

  • 识别符号对应的子串
    • 词素(lexemes)
  • 识别每个词素的符号类

习题

首先有$11$个空白，其次有$1$个关键词(while)，所以选择第一项。

词法分析例子

1. 目标是对字符串进行划分。这是通过从左向右读取，一次识别一个符号来实现的。
2. 可能需要“提前看”来决定一个符号的结束和下一个符号的开始。

例1：

if (i == j)
	Z = 0;
else
	Z = 1;

例如分析==，只看第一个=是不够的，还需要看后面一个=。

例2：

DECLARE (ARG1,. . ., ARGN)

DECLARE是关键字还是数组引用？

例3：

C++模板语法：

Foo <Bar>

C++流语法：

cin >> var;

考虑如下例子：

Foo <Bar <Bazz>>

最右侧的>>读入也需要提前看。

正则语言

• 词法结构=符号类
• 我们必须说一个符号类中有多少组字符串
  • 使用正则语言

正则表达式

首先介绍如下集合以及操作：

• 单个字符

  $$'c'=\{"c"\}$$

• Epsilon

  $$\epsilon=\{""\}$$

• 并集

  $$A+B=\{a|a\in A\}\cup \{b|b\in B\}$$

• 拼接

  $$AB=\{ab|a\in A,b\in B\}$$

• 迭代(Iteration)

  $$\begin{aligned} A^{\star}&=\bigcup_{i\ge 0}A^i\\ A^i&= \underbrace{A\ldots A}_{i次}\\ A^0&= \epsilon \end{aligned}$$

• 补充一点：

  $$A^+=AA^{\star}$$

定义：

$\Sigma$上的正则表达式是包括如下内容的最小表达式集：

$$R=\epsilon | 'c'|(R+R)|RR|R^{\star}$$

其中$c\in \Sigma$。

总结

• 正则表达式指定正则语言
• 五种构造
  • 2个基本情形
    • 空字符串和单字符字符串
  • 3个复合表达式
    • 并集，拼接，迭代

习题

$$(0+1)^{\star} 1(0+1)^{\star} =\{(i个1或0) 1(j个1或0) |i\ge 0,j\ge 0\}$$

所以应该选择第三项。

形式语言

定义：令$\Sigma$是一组字符（字母）的集合，关于$\Sigma$的语言是由$\Sigma$中字符构成的字符串的集合。

来看几个例子：

字母	语言
英语字母	句子
ASCII	C语言

意义函数$L$将语法（正则表达式）映射到语义，考虑之前的例子：

$$\begin{aligned} L(\epsilon) &= \{""\}\\ L('c') &= \{"c"\}\\ L(A+B)&=L(A)\cup L(B)\\ L(AB)&=\{ab|a\in L(A),b\in L(B)\}\\ L(A^{\star})&=\bigcup_{i\ge 0}L(A^i) \end{aligned}$$

• 为什么使用意义函数？
  • 明确什么是语法，什么是语义。
  • 允许我们把符号作为一个单独的问题来考虑。
  • 因为表达式和其含义不是一一对应的。

词法规范

1. 关键词：”else”,”if”,”begin”等。

   $$\text{'if'}+\text{'else'}+\text{'then'}+\ldots$$

2. 整数：非空数字串。

   记

   $$\text{digits}='0'+'1'+'2'+'3'+'4'+'5'+'6'+'7'+'8'+'9'$$

   那么整数可以表达为

   $$\text{digits}^+=\text{digits}\ \text{digits}^{\star}$$

3. 标识符：以字母开头的字母或数字字符串。

   记

   $$\text{letter}=[a-zA-Z]$$

   那么标识符可以表达为

   $$\text{letter}(\text{letter+digit})^{\star}$$

4. 空白：非空的空格、换行符和制表符序列。

   $$('\ '+'\text{\n}'+'\text{\+}')^{+}$$

Pascal例子

总结

• 正则表达式描述了许多有用的语言

• 正则语言是一种语言规范

  • 我们仍然需要一个实现

• 下一次：给定一个字符串$s$和一个rexp $R$，判断

  $$s\in L(R)?$$

习题

应该选择2,4

词法规范补充

回顾之前介绍的内容：

• 至少有一个：$A^+\equiv AA^{\star}$
• 并集：$A|B\equiv A+B$
• 选择：$A?\equiv A+\epsilon$
• 范围：$’a’+’b’+\ldots+’z’\equiv [a-z]$
• 排除范围：$[a-z]$补集合$\equiv [\text{^} {a-z}]$

回到上一部分的问题，解决上述问题的流程如下：

1. 为每个符号类的词素写一个rexp

   • $\text {Number = digit}^+$
   • $\text{Keyword = ‘if’ + ‘else’ +…}$
   • $\text{Identifier = letter(letter + digit)}^{\star}$
   • $\text{OpenPar}=’(‘$
   • $\ldots$

2. 构造$R$，匹配所有符号的所有词素

   $$\begin{aligned} R&=\text{Keyword + Identifier + Number + …}\\ &=R_1+R_2+... \end{aligned}$$

3. 假设输入为$x_1\ldots x_n$，对$1\le i\le n$，判断

   $$x_1\ldots x_i \in L(R)$$

4. 如果成功，那么我们知道

   $$x_1\ldots x_i \in L(R_j)，对某个j$$

5. 从输入中删除$x_1\ldots x_i$，返回步骤(3)

该步骤有如下几个问题：

• 使用多少输如？

  • 例如$x_1\ldots x_i, x_1\ldots x_j \in L(R)$，那么应该选择哪个？答案是”Maximal Much”，即选择长度较大的输入。

• 使用哪个符号？

  • 例如$x_1\ldots x_i\in L(R_j),L(R_k)$，那么应该选择哪个？答案是根据符号的优先级（事先定义），例如输入$\in L(\text{Keywords}),L(\text{Identifiers})$，那么通常是选择$L(\text{Keywords})$

• 如果没有规则匹配？

  • 例如$x_1\ldots x_i\not \in L(R)$。通常我们定义一种新的符号： $$\text{Error}=[\text{all strings not in the lexical spec}]$$ 并将其优先级设置为最低。

总结

• 正则表达式是字符串模式的简明表示法
• 用于词法分析需要小的扩展
  • 解决歧义
  • 错误处理
• 已知良好的算法
  • 仅要求输入单次传递
  • 每个字符的操作少（查表）

有限自动机

• 正则表达式=规范
• 有限自动机=实现
• 一个有限自动机由
  • 输入字母$\Sigma$
  • 有限状态集合$S$
  • 起始状态$n$
  • 接收状态$F\subseteq S$
  • 转移集合$\text{state}\to^{\text{input}}\text{state}$

转移说明

• 转移

  $$s_1\to^a s_2$$

• 读作：在状态$s_1$，如果输入为$a$，则进入状态$s_2$

• 如果输入结束且处于接受状态$\Rightarrow\text{accept}$

• 否则$\Rightarrow\text{reject}$

图形符号：

例子

• 一个有限自动机，它接受任意数量的$1$后跟一个$0$
• 字母表：$\{0,1\}$

DFA与NFA

• 另一种转移：$\epsilon-$移动

  

根据$\epsilon$移动，可以将自动机分为两类：

• 确定性有限自动机(DFA)
  • 每个状态在每个输入下进行转移
  • 没有$\epsilon-$移动
  • 
• 非确定性有限自动机(NFA)
  • 在给定状态下，一个输入可以有多个转移
  • 可以有$\epsilon-$移动（不是一定有）
  • 

两者的特点如下：

• DFA在状态图上只走一条路径

• NFA可以选择路径

  • 如果某些选择导致accept状态，则accept NFA

• NFA会进入多个状态

  

  $A$为起始状态

总结

• NFA和DFA识别同一组语言
  • 正则语言
• DFA执行速度更快
  • 没有可供考虑的选择
• NFA通常较小
  • 指数级减少

习题

感觉应该选择第一项。

正则表达式到NFA

我们希望完成如下转换：

这里先讨论正则表达式到NFA的部分。

转换

思路：对每个正则表达式，定义一个等价的NFA：

• 符号：正则表达式$M$的NFA：

  

下面分别讨论：

• 对于$\epsilon$：

  

• 对于输入$a$：

  

• 对于$AB$：

  

• 对于$A+B$：

  

• 对于$A^{\star}$：

  

例子

考虑正则表达式

$$(1+0)^{\star} 1$$

习题

右上。

NFA到DFA

这部分讨论另一部分：

定义：$\epsilon-\text{closure}(A)$定义为从$A$出发，通过$\epsilon-$移动到达的状态。

考虑下图：

$$\begin{aligned} \epsilon-\operatorname{closuce}(B)&=\{B, C, D\}\\ \epsilon-\text { closure }(G)&=\{A, B, C, D, G, H, I\} \end{aligned}$$

现在定义转换方式：

• NFA

  • 状态集合：$S$

  • 起点：$s\in S$

  • 终点集合：$F\subseteq S$

  • 定义集合

    $$a(X)=\{y | x\in X \and x\to^a y\}$$

  • 以及$\epsilon-\text{closure}$

• DFA

  • 状态：$S$的子集
  • 起点：$\epsilon-\text{closure}(s)$
  • 终点：$\{X|X\cap F\neq \varnothing\}$，其中$X\subseteq S$
  • 状态转移：$X\to^a Y$，如果$Y=\epsilon-\text{closure}(a(X))$

例子

实现有限自动机

• DFA可以由2D表T实现

  • 一维是状态

  • 另一维为输入符号

  • 对于每个转移$\mathrm{S}_{\mathrm{i}} \rightarrow^{\mathrm{a}} \mathrm{S}_{\mathrm{k}}$，定义$\mathrm{T}[\mathrm{i}, \mathrm{a}]=\mathrm{k}$

    

例子

更经济的实现如下：

另一个例子：

总结

• NFA->DFA转换是关键
• 工具在速度和空间之间进行权衡
  • DFA：更快，不太紧凑。
  • NFA：更慢，简洁。