写一个词法分析器

设计

对于一个简单的词法分析器,大概只需要1个可变状态,2个接口,若干辅助函数。

  • 词法分析器的状态应该包括

    • 现在分析到哪个字符了
    • 当前会是什么标记 (Token),标记的种类,在源代码中的位置,标记的长度
  • 词法分析器的接口

    • Lexer lex_init(const char *code); 用源代码初始化词法分析器,Lexer 是一个词法分析器实例,保存着词法分析器的内部状态,在面向对象语言中相当于构造器, new 的过程。
    • Tok *lex_next(Lexer lexer); 解析出下一个标记,Tok 代表着一个标记,调用者循环调用该函数可完成全部源代码的解析,调用者也可以在遇到词法错误时结束词法分析的过程,不再继续调用该函数。
  • 辅助函数

    主要分为两种,分别是 is_XXX 和 get_XXX,分别用于判断当前要解析的字符是否可能是某种标记,和从当前开始解析一个标记,并移动当前解析到哪里的指针。

定义结构体

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
enum {
TOK_EOF, // 读到了尽头
TOK_INVALID, // 出现了词法错误

TOK_ELLIPSIS,
TOK_RIGHT_ASSIGN,
TOK_LEFT_ASSIGN,
TOK_ADD_ASSIGN,
TOK_SUB_ASSIGN,
TOK_MUL_ASSIGN,
TOK_DIV_ASSIGN,
TOK_MOD_ASSIGN,
TOK_AND_ASSIGN,
TOK_XOR_ASSIGN,
TOK_OR_ASSIGN,
TOK_RIGHT_OP,
TOK_LEFT_OP,
TOK_INC_OP,
TOK_DEC_OP,
TOK_PTR_OP,
TOK_AND_OP,
TOK_OR_OP,
TOK_LE_OP,
TOK_GE_OP,
TOK_EQ_OP,
TOK_NE_OP,

TOK_CONSTANT,
TOK_STRING_LITERAL,

TOK_AUTO = 200, // 为了避免和'+' , '-' 等 ascii 码片冲突
// 此外 200 及以上都属于标识符 (IDENTIFIER)
TOK_BREAK,
TOK_CASE,
TOK_CHAR,
TOK_CONST,
TOK_CONTINUE,
TOK_DEFAULT,
TOK_DO,
TOK_DOUBLE,
TOK_ELSE,
TOK_ENUM,
TOK_EXTERN,
TOK_FLOAT,
TOK_FOR,
TOK_GOTO,
TOK_IF,
TOK_INT,
TOK_LONG,
TOK_REGISTER,
TOK_RETURN,
TOK_SHORT,
TOK_SIGNED,
TOK_SIZEOF,
TOK_STATIC,
TOK_STRUCT,
TOK_SWITCH,
TOK_TYPEDEF,
TOK_UNION,
TOK_UNSIGNED,
TOK_VOID,
TOK_VOLATILE,
TOK_WHILE,
TOK_IDENTIFIER
};

下面定义一个 Token 元素的结构。

  • tok 对于单字符操作符,这里存储的就是字符本身 ( ASCII 码 ) ,其他的存储的是枚举类型的值。
  • len 该标记的长度 比如 对于 struct 长度就是 5 , == 长度就是 2 , "asdf" 长度就是 6 。
  • ptr 该标记的在源码字符串中的起始位置。
  • line_num 该标记所在的行号。
    1
    2
    3
    4
    5
    6
    typedef struct token_s {
    int tok;
    int len;
    char *ptr;
    int line_num; // 行号
    } Tok;

Lexer

该结构体存储了词法分析器的状态

  • cur 指针指向当前正在处理的字符(相对于源码)
  • tok 表示正在解析的标记
  • line_num 毫无疑问的是行号
    1
    2
    3
    4
    5
    struct lexer_s {
    char *cur;
    Tok tok;
    int line_num;
    };

初始化一个词法分析器需要传入待分析的代码作为输入。

1
2
3
4
5
Lexer lex_init(const char *code) {
struct lexer_s *l = calloc(sizeof(struct lexer_s), 1);
l->cur = code;
return l;
}

解析的流程

定义next方法每次产生一个新的 Tok 并将其返回,词法分析的过程就是不断调用 next 方法直到其返回的 Tok 的种类是 TOK_EOF

1
2
3
4
5
6
7
main(){
// ...
while ((tok = lex_next(l))->tok != TOK_EOF) {
// do something with tok
}
// ...
}

