02_词法分析

• 词法分析器
  • 输入：程序文本/字符串 s + 词法单元 (token) 的规约
  • 输出：词法单元流

分类:

• 词法分析器生成器（最简单）
• 手写词法分析器
  • 生产环境下编译器常用（如gcc）
• 自动化词法分析器(最难)

1. 词法分析器生成器ANTLR

• 输入：词法单元（token）的规约
• 输出：词法分析器
• 如何形式化规约？
  • 正则表达式

有空看看这个C.g4
不知道词法单元怎么描述？

1.1. ANTLR语法

• 发音|ant-lər|

• 小写字母开头：文法

• 大写字母开头：语法

• 优先级：

  • 若某字符串满足多个规则，会优先满足前一个规则。特例放在前面
  • 约定：字面量的token优先级高于符号量

• 词法单元

  • 关键字
    • 只包含自己，不需要描述
  • 符号量
    • 一类，需要描述

1.1.1. ANTLR v4 中两大冲突解决规则

1. 最前优先匹配: 关键字 vs. 标识符

BEGIN : 'begin' ;
ID : [a-z]+ ;

1. 最长优先匹配: >=, ifhappy, thenext, 1.23

1.2. 命令行使用

• alias:
  • alias grun="java org.antlr.v4.gui.TestRig"用于调试
  • alias antlr4="java -jar /usr/local/lib/antlr-4.9.1-complete.jar"

1. 写一个.g4文件
2. 在文件目录下antlr4 <file>.g4
3. javac *.java
4. grun <file> <rule> [options]
   例子：

grun SimpleExpr r -tokens

1.3. 以编程的方式使用antlr4

以编程方式使用antlr4生成的xxxLexer.java

1. 在g4文件中写package语句
   • 如果词法语法分开，一般写在语法部分

@header{
package simpleexpr
}

=>所有自动生成的文件都放到包里

header中所有的代码都会被拷贝到生产的java文件

1. 写一个测试文件

CharStream input = CharStreams.fromStream(is);
SimpleExprLexer lexer = new SimpleExprLexer(input);//把输入程序以字符串的形式传给词法分析器

lexer.getAllTokens().forEach(System.out::println);//lamda表达式

1.4. 把词法部分和语法部分分开

不同语言语法部分各不相同，词法却很相似

1. 单独写一个g4文件

lexer grammer SimpleExprRules;

1. 语法部分import词法部分即可

[grammer-v4] antlr 官方维护的

1.5. 参考

antlr4权威指南：

• 5.5：识别常见的语法结构
• 15.5：词法规则
• 15.6：通配符与非贪婪子规则
• 12：词法分析器黑魔法（暂时用不到），词法分析高端用法

2. 正则表达式

作用：词法单元的形式化规约 。
正则表达式是语法，正则语言是语义。

2.1. 概念

• id:字母开头的字母/数字串
• 字母表：字母和数字等符号集合
• 串：符号构成的有穷序列，含空串
• 语言：id定义的集合，可数个串的集合
  • 空语言与只含有空串的语言不同
  • 集合运算可以得到新的语言

2.2. 语言运算

可以使用集合运算构造新的语言。

• 串的指数运算
• L M并：
• L M连接：
• Kleene闭包：
• L的正闭包：

允许我们构造无穷的集合

2.3. 正则表达式定义

2.3.1. 语法

给定字母表，上的正则表达式由且仅由以下规则定义:

2.3.2. 语义

正则表达式对应的正则语言：

2.4. 扩展语法

• .*默认贪婪匹配
• .*?非贪婪匹配
• ~[\n]*匹配除了某些字符外的其他字符

.在.g4中可以匹配任意符号，但在一些版本的正则表达式中表示除了换行符之外的任意字符

2.4.1. 特殊匹配

2.4.1.1. 反向引用

<[hH](1-6)>.*?<\/[hH]\1>*

r1/r2

2.4.1.2. 前视断言

(?=<expr>)

(?=…)
当 … 匹配时，匹配成功，但不消耗字符串中的任何字符。这个叫做 前视断言 （lookahead assertion）。

• Isaac (?=Asimov) 将会匹配 'Isaac ' ，仅当其后紧跟 'Asimov' ,但不消耗Asimov
• “Windows(?=95|98|NT|2000)”能匹配“Windows2000”中的“Windows”，但不能匹配“Windows3.1”中的“Windows”
  regex101: build, test, and debug regex

