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} \mid \_)(\mathrm{letter} \mid \mathrm{digit} \mid \_ )*\]

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

token 识别

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

  1. 写出各个 token 类的正则表达式 \(R_i\)，同时记一个正则表达式 \(R\) 为所有 \(R_i\) 的并，即： \[R = R_1 \mid R_2 \mid \cdots \mid R_m\]
  2. 设输入为 \(x_1 \cdots x_n\)，对所有 \(i \in [1, n]\)，检查是否有： \[x_1 \cdots x_i \in L(R)\]
  3. 若找到一个 \(i\) 满足上述条件则说明必有至少一个 \(j\in[1,m]\)， \[x_1 \cdots x_i \in L(R_j)\] 将其记录为 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
10
{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;
    }
}

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