词法分析器 | Uonlra‘s Blog

type

status

date

slug

summary

概述

词法分析器的任务是将字符流转换为输入语言的单词流。

每个单词都必须归类到语法范畴中（syntactic category），

关键词：词法分析器；有限自动机；正则表达式；不动点

简介

在编译器中，词法分析器是唯一的在一趟流程会操作输入程序的中的每个字符的处理过程。主要原因是因为词法分析器执行的任务相对简聚合字符以形成源语言中的单词和标点。）

💡

识别器可以在字符流中识别特定单词的程序

编译器中的词法分析器读取由字符组成的输入流，并产生包含单词的输出流时完成的聚集和分类操作，词法分析器会应用一组描述输入程序设计语言的词法结构（微语法）的规则。

💡

语法范畴根据单词的语法用途对单词进行的分类微语法语言的词法结构

大多数的程序设计语言的为微语法都很简单（相邻的字母由左到右聚集在一起），都是将字符聚集成单词。

在一些程序设计语言中，一些单词称为关键字或者保留字，为了识别它们，词法分析器可以查找字典，或者将关键字自建编码到其微语法中。

💡

关键字为特定语法目的而保留的单词，不能用作标识符

识别单词

识别单词通常是逐字符列出的公式。

下面是一个识别关键字“new” 的识别器：

s3是接受状态，仅当输入为 “new” 时，识别状态器才会到达s3, 如果某个过程无法匹配，则相应的阶段进入错误状态。

为了识别多个单词，我们可以从同一个给定状态发出多条边。

下图为能同时识别new 和 not 的识别器，转移图如下：

通过合初始状态并重新找到所有的状态，就可以合并用于不同单词的识别器。

识别器的形式化

转移图充当了它的实现代码的抽象。它还可以看作是形式化的数学对象，称为有限自动机（定义识别区的规格）。

有限自动机（FA）是一个五元组（S, ∑, δ, S0, SA).

💡

有限自动机 (finite automaton) 识别器的一种形式化方法，包含一个有限状态集、一个字母表、一个转移函数、一个起始状态和一个或多个接受状态。

对于每个输入字符，FA都会进行一次状态转移。假定可以高效地实现FA，识别器的运行时间应该与输入字符串的长度成正比。

💡

词素对FA识别的一个单词来说，即单词对于的实际文本。

有环的转移图更为复杂，这可以通过while来实现这种控制流。

类Algol语言中，支配标识符名的规则在简化后这样表示：标识符以一个字母字符开头，后接零或者多个字母数字字符。

通过RE(正则表达式)的符号表示法来描述语言，称为正则语言。它等效于FA,简答的识别器有简单的RE规则。

由单个new单词组成的语言，用RE描述时，可以写作 “new”。在RE中，两个字符彼此相邻意味着对应的语言的单词中，二者也会以相同的顺序出现。

包括两个单词new和while的语言，用正则表达式可以写作new or while.

包括new或not的语言可以写作new|not。其他的写法也可能。

程序设计语言中可能出现的RE:

: / ; / ? / = > / ( ) / { }/ [ ]

关键字：

if while this integer instanceof

可以用 ”(x)^*“ 来表示 ”x的零次出现或者多次出现。”*“运算符被称为柯林闭包。

即在一个语言集合L里的任意字符串重复0到n次组合，可以重复。可能出现无穷多次的重复组合的情形。

一个RE由三个基本的操作构建而成。

选择两个字符串集合R和S的交替或并集，记作 R|S.

连接两个字符串集合R和S的交替或并集，记作RS。

闭包集合R的柯林闭包，记作R^*，把R和自身连接零次或多次形成的所有集合取并集。

💡

有限闭包对任一整数i，RE R^i 指定了R出现一次到i次的情形。正闭包 RE R^+表示R出现一次或者多次。

为了消除奇异性，括号有最高的优先级，然后是闭包，连接，选择。

现有如下RE:

其对应的FA 如下：

如何确定FA的性能好坏?

FA的运行开销与输入长度成正比，和生成FA的RE长度或复杂度无关。

用枚举法设计RE固然不错但是，当我们处理多个寄存器时，就不尽人意了。

正则表达式在许多操作下都是封闭的，如果我们将操作应用到一个或者一组RE,结构也显然是RE。

这些操作包括连接，并集，补集操作和闭包操作。

柯林闭包和有限闭包操作下，正则表达式也是封闭的。

💡

完全FA 显式包含所有错误转移的FA。

使用正则表达式的基本操作来创建一个匹配六个字符的模式 (?:[a-zA-Z0-9_]{6})

正则表达式和语法分析器关系图：

确定性FA(DNF)，非确定性FA(NFA)

NFA 非确定性有限自动机

可以在FA中使用针对∈输入的转移来合并FA,并组成用于更复杂RE的FA。

在FA1的接受状态添加一个针对输入 ∈的转移m,转移到FA的初始状态。

💡

∈转移针对空串输入∈进行的转移，不会改变输入流中的的读写位置

考虑 a* 和 ab 的FA

当我们用∈来合并它们，形成一个处理a*ab的FA。

这时FA有两种不同的转移。

在每一步，FA都会检查当前的字符。FA的状态隐含了左上下文（left context），即它以及处理过的那些字符。

💡

非确定性FA 允许在空串输入∈上进行转移的FA,其状态对同一字符输入可能有多种转移。确定性FA 转移函数为单值的FA称为DFA。DFA不允许∈转移

针对FA的行为，现有的两种模型：

每次NFA必须进行非确定性转移时，如果有使得输入字符串转向接受状态的转移存在，则采用这样的转移。

每次NFA必须进行非确定性转移时，NFA都会克隆自身，以追踪每个可能的转移。

NFA和DFA的等价性：

NFA和DFA在表达力上是等价的。任何DFA都是NFA的一个特例。任何NFA都可以通过一个DFA模拟。

Thomson构造法

要让RE得到实现完成的词法分析器，首先必须从这个RE导出一个NFA.

Thompson构造法有一个用于构造对应单字母的RE的NFA，还有一种NFA上的转换，模拟了连接、选择和闭包等用于RE运算符的效果。

每个NFA都有一个起始状态和一个接受状态。除了进人起始状态的初始转移之外，没有其他转移。没有从接受状态发出的转移

连接早先构建的对应于一些组件RE的NFA时，总是使用∈ 转移来连接前一个NFA的接受状态和后一个NFA的起始状态

个状态至多有两个进入该状态和两个退出该状态的e转移，对于字母表中的每个符号，至多有一个进入该状态和一个退出该状态的转移

a(b|c)*

概述

简介

识别单词

识别器的形式化

NFA 非确定性有限自动机

Thomson构造法

Uonlra

Notion 交流频道

加入社群讨论分享