编译原理 - 词法分析

词法分析

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

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

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

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()

上述伪代码中的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