词法分析

编译器的前端可以分成如下过程：

=》前端=》词法分析器=》记号=》语法分析器=》抽象语法树=》语义分析器=》中间表示=》

词法分析的任务是将程序员所写的程序切分成记号流。

if (x > 5)
  y = "hello";
else
  z = 1;

经过词法分析器分析之后，会被字符切分为如下内容

IF LPAREN IDENT(x) GT INT(5) RPAREN
  IDENT(y) ASSIGN STRING("hello") SEMICOLON
ELSE
  IDENT(z) ASSIGN INT(1) SEMICOLON EOF

记号

记号的数据结构定义，类似如下代码

enum kind {IF, LPAREM, ID, INTLIT, ...}
struct token
{
    enum kind k;
    char *lexeme;
}

词法分析器的任务：字符流到记号流的转换

• 字符流：和被编译的语言密切相关(Unicode, ASCII)
• 记号流：编译器内部定义的数据结构，编码所识别出的词法单元

词法分析器的实现方法

至少两种的实现方案：

• 手工编码实现法

• 相对复杂，且容易出错
• 但是目前非常流行的实现方法

• GCC，LLVM，…

• 词法分析器的生成器

• 可快速原型，代码量少
• 但是较难控制细节

手工编码实现法

如果我们有<=、<>、<、=、>、>=、>符号，如下图，我们的提取步骤，根据第一个字符，我们可以按照下图步骤读取对应的符号。

其他的标识符转移图和上述的类似。

标识符和关键字

• 很多语言中标识符和关键字是有交集的

• 从词法分析的角度看，关键字是标识符的一部分

• 以C语言为例：

• 标识符：以字母或者下划线开头，后面跟了零个或者多个字母，下划线或者数字
• 关键字：if while else

如何识别关键字

• 在标识符识别的时候，单独加上标识符的识别

• 关键字表算法

对给定语言中的所有的关键字，构造关键字构成的hash表

对所有的标识符和关键字，先统一按照标识符的转移图进行识别

识别完成之后进一步查询hash表看是否有关键字

通过合理的构造hash表，可以在O(1)时间内完成查询

词法分析器的生成器

正则表达式

• 对给定的字符集 A = {c1, c2…cn}

• 归纳定义

空串a是正则表达式

对于任意的c 属于A, c是正则表达式

如果M和N是正则表达式，则一下也是正则表达式

选择 M | N = {M, N}

连接 MN = {mn | m属于M, n属于N}

闭包 M* = {c, M，MM, MMM, … }

如何使用正则表达式？

• 关键字

• C语言中的关键字 if while 如何使用正则表达式表示呢 if

• 表示符

• C语言中的标识符需要以字母或下划线开头，后面跟零个或者多个字母i，数字或者下划线。 如何使用正则表达式表示呢？

正则表达式语法糖

参见正则表达式文章连接：正则表达式-CSDN博客

有限状态自动机(FA)

输入的字符串=》FA=》{YES, NO}

• 确定的有限状态自动机：DFA

• 对任意字符，对多只有一个状态可以转移

• 非确定的有限状态自动机：NFA

• 对任意的字符，有多余一个状态可以转移

DFA的实现

可以看成一个有边和节点的有向图；

• 边上有信息
• 节点上也有信息

正则表达式到非确定有限状态自动机

• Thompson算法：正则表达式=》NFA
  
• 子集构造算法：NFA=>DFA
  
• Hopcroft最小化算法：DFA=>词法分析器代码

Thompson算法

• 基于对RE的构造做归纳

• 对基于的RE直接构造
• 对复合的RE递归构造

• 递归算法，容易实现

子集构造算法

• 不动点算法

• 算法为什么能工运行终止

• 时间复杂度

• 最坏情况O(2^n)
• 但是在实际中不常发生

• 因为并不是每个子集都会出现

• ε-闭包的计算：深度优先或者是广度优先

Hopcroft最小化算法

DFA的代码表示

• 概念上讲，DFA是一个有向图
• 实际上，有不同的DFA的代码表示

• 转移表
• 哈希表
• 跳表等

• 取决于在实际实现中，对时间空间的权衡

转移表

nextToken()
state = 0
stack = []
while (state != ERROR)
  c = getChar()
  if (state is ACCEPT)
    clear(stack)
    push(state)
  state = table[state][c]
  
while (state is not ACCEPT)
  state = pop()
  rollback()
z

上述伪代码中的stack 是为了 最长匹配

跳转表

netxToken()
    state = 0
    stack = []
    goto q0
q0：
    c = getChar()
    if (state is ACCEPT)
        clear(stack)
    push (state)
    if (c == 'a')
        goto q1

q1:
  c = getChar()
    if (state is ACCEPT)
        clear(stack)
    push(state)
    if (c == 'b' || c == 'c')
        goto q1