next 方法终于工作是,通过当前字符以及当前字符的下一个字符,或者当前字符的后几个字符,来确定是哪种类型的标记,并将其返回。所以整体结构是许多 IF-ELSE 的堆叠。但需要注意的是,像空行、空格、注释等都是无法产生合法标记流的字符,需要将他们跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static Tok *next(struct lexer_s *l) {
int tok = TOK_INVALID, _tok;

skip_spaces_and_comments(l);
l->tok.ptr = l->cur;
l->tok.line_num = l->line_num;

if (*l->cur == '\0') {
tok = TOK_EOF;
} else if (is_digit(*l->cur)) {
tok = get_num(l);
} else if ...

if (l->cur != '\0') l->cur++;
l->tok.tok = tok;
return &l->tok;

}

skip_spaces_and_comments 跳过无效字符

无效字符有三种

  1. 空白字符 (空格、制表符、换行符等) 正则: [ \t\v\n\f]
  2. 单行注释 以 // 开头,直到行末
  3. 多行注释 以 /* 开头直到 */
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
static bool is_space(int c) {
return c == ' ' || c == '\r' || c == '\n' || c == '\t' || c == '\f' ||
c == '\v';
}
static void skip_spaces_and_comments(struct lexer_s *l) {
const char *pos;
do {
pos = l->cur;
// 处理空白字符
while (is_space(l->cur[0])) {
if (l->cur[0] == '\n') l->line_num++;
l->cur++;
}

// 处理单行注释
if (l->cur[0] == '/' && l->cur[1] == '/') {
while (l->cur[0] != '\0' && l->cur[0] != '\n') l->cur++;
}

// 处理多行注释
if (l->cur[0] == '/' && l->cur[1] == '*') {
l->cur += 2;
while (l->cur[0] != '\0') {
if (l->cur[0] == '\n') l->line_num++;
if (l->cur[0] == '*' && l->cur[1] == '/') {
l->cur += 2;
break;
}
l->cur++;
}
}
} while (pos < l->cur);
}

is_alpha & get_identifier & is_keyword 处理标识符和关键字

再定义两个简洁直观的辅助函数 is_alphais_digit 用于判断当前字符是否为字母和数字。

