跟我一起自己写编译器-4.词法分析

发表于 更新于 分类于 阅读次数： 本文字数： 6.2k 阅读时长 ≈ 6 分钟

5. 词法分析

词法分析，如其名，只分析词语，即token，词是一个文法的最小单元。至于什么是文法，后面会介绍，这里不需要过多忧虑。

5.1. 举个例子

比如我们有一个代码,这个代码和c/c++很相似（但是这个是pava代码，读者目前可以理解为c代码），这是一个计算斐波那契数列的代码，他的词法分析结果是什么呢？

1
2
3
4
5
6
7
8
int fib(int x){
    if(x<2) return 1;
    return fib(x-1) + fib(x-2);
}
int main(){
    int a = fib(5);
    return a;
}

下文的代码就是词法分析结果, 词法分析器从源文件依次读取，然后分割出最小的词法单元，

最开始词法分析器读到了字符i，然后读到了字符n，然后读到了字符t,紧接着读到了空格字符，这时候词法分析器发力，进行分割，将前三个字符int划为最小词法单元符号。

紧接着继续读取f,当他读入f这个字符的时候，词法分析器发力，将第四个字符(空格字符)划为词法单元empty,当然在下文中无法找到emtpy这个token，因为empty代表空字符，可有可无。

然后词法分析器继续分析，不断地解析，一直解析出fib(符号)， ((左括号)， int(符号),x(符号),)(右括号)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
"int"(symbol)
"fib"(symbol)
"("(leftBracket)
"int"(symbol)
"x"(symbol)
")"(rightBracket)
"{"(leftCurlyBracket)
"if"(if)
"("(leftBracket)
"x"(symbol)
"<"(lt)
"2"(number)
")"(rightBracket)
"return"(return)
"1"(number)
";"(semicolon)
"return"(return)
"fib"(symbol)
"("(leftBracket)
"x"(symbol)
"-"(sub)
"1"(number)
")"(rightBracket)
"+"(add)
"fib"(symbol)
"("(leftBracket)
"x"(symbol)
"-"(sub)
"2"(number)
")"(rightBracket)
";"(semicolon)
"}"(rightCurlyBracket)
"int"(symbol)
"main"(symbol)
"("(leftBracket)
")"(rightBracket)
"{"(leftCurlyBracket)
"int"(symbol)
"a"(symbol)
"="(eq)
"fib"(symbol)
"("(leftBracket)
"5"(number)
")"(rightBracket)
";"(semicolon)
"return"(return)
"a"(symbol)
";"(semicolon)
"}"(rightCurlyBracket)
"$END"($END)

5.2. 识别词法单元

编译器的第一步就是词法分析，他需要从待分析的文本中，逐字符读取，并分割词法单元。一种高效而有简单的方式就是使用正则表达式构建NFA模型，然后优化为DFA，此后对文本进行分割。

这里可能有一些抽象，突然来了这么多概念，下面一个一个来解释。

5.3. 确定有限状态自动机

确定有限状态自动机 被称为DFA

确定有限状态自动机\({\displaystyle {\mathcal {A}}}\)是由

  • 一个非空有限的状态集合\({\displaystyle Q}\)
  • 一个输入字母表\({\displaystyle \Sigma }\)（非空有限的字符集合)
  • 一个转移函数\({\displaystyle \delta :Q\times \Sigma \rightarrow Q}\)（例如：\({\displaystyle \delta \left(q,\sigma \right)=p,\left(p,q\in Q,\sigma \in \Sigma \right)}\))
  • 一个开始状态\({\displaystyle s\in Q}\)
  • 一个接受状态的集合\({\displaystyle F\subseteq Q}\)

所组成的5-元组。因此一个DFA可以写成这样的形式：\({\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)}\)。

5.4. 非确定有限状态自动机

非确定有限状态自动机又被称为NFA，与DFA不同的是他的转移是不确定的，他的转移不唯一。

4.5. 正则表达式识别原理

4.5.1. 正则例1

首先给出一个正则表达式a， 这个正则表达式能识别，且仅能识别字符串a，那么如何来表示呢?下图是这个正则表达式所对应的nfa，最开始我们在状态start， 当我们读取字符a以后，会转移到end，当我们到达end的时候如果输入结束，自动机就输出匹配成功。所以该自动机能使被字符串a，如果输入为b， 自动机在start时，会因为没有b这个转移而直接输出匹配失败，如果输入为ab自动机会因为在end处无法找到转移b而输出匹配失败.

