本项目利用 Flex (fast lexical analyzer generator)，实现了对给定 PCAT 语言样例的词法分析。
Compilers @ Fudan University, fall 2021.
1 Flex 使用方法
一个 Flex 词法分析程序分为三个部分：
- 定义区（definitions）：包含所有 token 和初始状态（start condition）的声明，以及一些 Flex 的设置。
- 规则区（rules）：定义了 Flex 在扫描时匹配到相应 pattern 时需要采取的操作。
- 用户代码区（user code）：（可选）用户可以在这里定义一些 Flex 扫描时需要用到的辅助函数，此部分代码会被直接复制到 Flex 自动生成的 C/C++ 代码里（本项目中为
src/lexer.cpp）。
三个部分之间使用一个单行的 %% 分隔。
1
2
3
4
5
| // Definitions
%%
// Rules
%%
// User code
|
下面我们展开讲讲本项目中这三个部分是如何实现的。
1.1 定义区
1
2
3
4
5
| // src/lexer.lex
%{
#include "lexer.hpp"
%}
|
我们首先 include 了一个 lexer.hpp，其中以枚举的形式定义了所有我们需要用到的 token 类型。这样我们之后就可以在不失可读性的前提下，通过 switch 语句对每个 token 类型分别进行处理。这里被 %{ 和 %} 包围的内容也会被直接复制到 src/lexer.cpp 里。
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
| // src/lexer.hpp
#ifndef SRC_LEXER_HPP_
#define SRC_LEXER_HPP_
enum Tokens {
T_EOF = 0,
T_WS,
T_NEWLINE,
T_INTEGER,
T_REAL,
T_STRING,
T_RESERVED,
T_IDENTIFIER,
T_OPERATOR,
T_DELIMITER,
T_COMMENTS_BEGIN,
T_COMMENTS,
T_COMMENTS_END,
};
enum Errors {
E_UNTERM_STRING = 10000,
E_UNTERM_COMMENTS,
E_UNKNOWN_CHAR,
};
#endif // SRC_LEXER_HPP_
|
随后，我们对 Flex 进行了一些设置。
1
2
3
4
5
| // src/lexer.lex
%option c++
%option noyywrap
%option yylineno
|
这几个设置分别表示：
c++：使用 C++ API。这里主要是因为我个人不太喜欢 C 和 C++ 的语法混用，所以就想着尽可能使用纯 C++ 实现，不使用 C++ API 当然也没有任何问题。noyywrap：在遇到 EOF (end-of-file) 时，不调用函数 yywrap()，而是直接终止程序。这是因为我们这里只打算一次处理一个源文件，所以遇到 EOF 后简单退出就可以了。yylineno：让 Flex 在扫描时自行维护当前所在的行号，保存在变量 yylineno 中（C++ API 下需使用函数 lineno() 读取）。当然我们也可以手动实现，不过既然 Flex 本来就提供了这个接口，那就不重复造轮子了。
然后，我们声明了一个初始状态 COMMENT。
1
2
3
| // src/lexer.lex
%x COMMENT
|
声明这个初始状态的目的将在之后的规则区部分阐述。
最后，我们声明了一些名称（name），用来对一些正则表达式片段以 ${name} 的形式进行复用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| // src/lexer.lex
WS ([ \t]+)
NEWLINE (\r?\n)
DIGIT [0-9]
INTEGER ({DIGIT}+)
REAL ({DIGIT}+"."{DIGIT}*)
LETTER [A-Za-z]
STRING (\"[^\n"]*\")
UNTERM_STRING (\"[^\n"]*)
RESERVED (AND|ARRAY|BEGIN|BY|DIV|DO|ELSE|ELSIF|END|EXIT|FOR|IF|IN|IS|LOOP|MOD|NOT|OF|OR|OUT|PROCEDURE|PROGRAM|READ|RECORD|RETURN|THEN|TO|TYPE|VAR|WHILE|WRITE)
IDENTIFIER ({LETTER}({LETTER}|{DIGIT})*)
OPERATOR (":="|"+"|"-"|"*"|"/"|"<"|"<="|">"|">="|"="|"<>")
DELIMITER (":"|";"|","|"."|"("|")"|"["|"]"|"{"|"}"|"[<"|">]"|"\\")
COMMENTS_BEGIN "(*"
COMMENTS_END "*)"
|
虽说是正则表达式，其实只是 Flex 实现的简化版正则表达式，像贪婪模式 ? 之类的高级标识符都是不支持的。这也导致了我们很难直接通过正则表达式来匹配一个多行注释，关于这点之后我们会展开来讲。
1.1.1 正则表达式原理
下面讲一下上述各个正则表达式的原理。
WS：空白字符。[ \t]+ 表示匹配一个或多个空格或 tab (\t)。
NEWLINE：换行符。\r?\n 表示匹配 LF (\n) 或 CRLF (\r\n) 两种格式的换行符。
DIGIT：数字。[0-9] 表示匹配 $0$ ~ $9$ 中的任一数字。
INTEGER：整数，注意 PCAT 语法下将 INTEGER 规定为不超过 $2^{31}-1$ 的非负整数。{DIGIT}+ 表示匹配一个或多个数字（也就是先前定义的 DIGIT）。由于 INTEGER 一定非负，因此不需要检查开头是否有负号，这里我们将整数是否越界的判断逻辑留到了用户代码部分。
REAL：浮点数（实数），注意 PCAT 语法下将 REAL 规定为没有精度限制的非负实数。{DIGIT}+"."{DIGIT}* 表示匹配一个包含小数点 . 的浮点数，其中小数点前为一个或多个数字，小数点后为零个或多个数字。
LETTER：字母。[A-Za-z] 表示匹配任一大写或小写字母。
STRING：（单行）字符串。\"[^\n"]*\") 表示匹配一个开头和结尾均为双引号 " 的字符串，引号之间包含零个或多个非换行字符 (\n) 的任意字符。
UNTERM_STRING：（单行）未闭合的字符串。实际上就是缺少了右引号的 STRING，用于后续报错功能的实现。
RESERVED：保留字。原表达式表示匹配其中一个关键字。
IDENTIFIER：标识符。{LETTER}({LETTER}|{DIGIT})* 表示匹配一个由字母或数字组成的标识符，其中第一个字符必须是字母。
OPERATOR：运算符。原表达式表示匹配其中一个运算符。
DELIMITER：分隔符。原表达式表示匹配其中一个分隔符。
COMMENTS_BEGIN：（多行）注释开始，即 (*。
COMMENTS_END：（多行）注释结束，即 *)。
1.2 规则区
然后就是 Flex 程序中的关键部分——规则区。这里我们利用先前在 src/lexer.hpp 中定义好的 token 类型，将扫描过程中读取到的 token 进行分类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| // src/lexer.lex
<INITIAL><<EOF>> return T_EOF;
<INITIAL>{WS} return T_WS;
<INITIAL>{NEWLINE} return T_NEWLINE;
<INITIAL>{INTEGER} return T_INTEGER;
<INITIAL>{REAL} return T_REAL;
<INITIAL>{STRING} return T_STRING;
<INITIAL>{UNTERM_STRING} return E_UNTERM_STRING;
<INITIAL>{RESERVED} return T_RESERVED;
<INITIAL>{IDENTIFIER} return T_IDENTIFIER;
<INITIAL>{OPERATOR} return T_OPERATOR;
<INITIAL>{DELIMITER} return T_DELIMITER;
<INITIAL>{COMMENTS_BEGIN} BEGIN(COMMENT); return T_COMMENTS_BEGIN;
<COMMENT>{COMMENTS_END} BEGIN(INITIAL); return T_COMMENTS_END;
<COMMENT>(.|{NEWLINE}) return T_COMMENTS;
<COMMENT><<EOF>> return E_UNTERM_COMMENTS;
<INITIAL>. return E_UNKNOWN_CHAR;
|
这部分中，每一行就代表一个规则。左侧为规则的 pattern，右侧为匹配到此 pattern 时需要采取的操作。
规则中 pattern 的格式为 <起始状态>正则表达式。起始状态部分可以缺省，表示无需考虑状态，始终匹配。这里 <INITIAL> 表示默认的起始状态，<COMMENT> 则为我们之前声明的注释状态。正则表达式部分就用到了我们前面在定义区里定义的名称，这里可以直接使用。
可以看到，当我们匹配到相应的 pattern 时，通常我们会直接 return 一个 token 类型，这就是分类的过程。用户程序中，每次我们调用函数 yylex()，即可从源文件中读入一个单词，并根据这些规则进行匹配，最后得到相应的 token 类型。
这里比较特殊的是对注释的处理。最开始我尝试仅使用正则表达式进行匹配，这个当然可以做，表达式应该是这样："(*"([^*]|(\*[^)]))*"*)"。写成这样是因为 Flex 的正则表达式不支持贪婪模式，因此普通的匹配会直接匹配到程序的第一个 (* 和最后一个 *)，然后中间就全被当成注释了。为了避免这个问题，需要手动设定第一次匹配到 *) 就退出。
但问题出在对未闭合多行注释错误的处理，至少我是没能写出好的正则表达式实现。虽然可以通过测试样例，但对于我自己设计的一些更复杂的样例就不太能很好地匹配了。因此我最终放弃了仅使用正则表达式的方案。
目前的方案是这样：
<INITIAL> 状态下匹配到 (*，就进入 <COMMENT> 状态。<COMMENT> 状态下匹配到 *)，就回到 <INITIAL> 状态。<COMMENT> 状态下匹配到非 EOF 的任意字符，都保持当前状态。<COMMENT> 状态下匹配到 EOF，就返回未闭合注释错误。
对于注释的内容，我们在用户代码中手动维护，这个我们 之后 再详细阐述。这样我们就优雅地实现了多行注释的匹配，可读性也比仅使用正则表达式要好很多。
最后，我们使用 <INITIAL>. 规则进行兜底，用来处理源文件中出现的未知字符。
1.3 用户代码区
为了代码结构清晰，我们将用户代码单独分出来，作为一个独立的文件 src/main.cpp。一些琐碎的细节（例如文件 I/O 的实现）这里就不赘述了，具体可以直接参见源代码。我们这里只讲关键的 token 所在行列号和类型的判断，以及报错功能的实现。
1.3.1 判断 token 所在行列号
核心思路实际上就是维护 Flex 当前扫描到的位置。由于 Flex 会自行维护当前所在的行号，因此我们的重点在于维护当前所在的列号。当然，对于多行注释，我们也需要手动维护注释起始位置的行号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // src/main.cpp
std::tuple<int, int> UpdatePosition(const yyFlexLexer& lexer) {
static int cur_row = 1; // self-maintained current row number
static int cur_column = 1; // self-maintained current column number
auto start_row = cur_row;
auto start_column = cur_column;
std::string token = lexer.YYText();
auto size = lexer.YYLeng();
if (lexer.lineno() == start_row) {
cur_column += size;
} else {
cur_row = lexer.lineno();
auto endl_pos = token.find_last_of('\n');
cur_column = endl_pos == std::string::npos ? size : size - endl_pos;
}
return {start_row, start_column};
}
|
具体来说，我们的思路是利用 Flex 当前匹配到的单词长度 yyleng（C++ API 下需使用函数 YYLeng() 读取）作为当前所在列关于上次扫描时的偏移量，然后根据上次扫描时所在的列号，计算出本次扫描时所在的列号。因此，我们在扫描时也需要读入空白字符，不能直接简单跳过了。当读取到换行符时，行号加 1，列号归 0。
这里为了程序的可维护性，考虑到多行注释可能存在的不同实现，我们保持了对一次性读入多行注释这种情况的支持。这种情况下，读入的文本 yytext 中可能包含换行符，因此不能简单通过增加一个 yyleng 就得到当前列号。这里如果我们发现当前所在行（由 Flex 自动维护的 yylineno）与上次扫描时不同，说明读入的文本中存在换行符。那么我们就找到换行符最后一次出现的位置，计算这个位置到文本末尾的距离，即可得到实际的列号。
这样，我们就得到 token 所在的行列号了。需要注意的是，我们多行注释目前的实现会实时更新当前所在的位置，但我们需要的其实是注释的起始位置，也就是 (* 的位置。当然我们也不能不让它更新位置了，不然之后读入的 token 就会出现行列号错误的问题。我们这里采用的方案是，简单备份一下 (* 所在的位置，之后遇到 *) 时，输出这个备份的起始位置就可以了。
1.3.2 判断 token 的类型
这个很简单，直接调用函数 yylex() 得到当前 token 的类型，然后用一个 switch 语句还原成一个字符串就可以了。例如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // src/main.cpp
auto t = lexer.yylex();
auto [type, error_msg] =
[&token](int t) -> std::tuple<const char*, const char*> {
switch (t) {
case T_REAL: return {"real", NULL};
case T_OPERATOR: return {"operator", NULL};
case T_DELIMITER: return {"delimiter", NULL};
// ...
default: return {"error", "UnknownError"};
}
}(t);
|
这里变量 type 保存的就是输出的 token 类型。
1.3.3 实现报错功能
一个 PCAT 程序中可能出现以下几种词法错误：
- 整数大小超过 $2^{31}-1$
- 字符串常量的长度（不含引号）超过 $255$
- 字符串中包含非法字符 tab
- 标识符长度超过 $255$
- 未闭合的字符串（没有右引号）
- 未闭合的注释（没有
*)） - 出现未知字符
下面我们依次介绍这些报错功能都是如何实现的。
1.3.3.1 整数错误
整数的越界错误我们是留到用户代码区再处理的，因为这样比较方便。具体来说，当 token 类型是整数时，我们先检查它的位数（十进制）是否超过 $10$。因为如果位数超过 $10$ 了，就一定大于 $2147483647$ 了。这样做是为了防止类型转换时发生越界。对于 $10$ 位以内的整数，我们就可以放心地利用函数 std::stoull() 转换为 64 位整型 uint64_t 了，然后简单地和 INT32_MAX 比一下大小即可。
1
2
3
4
5
6
7
8
| // src/main.cpp
case T_INTEGER: {
if (token.size() > 10 || std::stoull(token) > INT32_MAX) {
return {"error", "RangeError: out of range"};
}
return {"integer", NULL};
}
|
1.3.3.2 字符串错误
字符串的错误分为 3 种。对于字符串值相关的 2 种错误，我们可以简单地留到用户代码区解决。具体来说，先判断一下总长度（含引号）是否超过 $257$，然后查找一下字符串中是否包含 tab 就可以了。
1
2
3
4
5
6
7
8
9
10
| // src/main.cpp
case T_STRING: {
if (token.size() > 257) {
return {"error", "ValueError: string literal is too long"};
} else if (token.find('\t') != std::string::npos) {
return {"error", "ValueError: invalid character found in string"};
}
return {"string", NULL};
}
|
而对于字符串未闭合的错误，由于未闭合的字符串从定义上来说就不是字符串了，因此需要在规则区解决。之前我们在 token 分类时有一个对应未闭合字符串的 E_UNTERM_STRING 类别，就是用于这种情况的报错实现。
1
2
3
4
| // src/main.cpp
case E_UNTERM_STRING:
return {"error", "SyntaxError: unterminated string literal"};
|
1.3.3.3 标识符错误
标识符过长的报错处理和字符串是一样的，这里不再赘述。
1
2
3
4
5
6
7
8
| // src/main.cpp
case T_IDENTIFIER: {
if (token.size() > 255) {
return {"error", "CompileError: identifier is too long"};
}
return {"identifier", NULL};
}
|
出现未知字符或许也可以算标识符错误吧。处理方式之前已经提到了，就是在规则区利用一个兜底规则，将所有未成功匹配的字符都判定为未知字符。
1
2
3
4
| // src/main.cpp
case E_UNKNOWN_CHAR:
return {"error", "CompileError: unknown character"};
|
1.3.3.4 注释错误
注释的错误是最难处理的，因为我们还需要手动维护注释的内容（如果希望在报错信息里展示的话）。为什么不能简单地使用函数 yymore() 呢？其实普通注释是可以的，但对于未闭合的注释，Flex 将不可避免地读入 EOF。而当 Flex 读到 EOF 时，会直接清空当前的 yytext 缓冲区，而这个问题是很难规避的，于是注释的内容就保存不下来了。比较好的解决方案就是手动维护。
先看代码（只保留了注释处理相关的部分）：
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
| // src/main.cpp
static std::string buf; // self-maintained buffer for comments
static int start_row_bak = 1;
static int start_column_bak = 1;
auto t = lexer.yylex();
auto [start_row, start_column] = UpdatePosition(lexer);
std::string token = lexer.YYText();
switch (t) {
// ...
case T_COMMENTS_BEGIN: {
start_row_bak = start_row;
start_column_bak = start_column;
// fallthrough
}
case T_COMMENTS: {
buf += token;
break;
}
case E_UNTERM_COMMENTS:
case T_COMMENTS_END: {
// Use the actual starting position of T_COMMENTS_BEGIN.
start_row = start_row_bak;
start_column = start_column_bak;
token = buf + token;
buf.clear();
// fallthrough
}
default: {
auto [type, error_msg] =
[&token](int t) -> std::tuple<const char*, const char*> {
switch (t) {
case T_COMMENTS_END: return {"comments", NULL};
case E_UNTERM_COMMENTS:
return {"error", "SyntaxError: unterminated comments"};
// ...
}
}(t);
// Output to file
}
}
|
具体来说：
- 当遇到注释开头
T_COMMENTS_BEGIN 时，备份注释开头所在的行列号，将本次读入的文本（也就是 (*）附加到缓冲区 buf 末尾。 - 当遇到注释文本
T_COMMENTS 时，将读入的文本附加到 buf 末尾。 - 当遇到注释结尾
T_COMMENTS_END 或遇到 EOF（也就是注释未闭合的情况 E_UNTERM_COMMENTS）时，还原注释开头所在的行列号，将读入的文本（也就是 *)）附加到 buf 末尾，并将 buf 的内容（也就是注释的完整内容）作为 token。然后清空 buf，进入下一阶段。- 对于
T_COMMENTS_END 的情况，说明注释格式正确，正常输出。 - 对于
E_UNTERM_COMMENTS 的情况，说明注释未闭合，进入报错逻辑。
至此，所有词法错误的报错功能就实现完了。
2 运行本项目
2.1 构建与运行
本项目使用 C++17 编写，构建前需要先安装以下依赖：
执行 make 即可构建并运行本项目，默认是进入命令行交互模式，按 CTRL + D 键退出。如果需要从文件中读入，则执行 make INPUT=<path>，其中 <path> 即为指定的文件路径。例如：
1
| make INPUT="tests/case_1.pcat"
|
输出文件将默认保存在 output 目录下。
2.2 测试
本项目自带了 14 个 PCAT 语言测试样例，位于 tests 目录下。测试时依次通过上述命令处理即可，或者你也可以编写一个简单的 bash 脚本。
例如对于这样的输入（tests/case_1.pcat）：
1
2
3
4
5
6
7
8
| PROGRAM IS
VAR i, j : INTEGER := 1;
VAR x : REAL := 2.0;
VAR y : REAL := 3.0;
BEGIN
WRITE ("i = ", i, ", j = ", j);
WRITE ("x = ", x, ", y = ", y);
END;
|
就将得到这样的输出：
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
| ROW COL TYPE TOKEN / ERROR MESSAGE
--------------------------------------------------------------------------------
1 1 reserved keyword PROGRAM
1 9 reserved keyword IS
2 5 reserved keyword VAR
2 9 identifier i
2 10 delimiter ,
2 12 identifier j
2 14 delimiter :
2 16 identifier INTEGER
2 24 operator :=
2 27 integer 1
2 28 delimiter ;
3 5 reserved keyword VAR
3 9 identifier x
3 11 delimiter :
3 13 identifier REAL
3 18 operator :=
3 21 real 2.0
3 24 delimiter ;
4 5 reserved keyword VAR
4 9 identifier y
4 11 delimiter :
4 13 identifier REAL
4 18 operator :=
4 21 real 3.0
4 24 delimiter ;
5 1 reserved keyword BEGIN
6 5 reserved keyword WRITE
6 11 delimiter (
6 12 string "i = "
6 18 delimiter ,
6 20 identifier i
6 21 delimiter ,
6 23 string ", j = "
6 31 delimiter ,
6 33 identifier j
6 34 delimiter )
6 35 delimiter ;
7 5 reserved keyword WRITE
7 11 delimiter (
7 12 string "x = "
7 18 delimiter ,
7 20 identifier x
7 21 delimiter ,
7 23 string ", y = "
7 31 delimiter ,
7 33 identifier y
7 34 delimiter )
7 35 delimiter ;
8 1 reserved keyword END
8 4 delimiter ;
--------------------------------------------------------------------------------
Total: 50 tokens, 0 errors
|
参考资料
- Flex - a scanner generator
- The PCAT Programming Language Reference Manual
