虎书第2章《词法分析》笔记

源代码的分析一般有几种?

分析一般分为以下三种:

词法分析: 将源代码分解为一个个独立的词法符号
语法分析: 分析程序的短语结构
语义分析: 推算程序的含义

为什么要将词法分析和语法分析分离?

词法分析是以字节流作为输入, 生成一系列的名字, 关键字和标点符号, 同时抛弃单词之间的空白字符和注释. 程序中的每个地方都可能出现空白字符和注释, 如果让语法分析来处理它们就会使得语法分析过于复杂, 所以要将词法分析从语法分析中分离出去.

什么是词法单词?

词法单词是字符组成的序列, 可以将其看作程序设计语言的文法单位. 程序设计语言的词法单词可以归类为有限的几组单词类型.

类型	例子
ID	foo n14 last
NUM	73 0 00 515 082
REAL	66.1 .5 10. 1e67 5.5e-10
IF	if
COMMA	,
NOTEQ	!=
LPAREN	(
RPAREN	)

我的理解: 词法分析就是要将源代码尽可能的打散, 并获取最小的有意义的单元.

什么是保留字

像 IF, VOID, RETURN 这些就是程序设计语言的保留字 (reserved word), 它们不能被用户的源代码作为标识符使用.

词法分析器输出的例子

float match0(char *s)   /* find a zero */
{
    if (! strncmp(s, "0.0", 3))
        return 0.;
}

词法分析器发挥的单词流如下:

FLOAT ID(match0) LPAREN CHAR STAR ID(s) RPAREN
LBRACE
    IF LPAREN BANG ID(strncmp) LPAREN ID(s) COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN
        RETURN REAL(0.0) SEMI
RBRACE
EOF

用中文翻一下就是

浮点类型 标识符 (match0) 左括号 字符类型 星号 标识符 (s) 右括号
左大括号
    IF 关键字 左括号 取反 标识符 (strncmp) 左括号 标识符 (s) 逗号 字符串类型 (0.0) 逗号 数字类型 (3) 右括号 右括号
        返回 实数类型 (0.0) 分号
右大括号
文件结束

什么是语义值

就是某些单词除了类型, 还有带有一些值, 比如标识符类型有标识符的名称, 字符串类型有具体的字符串; 而有些单词则没有语义值, 比如 IF 和 RETURN 等.

做词法分析的时候除了要返回单词类型, 还要返回对应的语义值 (如果有的话).

什么是克林闭包

克莱尼星号 (Kleene 星号), 或称 Kleene 闭包, 德语称 Kleensche Hülle, 在数学上是一种适用于字符串或符号及字元的集合的一元运算. 当 Kleene 星号被应用在一个集合 ${\displaystyle V}$ 时, 写法是${\displaystyle V^{*}}$. 它被广泛用于正则表达式.

Kleene 星号应用于字符串集合的例子:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab",
                   "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Kleene 星号应用于字元集合的例子:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

什么是词法规则中的二义性, 如果消除二义性问题?

比如: if89 是应当将其看作一个标识符还是两个单词 if 和 89?

消除二义性有两种方法:

最长匹配: 初始输入子串中, 取可以与任何正则表达式匹配的那个最长的字符串作为下一个单词;
规则优先: 对特定的最长初始字符串, 第一个与之匹配的正则表达式决定了这个子串的单词类型, 也就是你书写的规则顺序会影响词法分析.

什么是确定的有限自动机 (DFA) 和不确定的有限自动机 (NFA)?

在确定的有限自动机 (DFA) 中, 不会有同一状态出发的两条边标记为相同的符号;
非确定有限自动机 (NFA) 是一种需要对从一个状态出发的多条标有相同符号的边进行选择的自动机.

Difference between DFA and NFA:

DFA	NFA
Each transition leads to exactly one state called as deterministic	A transition leads to a subset of states i.e. some transitions can be non-deterministic.
Accepts input if the last state is in Final.	Accepts input if one of the last states is in Final.
DFA stands for Deterministic Finite Automata.	NFA stands for Nondeterministic Finite Automata.
For each symbolic representation of the alphabet, there is only one state transition in DFA.	No need to specify how does the NFA react according to some symbol.
DFA cannot use Empty String transition.	NFA can use Empty String transition.
DFA can be understood as one machine.	NFA can be understood as multiple little machines computing at the same time.
In DFA, the next possible state is distinctly set.	In NFA, each pair of state and input symbol can have many possible next states.
DFA is more difficult to construct.	NFA is easier to construct.
DFA rejects the string in case it terminates in a state that is different from the accepting state.	NFA rejects the string in the event of all branches dying or refusing the string.
Time needed for executing an input string is less.	Time needed for executing an input string is more.
All DFA are NFA.	Not all NFA are DFA.
DFA requires more space.	NFA requires less space then DFA.
Dead state may be required.	Dead state is not required.
δ: QxΣ -> Q i.e. next possible state belongs to Q.	δ: QxΣ -> 2^Q i.e. next possible state belongs to power set of Q.
Backtracking is allowed in DFA.	Backtracking is not always possible in NFA.
Conversion of Regular expression to DFA is difficult.	Conversion of Regular expression to NFA is simpler compared to DFA.