graph LR
    start[start起点] -->|a| ed(end终结)

4.5.2. 正则例2

考虑串联，来正则表达式ab， 这里如何构建呢，首先我们分别构建两个自动机。

graph LR
    start1[start1起点] -->|a| ed1(end1终结)
    start2[start2起点] -->|b| ed2(end2终结)

然后将他们组装在一起， 注意到这里出现了一个空，这就意味着，当我们处于状态end1的时候可以不输入任何字符，直接转移到状态start2 ，于是这个自动机最开始在start1 处，当他输入字符a，他会转移到end1 以及start2，当继续输入字符b，会转移到end2（end1无法转移,start2可转移）

graph LR
    start1[start1起点] -->|a| ed1(end1)
    ed1 -->|空| start2
    start2[start2] -->|b| ed2(end2终结)

4.5.3. 正则例3

考虑并联,来正则表达式a|b， 这里如何构建? 依然构建两个自动机

graph LR
    start1[start1起点] -->|a| ed1(end1终结)
    start2[start2起点] -->|b| ed2(end2终结)

然后串联， 这里不用再解释了

graph LR
    start1[start1] -->|a| ed1(end1)
    start2[start2] -->|b| ed2(end2)
    start[start起点] -->|空| start1 & start2
      ed1 & ed2 -->|空| ed[end终结]

4.5.4. 正则例4

考虑自循环， 来正则表达式a+, 加号表示出现最少一次,可以为多次, 只需要引一条从end到start的边即可

graph LR
     start[start起点] -->|a| ed(end终结)
      ed -->|空| start

至此我们已经分析完了所有的正则单元，复杂的正则表达式均可由此合并而成。

4.6. NFA转DFA

nfa转dfa算法涉及到一个闭包，我们直接对这个nfa来计算闭包

graph LR
     start[start起点] -->|a| ed(end终结)
      ed -->|空| start

最开始位于状态start， 当输入a以后，进入状态end， 计算end的空闭包[start,end]，当从状态[start,end]输入a以后，进入状态end，也就是[start,end], 于是最终我们得到了这个dfa

graph LR
    start[start] -->|a| ed([start,end])
      ed -->|a| ed

4.7. DFA识别

如何为一门语言设计他的dfa呢？实际上一门语言涉及到多个token，每个token都会由一个正则，那么就会出现正则冲突，即一个字符串可以被识别为多种token，这时候就定义优先级即可。

另一种情况，即是否贪婪，如果一个字符串的前缀可以被识别为一个token，即字符串ifhaha的前缀if可以被识别为tokenif ,而他自身可以被识别为tokensymbol，这时候，我们需要选择最长的那个，即最长匹配即可。

4.8. 效果展示

笔者的项目中又涉及到一款c类语言(pava语言)的token配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
{
    "tokens": [
        {"number": "0|[123456789]\\d*"},
        {"doubleQuotes": "\""},
        {"blank": "\\s+"},
        {"leftCurlyBracket": "\\{"},
        {"rightCurlyBracket": "\\}"},
        {"string": "\"[\\s\\w\\d]*\""},
        {"include": "#include"},
        {"while": "while"},
        {"if": "if"},
        {"for": "for"},
        {"return": "return"},
        {"break": "break"},
        {"continue": "continue"},
        {"do": "do"},
        {"goto": "goto"},
        {"else": "else"},
        {"comma": ","},
        {"leftBracket": "\\("},
        {"rightBracket": "\\)"},
        {"add": "\\+"},
        {"sub": "\\-"},
        {"mul": "\\*"},
        {"div": "/"},
        {"mod": "%"},
        {"doubleEq": "=="},
        {"eq": "="},
        {"ne": "!="},
        {"leftShift": "<<"},
        {"rightShift": ">>"},
        {"be": ">="},
        {"le": "<="},
        {"bt": ">"},
        {"lt": "<"},
        {"semicolon": ";"},
        {"symbol": "[_\\w][_\\w\\d]*"}
      ]
}

该配置在经过自动构建工具compiler/Reg.java at master · fightinggg/compiler · GitHub构建以后得到了下图的nfa, 如果此图太小，读者可以右键点击到新页面查看，此处不对此工具进行解释，因为它涉及到更深层次的内容，笔者将在后面的章节中予适当的时候对此工具进行描述，另一方面由于此dfa也不是很大，人工绘制也不是不可能，综上此处不做解析了。