词法剖析

编译器的履行流程

编译器履行能够分为8个阶段：词法剖析、语法剖析、语意剖析、中间代码生成、指令挑选、代码优化、寄存器分配、代码生成。其间前4个阶段构成编译器的前端frontend，剩余阶段组成了编译器的后端backend。如下图所示：

编译器的前端与机器无关，后端履行的结果是特定系统架构下的汇编代码。为了生成可履行程序，汇编代码还要经过汇编器、链接器。整个程序的履行能够用下面这张图来阐明：

词法剖析的效果

词法剖析和NLP里的命名实体识别技能类似，都是把输入字符映射到有意义的代表物(Token)上，和人类言语比较，编程言语的规矩语法过于简略，所以咱们用基于规矩的字符匹配算法就能够搞定这一步，并不需要模型算法技能。当然，在词法剖析中，咱们还能够滤除冗余信息(空格，换行符等)，所以词法剖析能够看作是从原始信息中提取关键信息的一步。关于source code中的词法结构，咱们应该如何描绘呢？正则表达式是一种东西，有描绘东西之后就需要实现它，对应的实现东西便是有限自动机(finite automata)。

有限自动机

界说

有限自动机是一个五元组 $(S,,,s0,SA)(S,\Sigma,\delta,s_0,S_A)$ :

$S$ 是一个有限状况调集，包括一个错误状况 $s_e$
$\Sigma$ 是一个有限字母调集
$(s,c)\delta(s,c)$ 叫做搬运函数，关于 $∀s∈S∨∀c∈,(s,c)∈S\forall s\in S \vee \forall c \in \Sigma ,\delta(s,c) \in S$ ，状况搬运能够写为 $si→c(si,c)s_i\stackrel{c}{\rightarrow}\delta(s_i,c)$
$s0∈Ss_0\in S$ 叫做开始状况
$SA⊆SS_A \subseteq S$ 是承受状况的调集

有限自动机也能够用图来表明，假定咱们要识别new,not,while这三个关键词，程序伪代码如下：

c = NextChar()
if (c == 'n'):
    c = NextChar()
    if(c == 'e')
        c = NextChar()
        if(c=='t'):
            return 'accept state'
	else if (c == 'o'):
        c = NextChar()
        if (c == 't'):
            return 'accept state'
else if(c=='w'):
    c = NextChar()
    if(c == 'h'):
        c = NextChar()
        if(c =='i'):
            c = NextChar()
            if(c=='l'):
                c = NextChar()
                if(c=='e'):
                    return 'accept state'
return 'unaccept state'

用状况图表明：

咱们说状况机 $FA(S,,,s0,SA)FA(S,\Sigma,\delta,s_0,S_A)$ 承受字符串 $x$ 当且仅当如下条件成立:

((…(((s0,x1),x2),x3)…,xn−1),xn)∈SA\delta(\delta(…\delta(\delta(\delta(s_0,x_1),x_2),x_3)…,x_{n-1}),x_n)\in S_A

有没有一种等价的方式来描绘上述的状况图呢？答案是有！正则表达式regular expression

正则表达式

界说

正则表达式在给定字母表上描绘了字符调集，包括空字符。这样的字符调集称之为language。关于给定的正则表达式r，language表明为L(r).正则表达式界说了三种运算：

Union， $R∣S:={x∣x∈Rorx∈S}R|S:=\{x|x\in R \text{ or } x\in S\}$
Concatenation, $RS:={xy∣x∈Randy∈S}RS:=\{xy|x\in R\text{ and } y\in S\}$
Closure, $R∗:=⋃i=0∞RiR^*:=\bigcup_{i=0}^{\infty}R^i$

特别地， $R+:=⋃i=1∞Ri=RR∗R^+:=\bigcup_{i=1}^{\infty}R^i=RR^*$ ,[0…9]=(0|1|2|3|4|5|6|7|8|9)

例子

标识符identifier： $a…z]|[A…z])([a…z]|[A…Z]|[0…9])^*$
非负整数： $0|[1…9][0…9]^*$ or $0…9]^+$
非负实数： $[0…9]+(∣.[0…9]∗)E(∣+∣−)(0…9)+[0…9]^{+}(\epsilon|.[0…9]^*)E(\epsilon|+|-)(0…9)^+$
字符串：“ $($ ^ $($ “|\ $n)$ $)∗)^*$ ”
单行注释：\\(^\n)\n
多行注释:\*(^*)**/

确认性有限自动机DFA

关于恣意输入字母c, $(s,c)\delta(s,c)$ 的输出是唯一确认的

非确认性有限自动机NFA

关于恣意输入字母c, $(s,c)\delta(s,c)$ 的输出能够有多个，而且包括空跳(不消费字母即可进行状况跳转) $(s,)\delta(s,\epsilon)$

DFA与NFA的等价性

关于有N个状况的NFA，咱们总能够用至多 $2^N$ 个状况节点构建DFA；关于DFA，本身便是NFA的一种特例，所以二者等价。

正则表达式到NFA

Thompson Construction

因为正则表达式在前面界说的三种运算上是关闭的，所以咱们能够界说NFA的这三种等价运算:

$ab$

$a ∣ b$

$a^*$

例子 $a(b|c)^*$

构建单独的DFA

构建 $b ∣ c$

构建 $b|c)^*$

构建 $a(b|c)^*$

DFA的等价表明

对比DFA和NFA咱们能够发现：NFA包括很多冗余的状况节点及状况搬运，因此使用NFA构建DFA是必要的。

NFA到DFA

Subset Construction算法

变量解释：

$−closure(sa)\epsilon-closure(s_a)$ :当前状况的所有空跳后继状况调集
$n_0$ :start state
$q$ :迭代状况变量
$Q$ :DFA state set

算法描绘

算法剖析：

关于NFA的N个状况，路径排列是 $2^N$ ,在while循环中注意到，Q是单调递增的，且worklist中t一定是不同的(相同地不会加入Q和worklist)，当Q中元素数量到达最大时，add操作不会履行，所以算法一定会终止，不会堕入死循环。

编译器理论篇 (一) 词法分析