Compiler -- Lexer

发表于 | 分类于 ，

概述

词法分析读取源代码中的字符，识别其中的子串为不同类型的词素（lexeme），生成其对应的 token 传递给语法解析器。

通常来讲，除了生成 token，词法分析器还会清除空白、注释，发现非法字符，生成符号表记录标识符，记录行号以便生成报错信息等。

Lexeme, Token & Token class

一个 token 通常包括两个部分：该 token 所属的 token 类（token class）以及该 token 代表的子串，也即词素（lexeme）。例如<Identifier, a>，<keyword, if>等。

一个 token 类表示了一个字符串集合，这些字符串通常具有相近的含义。例如标识符，某个关键字，字面常量等。词素 则表示了能被识别为某个 token 类的字符串。

为了识别与分类词素，需要一些方法来定义 token 类的识别模式（pattern）。常用的方法是使用正则语言（Regular Language）。

正则语言与正则表达式

数学上定义的“语言”（language）由两个集合所组成：字符集（alphabet）与定义在该字符集上的字符串（string）集。

其中字符集为一个包含若干符号的有限集，一般用希腊字母$\Sigma$表示，常见的例如 ASCII 字符集和 Unicode 字符集；字符串为一个由字符集$\Sigma$中的符号组成的有限序列；而语言中的字符串集可以是任意的由若干定义在$\Sigma$上的字符串组成的可数集。

从该定义中可以看出，每个 token 类都可以视作一个语言。

对于定义在相同字符集的两个语言$L$, $M$，有如下运算：

  • 并（union）：$L \cup M = \{s \mid s \in L \lor s \in M\}$
  • 连接（concatenation）：$LM = \{st \mid s \in L \land t \in M\}$
  • 克林闭包（Kleene closure）：$L* = \bigcup_{i=0}^{\infty} L^i$

其中$L^i$意为语言$L$自身连接$i$次，$i=0$时即为仅包含空串的语言，记为$\{\epsilon\}$；对应地，空字符串记为$\epsilon$。

定义在$\Sigma$上的正则语言可如下定义：

  • 仅包含空串$\{\epsilon\}$和仅包含单个字符$\{c\}(c\in \Sigma)$的语言为正则语言；
  • 若$L$为正则语言，则其克林闭包$L*$为正则语言；
  • 若$L, M$均为正则语言，则其并$L \cup M$与连接$LM$为正则语言。

可以通过定义如下的记号代表一个正则语言，即正则表达式（REGular EXpression, abbr. regex）：

  • 空串$\epsilon$代表的语言$L(\epsilon) = \{\epsilon\}$；
  • 字符$\mathbf{a}(a\in \Sigma)$代表的语言$L(\mathbf{a}) = \{a\}$；
  • $(r)|(s)$代表并$L(r) \cup L(s)$；
  • $(r)(s)$代表连接$L(r)L(s)$；
  • $(r)\ast$代表克林闭包$(L(r))\ast$；
  • $(r)$代表语言$L(r)$，该规则表示在表达式左右添加括号不改变其含义。

同时为了消除括号，通常各运算有如下优先级与结合性：

  1. 一元运算$\ast$优先级最高，左结合；
  2. 连接运算优先级次高，左结合；
  3. 并运算优先级最低，左结合。

通常来讲编程语言中的 token 类都是正则语言。例如，对于 C 语言中的标识符，可以用正则表达式表达为（不考虑保留字）：

其中$\mathrm{letter}$表示英文字母，$\mathrm{digit}$表示数字。

token 识别

定义了正则语言与正则表达式后，token 的识别过程可以表述为如下的步骤：

  1. 写出各个 token 类的正则表达式$R_i$，同时记一个正则表达式$R$为所有$R_i$的并，即：
  2. 设输入为$x_1 \cdots x_n$，对所有$i \in [1, n]$，检查是否有：
  3. 若找到一个$i$满足上述条件则说明必有至少一个$j\in[1,m]$，将其记录为 token，对应$R_j$的 token 类；
  4. 将$x_1 \cdots x_i$移除输入，返回步骤2继续寻找，直至输入为空。