2.4.1.3. 肯定型后视断言

(?<=<expr>)

(?<=…)

如果 ... 的匹配内容出现在当前位置的左侧，则匹配。这叫做 肯定型后视断言 （positive lookbehind assertion）。 (?<=abc)def 将会在 'abcdef' 中找到一个匹配，因为后视会回退3个字符并检查内部表达式是否匹配。内部表达式（匹配的内容）必须是固定长度的，意思就是 abc 或 a|b 是允许的，但是 a* 和 a{3,4} 不可以。注意，以肯定型后视断言开头的正则表达式，匹配项一般不会位于搜索字符串的开头。

• “(?<=95|98|NT|2000)Windows”能匹配“2000Windows”中的“Windows”，但不能匹配“3.1Windows”中的“Windows”
  regex101: build, test, and debug regex
  《正则表达式必知必会》

请使用正则表达式将一段文本中所有连续两次重复出现的单词找出来

1. 使用反向引用：

\b(\w+)\b\s+\b\1\b

这个正则表达式和前面的例子类似，只是使用了反向引用来引用第一组捕获到的内容，也就是前面匹配到的单词。这里使用\1来引用第一组捕获到的内容。

1. 使用正向前视断言：

\b(\w+)\b(?=\s+\1\b)

这个正则表达式使用了正向前视断言(?=\s+\1\b)来匹配单词，该断言表示单词后面紧跟着一个或多个空白字符和前面匹配到的单词。这里不需要捕获第一组内容。

1. 使用负向前视断言：

\b(\w+)\b(?!\W)\s+\b\1\b(?!\w)

2.4.2. vim简记法

3. 手写一个词法分析器

lookahead

• 过程
  • 向前看
  • 向前走
  • 调整状态
  • 记录关键点
  • 待机回头

本质：不断的识别字符串

要记录最后一次合理的peek,方便回退
状态转移时要携带信息从那个状态来的

4. 自动机理论与词法分析器生成器

根据表达/计算能力的强弱, 自动机可以分为不同层次

正则表达式、NFA、DFA表达能力等价 ：

除了Kleene都是Turing奖得主，但他导师是church

4.1. NFA

• NFA (Nondeteministic Finite Automaton)
• 非确定性有穷自动机

4.1.1. 定义

非确定性有穷自动机 A 是一个五元组 A = (Σ, S, s0, δ, F):

1. 字母表（）

2. 有穷的状态集合

3. 唯一的初始状态

4. 状态转移函数
   $$
   \delta : S\times (\Sigma \cup {\epsilon}\rightarrow 2^S)

   $$

5. 状态接受函数集合

• 约定: 所有没有对应出边的字符默认指向一个不存在的 “空状态”

  • 下图1的a指向空状态

• 非确定性体现：

  • 状态转移有种可能
  • 没有字符输入即，也可以自发跑到其他状态

4.1.2. 语言

• 接受（Accept）
  • （非确定性）有穷自动机接受字符串，当且仅当存在一条从开始状态到某个接受状态、标号为的路径
  • 给定一个字符串输入，如果最后字符串耗尽时的可能状态集合（因为是不确定状态机）包含接受状态，则接受
• **语言**：
  • 能接受的所有字符串构成的集合
  • 语义是否包含决定了自动机的强弱

4.1.3. 自动机的两个基本问题

• Membership 问题: 给定字符串？
• 究竟是什么？->用RE表示

4.1.4. 例子

4.2. DFA

• DFA (Deterministic Finite Automaton)
• 确定性有穷自动机,下一个状态唯一

4.2.1. 定义

• 五元组：

1. 字母表

2. 有穷的状态集合

3. 唯一的初始状态

4. 状态转移函数

   $$
   \delta:S\times \Sigma \rightarrow S

   $$

5. 接受状态集合

约定: 所有没有对应出边的字符默认指向一个 “死状态 ”

4.2.2. 无关状态

• 死状态：从这个状态没有通路到达结束状态
• 多余状态：从开始状态出发，任何输入串也不能到达的那个状态。

4.2.3. NFA与DFA比较

NFA更加易于理解 ，便于描述L(A)
DFA易于判断，适合产生词法分析器

用 NFA 描述语言, 用 DFA 实现词法分析器