1
2
3
4
5
6
7
static bool is_alpha(int c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

static bool is_digit(int c) {
return c >= '0' && c <= '9';
}

想一想 C 语言中的标识符的规则是什么,也就是变量的合法名称,以字母或下划线开头,后面可以跟随下划线、字母和数字,用正则表达式表示就是 a-zA-Z_*

next 函数中添加这么一条判断,如果当前字符符合标识符规则,那么就获取一个标识符。(1)

1
2
3
if (is_alpha(*l->cur) || l->cur[0] == '_') {
tok = get_identifier(l); // (1)
if ((_tok = is_keyword(l->tok.ptr, l->tok.len)) != 0) tok = _tok; // (2)
1
2
3
4
5
6
7
8
static int get_identifier(struct lexer_s *l) {
l->cur++;
while (l->cur[0] != '\0' && (is_alpha(*l->cur) ||
is_digit(*l->cur) || l->cur[0] == '_')) l->cur++;
l->tok.len = l->cur - l->tok.ptr;
l->cur--;
return TOK_IDENTIFIER;
}

我们知道,关键字也是标识符,使用 is_keyword 加以区分。

1
2
3
4
5
6
7
8
9
10
11
12
13
static int is_keyword(const char *s, int len) {
const char *reserved[] =
{"auto", "break", "case", "char", "const", "continue", "default", "do", "double", "else",
"enum", "extern", "float", "for", "goto", "if", "int", "long", "register", "return",
"short", "signed", "sizeof", "static", "struct", "switch", "typedef", "union", "unsigned",
"void", "volatile", "while", NULL};
if (!is_alpha(s[0])) return 0;
for (int i = 0; reserved[i] != NULL; i++) {
if (len == (int) strlen(reserved[i]) && strncmp(s, reserved[i], len) == 0)
return i + TOK_AUTO;
}
return 0;
}

将得到的标识符去与关键字列表进行判等匹配,由于reserved中的关键字列表顺序和 enum 中关键字顺序一致,使用 i + TOK_AUTO 进行偏移简化代码书写,is_keyword 函数当输入是一个关键字的时候返回对应的标记种类,如果不是关键字则返回0,在(2)中判断。

处理数字常量

C 语言中数字常量有一下几种形式

  • ‘a’ 字符常量

  • 12343 整数类型

    • 0x123 16 进制数字
    • 0b1101 2 进制数字
  • 3.14 浮点数字

    • 123e+2f 科学计数法
1
2
3
4
if (is_digit(*l->cur)) {
tok = get_num(l);
} else if (*l->cur == '\'') {
tok = get_char(l);

​ 由于这里只做标记的分割,只需要知道这个标记到底有多长,不做具体类型的区分,故使用 strtod 可以同时处理整数、浮点数(含科学计数法形式)。

1
2
3
4
5
6
7
static int get_num(struct lexer_s *l) {
strtod(l->cur, &l->cur);
if (strchr("fFlLuU", *l->cur) != NULL) l->cur++;
l->tok.len = l->cur - (char *) l->tok.ptr;
l->cur--;
return TOK_CONSTANT;
}

处理字符常量 ‘a’ ‘\n’

1
2
3
4
5
6
7
8
9
10
11
// 对于 '\0' 这种形式,两个单引号之间未必只有一个字符
static int get_char(struct lexer_s *l) {
l->cur++;
if (l->cur[0] == '\\') l->cur++; // skip \0 ...
if (l->cur[0] != '\0') l->cur++;
if (l->cur[0] == '\'') {
l->tok.len = l->cur - l->tok.ptr+1;
return TOK_CONSTANT;
}
return TOK_INVALID;
}

处理字符串常量

字符串常量就是以双引号包围的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
else if (*l->cur == '\"') {
tok = get_string_literal(l);

static int get_string_literal(struct lexer_s *l) {
l->cur++;
while (l->cur[0] != '\0' && l->cur[0] != '\"') {
if (l->cur[0] == '\\' && l->cur[1] != '\0' &&
// 遇到转译符要跳过两个,避免触发 l->cur[0] != '\"' 错误滴结束循环
(l->cur[1] == '\"' || strchr("bfnrtv\\", l->cur[1]) != NULL)) {
l->cur += 2;
} else {
l->cur++;
}
}
l->tok.len = l->cur - l->tok.ptr + 1;
return TOK_STRING_LITERAL;
}

最后处理 单目 双目 运算符

这里需要向后看1之多个字符,定义以下辅助函数,这里的处理和 is_keyword有相似之处。

1
2
3
4
5
6
7
8
9
10
11
12
static int get_symbol(struct lexer_s *l) {
char *symbols[] = {"...", ">>=", "<<=", "+=", "-=", "*=", "/=", "%=", "&=", "^=", "|=", ">>", "<<", "++", "--",
"->", "&&", "||", "<=", ">=", "==", "!=", NULL};
for (int i = 0; symbols[i] != NULL; i++) {
int len = strlen(symbols[i]);
if (strncmp(l->cur, symbols[i], len) == 0) {
l->cur += len - 1;
return i + TOK_ELLIPSIS;
}
}
return 0;
}

处理这些符号的时候,本着最长匹配原则,因为”==” 应该解析成一个判断号而不是两个赋值号,无论符合长度如何,他们的起始字符都应出现在 “;{},:=()[].&!~-+*/%<>^|?” 中,这里的处理与标识符&关键字的处理有相似之处。

1
2
3
4
5
else if (strchr(";{},:=()[].&!~-+*/%<>^|?", *l->cur) != NULL) {
tok = *l->cur;
if ((_tok = get_symbol(l)) != 0) tok = _tok;
l->tok.len = l->cur - l->tok.ptr + 1;
}

统计单词个数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::string code(std::istreambuf_iterator<char>(cin), {}); // 从标准输入流中获取代码
Lexer l = lex_init(code.c_str()); // 初始化词法分析器
map<std::string, int> words_count; // 单词计数器

Tok *tok;
while ((tok = lex_next(l))->tok != TOK_EOF) {
if (tok->tok >= TOK_AUTO) { // 200 以上都属于标识符 (IDENTIFIER)
auto key = std::string(tok->ptr, tok->len);
if (words_count.count(key) > 0) {
words_count[key] = words_count[key] + 1;
} else {
words_count[key] = 1;
}
}
}

for (auto &iter : words_count) {
cout << iter.first << " : " << iter.second << endl;
}

free(l); //用完了之后释放词法分析器所占用的空间

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×