对于冲突，有如下策略：

  • 对于不同长度的满足步骤 2 中条件的前缀，选择最长的前缀，例如将 == 视为一个 token 而不是两个=；
  • 对于不同的，满足步骤 3 中条件的$R_j$，选择最小的$j$，也即将排列顺序视为优先级，例如将某些词素视为关键字而非标识符；
  • 设置错误类以避免失配的情况，如非法字符，非法标识符等。

识别算法的实现通常使用有限状态机（Finite Automaton）。

有限状态机

有限状态机包含了以下部分：

  • 一个输入字符集$\Sigma$；
  • 一个状态有限集$S$；
  • 一个初始状态$s_0 \in S$；
  • 一个接受状态集$F \subseteq S$；
  • 一个转移集合$S \to^a S$，其中$a \in \Sigma \cup \{\epsilon\}$

有限状态机可以表示为一个有向图，其中的结点即为状态，边即为转移，边上有标号$a$。

有限状态机可分为非确定性有限状态机（Nondeterministic ~, abbr. NFA）与确定性有限状态机（Deterministic ~, abbr. DFA）。其中 DFA 除了上述部分外，还有以下约束：

  • 对于每个状态$s \in S$与每个字符$a \in \Sigma$，至多有一个转移；
  • 空串$\epsilon$不允许出现在标号上。

每个有限状态机都对应一个正则语言或空语言（即字符串集合为空集），使用有限状态机可以识别某个字符串是否属于对应的正则语言，方法如下：

  1. 从初始状态开始进行转移；
  2. 除了空串外，若要进行标号为$a$的转移，从字符串中“消耗”一个字符$a$，并转移到另一个状态，标号为$\epsilon$的转移不“消耗”字符直接转移；
  3. 若字符串“消耗”完毕后可到达接受状态$f \in F$，则称状态机接受该字符串，该字符串属于对应的正则语言；
  4. 若字符串“消耗”完毕后无法到达接受状态或无法进行任何转移，则称状态机拒绝该字符串，该字符串不属于对应的正则语言。

通过将某些状态的集合看作一种状态，可以将 NFA 转化为 DFA 。至于如何通过正则表达式生成有限状态机以及如何将 NFA 转化为 DFA 前面的博文已经提过了，这里不再赘述。

Lab

作业二中需要使用 flex 生成 COOL 语言的 Lexer。首先需要定义各个 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
CLASS       (class)
ELSE        (else)
FI          (fi)
IF          (if)
IN          (in)
INHERITS    (inherits)
LET         (let)
LOOP        (loop)
POOL        (pool)
THEN        (then)
WHILE       (while)
CASE        (case)
ESAC        (esac)
OF          (of)
DARROW      =>
NEW         (new)
ISVOID      (isvoid)
ASSIGN      <-	
NOT         (not)
LE          <=

TRUE        t(rue)
FALSE       f(alse)

OBJID       [a-z][_0-9a-zA-Z]*  // 对象标识符
TYPID       [A-Z][_0-9a-zA-Z]*  // 类型标识符

ILCMT       --.*    // inline comment
CMTST       "(*"
CMTED       "*)"
INT         [0-9]+  // 整型字面量

SGN         [\(\)\{\};:,\.<=\+\-\*/~@]  // 单字符 token
SKIP_SGN    [ \t\f\r\v]     // 空白字符

按照作业要求各关键字是大小写不敏感的，新版的 flex 可以使用 (?:) 组来进行大小写不敏感匹配，但我这里用的是老版本的所以没有使用。

然后是生成 token。先写出关键字的 token 生成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{CLASS} { return (CLASS); }
{ELSE}  { return (ELSE); }
{FI}    { return (FI); }
{IF}    { return (IF); }
{IN}    { return (IN); }
{INHERITS}  { return (INHERITS); }
{LET}   { return (LET); }
{LOOP}  { return (LOOP); }
{POOL}  { return (POOL); }
{THEN}  { return (THEN); }
{WHILE} { return (WHILE); }
{CASE}  { return (CASE); }
{ESAC}  { return (ESAC); }
{OF}    { return (OF); }
{DARROW}    { return (DARROW); }
{NEW}       { return (NEW); }
{ISVOID}    { return (ISVOID); }
{ASSIGN}    { return (ASSIGN); }
{NOT}   { return (NOT); }
{LE}    { return (LE); }