4.3. Thompson 构造法👍

从RE到NFA

• 基本思想: 按结构归纳

4.3.1. 构造过程

[[#2.3. 正则表达式定义]]

1. 是正则表达式
   

2. 是正则表达式
   

3. 如果 s 是正则表达式, 则是正则表达式。N((s))=N(s)

4. 如果 s, t 是正则表达式, 则是正则表达式

   • 根据归纳假设, N(s) 与 N(t) 的开始状态与接受状态均唯一->一边构造一边证明

   

5. 如果 s, t 是正则表达式, 则是正则表达式。

   • 根据归纳假设, N(s) 与 N(t) 的开始状态与接受状态均唯一
   • 拼接时,s终止与t初始看成一个状态

   

6. 如果 s 是正则表达式, 则是正则表达式。

   • 根据归纳假设, N(s) 的开始状态与接受状态唯一。

4.3.2. 正则表达式定义

给定字母表，上的正则表达式由且仅由以下规则定义:

1. 是正则表达式
2. ,是正则表达式
3. 如果是正则表达式，则也是正则表达式
4. 如果与是正则表达式，则也是正则表达式

4.3.3. N(r)性质和Thompson构造法复杂度分析

1. N(r)的开始状态与接受状态均唯一。
2. 开始状态没有入边, 接受状态没有出边。
3. N(r) 的状态数。 (：中运算符与运算分量的总和)
   • 每次构造最多加一个起点,一个终点
4. 每个状态最多有两个入边与两个出边。
5. , 每个状态最多有一个入边与一个出边。

4.3.4. 考试题型

给状态图，写出正则表达式。

4.4. 子集构造法👍

• Subset/Powerset Construction
• NFA到DFA的转换，用DFA模拟NFA

最差情况可能是指数级，但实际很少

4.4.1. 例子

NFA状态的子集包含结束状态则它就是DFA的结束状态。
初始状态集合为从开始，通过转移可以到达的状态。

4.4.2. 原理

• 闭包
  
• 子集构造法原理:
  

4.4.3. 闭包

• ：

  • 在初始集合上做
  • 由决定做什么

• 更形象的理解：每一次运算都会使得新的集合变大，直到找到不动点。

思考：把世界地图扔到地上，一定会存在一个现实中的点与地图上的位置重合？

4.5. DFA最小化算法👍

• 基本思想：等价的状态集合可以合并

• 正向：

  • 不断合并等价的状态，知道无法合并为止
  • 但这是一个递归定义，最初的等价关系从哪里来？

• 反向：
  • 划分等价集合，直到无法再继续划分（划分而非合并）
  • 天然就有初始划分：接受状态与非接受状态必定不等价，空串区分两种状态

初始划分：,区分两种状态。

通过符号

4.5.1. 算法

要先检查是否需要补 “死状态” (不补充可能有问题)

• 合并后一定还是DFA吗？
  • 一定是的。合并后节点在某个字符驱动下指向的状态也等价，若有多个状态也会合并。

4.5.2. 例子

4.6. DFA词法分析器

4.6.1. 匹配原则

• 最前优先匹配：关键字
• 最长优先匹配

4.6.2. 例子

• 有3个RE
  a
  abb
  a*b+

• 根据正则表达式构造相应的 NFA
  

• 合并这三个 NFA, 构造 a|abb|a *b+ 对应的 NFA

• 子集构造法将 NFA 转化为等价的 DFA (并消除 “死状态”)
  • 要保留各个 NFA 的接受状态信息, 并采用最前优先匹配原则
  • 需要消除 “死状态”, 避免词法分析器徒劳消耗输入流
    • 如果不消除，会耗尽输入流所有字符才发现错误。此时在回退到没有出错的状态代价很大。

• 模拟运行该 DFA, 直到无法继续为止 (输入结束或状态无转移); 假设此时状态为 s
  • 若 s 为接受状态, 则识别成功;
  • 否则, 回溯 (包括状态与输入流) 至最近一次经过的接受状态, 识别成功;
    • 若没有经过任何接受状态, 则报错 (忽略第一个字符)
• 无论成功还是失败, 都从初始状态开始继续识别下一个词法单元

• 特定于词法分析器的 DFA 最小化方法
  • 初始划分需要考虑不同词法单元（接受状态），比传统的划分更精细

4.7. kleene构造法