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

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

词法分析

例子

考虑如下代码:

1
2
3
4
if (i == j)
Z = 0;
else
Z = 1;

代码文本表示为:

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

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

符号

  • 符号类

    • 英语中:

      1
      Noun, verb, adjective,...
    • 编程语言中:

      1
      Identifier, Keywords, '(', ')', Numbers,...
  • 符号类对应于一组字符串

  • 标识符(Identifier):

    • 以字母开头的字母或数字字符串
  • 整数(Integer):

    • 非空数字串
  • 关键词(Keyword):

    • “else”,”if”,”begin”
  • 空白(Whitespace):

    • 非空的空格、换行符和制表符序列
  • 根据符号对程序子串进行分类

  • 向解析器传递符号

  • 实现必须做两件事:

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

习题

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

词法分析例子

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

例1:

1
2
3
4
if (i == j)
Z = 0;
else
Z = 1;

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

例2:

1
DECLARE (ARG1,. . ., ARGN)

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

例3:

C++模板语法:

1
Foo <Bar>

C++流语法:

1
cin >> var;

考虑如下例子:

1
Foo <Bar <Bazz>>

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

正则语言

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

正则表达式

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

  • 单个字符

  • Epsilon

  • 并集

  • 拼接

  • 迭代(Iteration)

  • 补充一点:

定义:

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

其中$c\in \Sigma$。

总结

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

习题

所以应该选择第三项。

形式语言

定义:令$\Sigma$是一组字符(字母)的集合,关于$\Sigma$的语言是由$\Sigma$中字符构成的字符串的集合。

来看几个例子:

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

意义函数$L$将语法(正则表达式)映射到语义,考虑之前的例子:

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

词法规范

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

  2. 整数:非空数字串。

    那么整数可以表达为

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

    那么标识符可以表达为

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

Pascal例子

总结

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

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

    • 我们仍然需要一个实现
  • 下一次:给定一个字符串$s$和一个rexp $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$,匹配所有符号的所有词素

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

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

  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)$。通常我们定义一种新的符号:并将其优先级设置为最低。

总结

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

有限自动机

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

转移说明

  • 转移

  • 读作:在状态$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}$:

例子

考虑正则表达式

习题

右上。

NFA到DFA

这部分讨论另一部分:

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

考虑下图:

现在定义转换方式:

  • NFA

    • 状态集合:$S$

    • 起点:$s\in S$

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

    • 定义集合

    • 以及$\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:更慢,简洁。

本文标题:Stanford Compiler Week 2 Lexical Analysis and Finite Automata

文章作者:Doraemonzzz

发布时间:2020年09月05日 - 23:13:00

最后更新:2020年09月06日 - 18:41:57

原始链接:http://doraemonzzz.com/2020/09/05/Stanford Compiler Week 2 Lexical Analysis and Finite Automata/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。