然后是单字符 token：

1
2
3
4
5
6
7
8
9
{SGN} {
    return yytext[0];
}
{SKIP_SGN} {}
\n { ++curr_lineno; }
. {
    cool_yylval.error_msg = yytext;
    return (ERROR);
}

需要注意的是这几项需要写在最后，.是用来兜底代表非法字符的；并且换行符需要单独处理，因为需要保存行号。

接下来是字面量和标识符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{TRUE} {
    cool_yylval.boolean = true;
    return (BOOL_CONST);
}
{FALSE} {
    cool_yylval.boolean = false;
    return (BOOL_CONST);
}

{OBJID} {
    cool_yylval.symbol = idtable.add_string(yytext);
    return (OBJECTID);
}
{TYPID} {
    cool_yylval.symbol = idtable.add_string(yytext);
    return (TYPEID);
}
{INT} {
    cool_yylval.symbol = inttable.add_string(yytext);
    return (INT_CONST);
}

这几项需要写在关键字后面，因为关键字不应该被识别为标识符。

再然后是注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{ILCMT} {}

{CMTST} { BEGIN(COMMENT); }
<COMMENT>\n { ++curr_lineno; }
<COMMENT>{CMTED} { BEGIN(INITIAL); }
<COMMENT>. {}

<COMMENT><<EOF>> {
    BEGIN(INITIAL);
    cool_yylval.error_msg = "EOF in comment";
    return (ERROR);
}
{CMTED} {
    cool_yylval.error_msg = "Unmatched *)";
    return (ERROR);
}

行内注释比较简单，关键是多行注释，由于多行注释内的语法与注释外不一样，所以使用到了状态 State。

状态需要先定义，在定义段中使用%x COMMENT可以定义COMMENT状态，使用BEGIN(COMMENT)可以切换到该状态，使用BEGIN(INITIAL)切换回初始状态，在正则表达式前加上<COMMENT>可以指定在某状态内的匹配操作。

最后是字符串，和注释一样使用到了状态：

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
51
52
53
54
55
56
57
58
59
\" {
    BEGIN(STRING);
    string_buf_ptr = string_buf;
}
<STRING>\\[^ntbf] {
    push_char_safe(yytext[1]);
}

<STRING>\\n {
    push_char_safe('\n');
}
<STRING>\\t {
    push_char_safe('\t');
}
<STRING>\\b  {
    push_char_safe('\b');
}
<STRING>\\f {
    push_char_safe('\f');
}

<STRING>\\\n {
    push_char_safe('\n');
    ++curr_lineno;
}

<STRING>\" {
    BEGIN(INITIAL);
    int len = string_buf_ptr - string_buf;
    string_buf_ptr = string_buf;
    if(is_strlen_exceed) {
    cool_yylval.error_msg = "String constant too long";
    is_strlen_exceed = false;
    return (ERROR);
    } else {
    cool_yylval.symbol = stringtable.add_string(string_buf, len);
        return (STR_CONST);
    }
}
<STRING>\n {
    BEGIN(INITIAL);
    is_strlen_exceed = false;
    string_buf_ptr = string_buf;
    cool_yylval.error_msg = "Unterminated string constant";
    ++curr_lineno;
    return (ERROR);
}
<STRING><<EOF>> {
    BEGIN(INITIAL);
    cool_yylval.error_msg = "EOF in string constant";
    return (ERROR);
}
<STRING>\0 {
    cool_yylval.error_msg = "String contains null character";
    return (ERROR);
}
<STRING>. {
    push_char_safe(yytext[0]);
}

和注释一样需要在定义段中加上%x STRING定义状态。同时这里使用了一个自定义的函数push_char_safe：

1
2
3
4
5
6
7
8
9
char *string_buf_ptr;
Boolean is_strlen_exceed;
void push_char_safe(char c) {
    if(string_buf_ptr - string_buf < MAX_STR_CONST) {
        *(string_buf_ptr++) = c;
    } else {
        is_strlen_exceed = true;
    }
}

该函数需定义在定义段的代码块中。