在计算理论中, 非确定有限状态自动机或非确定有限自动机 (NFA) 是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机. 这区别于确定有限状态自动机 (DFA), 它的下一个可能状态是唯一确定的. 尽管 DFA 和 NFA 有不同的定义, 在形式理论中可以证明它们是等价的; 就是说, 对于任何给定 NFA, 都可以构造一个等价的 DFA, 反之亦然: 通过使用幂集构造. 两种类型的自动机只识别正则语言. 非确定有限自动机有时被称为有限类型的子移位 (subshift). 非确定有限状态自动机可推广为概率自动机, 它为每个状态转移指派概率.

非确定有限自动机是 Michael O. Rabin 和达纳·斯科特 (Dana Scott) 在 1959 年介入的, 他们证明了它与确定自动机的等价性.

NFA 同 DFA 一样, 消耗输入符号的字符串. 对每个输入符号它变换到一个新状态直到所有输入符号到被耗尽.

不像 DFA, 非确定意味着对于任何输入符号, 它的下一个状态不是唯一确定的, 可以是多个可能状态中的任何一个. 因此在形式定义中, 一般都谈论状态幂集的子集: 转移函数不提供一个单一状态, 而是提供所有可能状态的某个子集.

一种扩展的 NFA 是 NFA-λ(也叫做 NFA-ε或有ε移动的 NFA), 它允许到新状态的变换不消耗任何输入符号. 例如, 如果它处于状态 1, 下一个输入符号是 a, 它可以移动到状态 2 而不消耗任何输入符号, 因此就有了歧义: 在消耗字母 a 之前系统是处于状态 1 还是状态 2 呢? 由于这种歧义性, 可以更加方便的谈论系统可以处在的可能状态的集合. 因此在消耗字母 a 之前, NFA-ε可以处于集合{1, 2}内的状态中的任何一个. 等价的说, 你可以想象这个 NFA 同时处于状态 1 和状态 2: 这给出了对幂集构造的非正式提示: 等价于这个 NFA 的 DFA 被定义为此时处于状态 q={1, 2}中. 不消耗输入符号的到新状态的变换叫做λ转移或ε转移. 它们通常标记着希腊字母λ或ε.

接受输入的概念类似于 DFA. 当最后的输入字符被消耗的时候, NFA 接受这个字符串, 当且仅当有某个转移集合把它带到一个接受状态. 等价的说, 它拒绝这个字符串, 如果不管应用什么转移, 它都不能结束于接受状态.

机器开始于任意初始状态并读取来自它的符号表的符号的字符串. 自动机使用状态转移函数 T 来使用当前状态, 和刚读入的符号或空串来确定下一个状态. 但是,"NFA 的下一个状态不只依赖于当前输入事件, 还依赖于任意数目的后续输入事件. 直到这些后续事件出现才有可能确定这个机器所处的状态" [2]. 如果在自动机完成读取的时候, 它处于接受状态, 则称 NFA 接受了这个字符串, 否则称为它拒绝了这个字符串.

NFA 接受的所有字符串的集合是 NFA 接受的语言. 这个语言是正则语言.

对于所有 NFA 都可以找到接受同样语言的一个确定有限状态自动机 (DFA). 所以出于实现 (可能) 更简单的机器的目的把现存的 NFA 转换成 DFA 是可行的. 这是使用幂集构造进行的, 这可能导致在必需状态的数目上的指数增长. 幂集构造的形式证明在这里给出.

对于有状态的可数无限集合的非确定有限自动机, 幂集构造给出有状态的连续统的确定自动机因为可数无限集合的幂集是连续统:${\displaystyle 2^{\aleph_{0}}=\aleph_{1}}$. 在这种情况下, 为了使状态转移有意义, 状态的集合必须被赋予一个拓扑. 这种系统叫做拓扑自动机.

有多种方式实现 NFA:

转换成等价的 DFA. 在某些情况下这导致在自动机大小上的指数爆炸, 从而辅助空间正比于在 NFA 中状态的数目 (因为状态值存储要求给在 NFA 中的每个状态最多一位).
保持机器当前可能处在的所有状态的集合数据结构. 在消耗最后一个输入符号的时候, 如果这些状态之一是最终状态, 则机器接受这个字符串. 在最坏的情况下, 这要求辅助空间正比于在 NFA 中状态的数目; 如果集合结构为每个 NFA 状态使用一位, 则这个方式等价于前者.
创建多个复件. 对于每个 n 路决定, NFA 创建这个机器的直到{\displaystyle n-1}n-1 个复件. 每个都进入单独的状态. 如果在耗尽最后的输入符号的时候, 至少一个 NFA 复件处在接受状态, 则 NFA 就接受它.(这也要求关于 NFA 状态数目的线性存储, 因为对所有 NFA 状态都可能有一个机器).
通过 NFA 的转移结构明确的传播 (propagate) 记号 (token) 并在一个记号到达最终状态的时候匹配. 这在 NFA 应当编码触发转移的事件的额外上下文的时候是有用的.

NFA-ε 的应用

NFA 和 DFA 是等价的, 如果一个语言可被一个 NFA 识别, 则它也可以被一个 DFA 识别, 反之亦然. 这种等价性的创建是重要和有用的. 有用是因为构造识别给定语言的 NFA 有时比构造这个语言的 DFA 要容易很多. 重要是因为 NFA 可以用来减少创建计算理论中很多重要性质的数学工作的复杂性. 例如, 使用 NFA 比使用 DFA 证明下列性质要更加容易: