词法分析¶

约 1330 个字 22 行代码预计阅读时间 7 分钟

为什么要把词法分析和语法分析分开

从本质上来说,词法分析使用的是DFA,语法分析使用的是CFG,如果不先做一步词法分析,语法分析当然也能涵盖词法分析的能力,但是会让语法分析的过程显得更复杂

Lexical Token¶

词法分析器会把字符流切分为一系列 Token。常见类别如下:

区分元字符与字面量

在正则中,. 通常是元字符；但放进引号后(如 "a.*"),可按普通文本处理。

Token 类别	作用	示例
关键字 (Keyword)	语言保留字,有固定语义	`if`, `while`, `int`, `return`
标识符 (Identifier)	程序员定义的名字	`sum`, `count`, `main`
字面量 (Literal)	直接写在代码里的常量值	`123`, `3.14`, `'a'`, `"hello"`
运算符 (Operator)	表示运算或比较	`+`, `-`, `*`, `/`, `==`, `=`
分隔符 (Delimiter / Punctuation)	分隔语句或表达式结构	`;`, `,`, `(`, `)`, `{`, `}`

实际上,字面量还可以分为NUM(整数)与REAL(实数)等.

类似的, 还有一些内容被称为 Non-tokens，它们在经过词法分析器时会被直接跳过或丢弃，不生成 Token 传递给语法分析器，主要包括：

空白字符 (Whitespaces)：包括空格 (Space)、制表符 (Tab)、换行符 (Newline) 等。它们的作用通常仅是为了分隔其他的 Token。
注释 (Comments)：包括单行注释（如 // ...）和多行注释（如 /* ... */）。代码注释纯粹是为了人类阅读，对程序的语义没有实质影响。
预处理指令 (Preprocessor Directives)：比如在 C/C++ 中的 #include、#define 等，它们通常在独立的预处理阶段或者词法阶段初就被执行或展开，不会作为原本的 Token 交给后端的分析阶段。

以下面这段代码为例:

#include<stdio.h>
#define ZERO 0.

/* find a zero */
float match0(char *s) { 
    if (!strncmp(s, "0.0", 3))
    return ZERO; 
}

有些编译器会预先过滤为:

float match0(char *s) {
    if (!strncmp(s,"0.0",3))    
    return 0.;}

对应的 Token 序列可以写成:

FLOAT ID(match0) LPAREN CHAR STAR ID(s) RPAREN LBRACE
IF LPAREN BANG ID(strncmp) LPAREN ID(s) COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN
RETURN REAL(0.0) SEMI
RBRACE EOF

词法分析与 Token 规则总结

标识符规则 (Identifiers): 标识符由字母和数字组成，且首字符必须是字母。其中，下划线 _ 被视为字母。
大小写敏感 (Case Sensitivity): 大写字母和小写字母是不同的（例如 Var 和 var 是两个不同的标识符）。
最长匹配原则 (Maximal Munch): 当输入流被解析为 Token 时，如果遇到一个字符，分析器会尽可能地去匹配能构成合法 Token 的最长字符串（例如遇到 == 会解析为一个等号运算符 Token，而不是两个赋值运算符 = 分离的 Token）。
非记号过滤 (Non-tokens): 空白字符 (空格、制表符、换行符) 以及注释都会被直接忽略，除非它们的作用是用于分隔其他的 Token。
必要的分隔: 在某些情况下（如相邻的标识符、关键字、常量之间），必须需要使用空白字符将它们隔开，否则它们会被根据最长匹配原则合并为一个 Token。

正则表达式¶

重复的内容不讲了,在这里

写法	含义	示例说明
`[abcd]`	匹配括号内任意一个字符	等同于 `(a \| b \| c \| d)`
`[b-g]`	匹配范围内的任意一个字符	等同于 `[bcdefg]`
`[b-gM-Qkr]`	匹配多个范围或独立字符中的任意一个	等同于 `[bcdefgMNOPQkr]`
`M?`	匹配 \(M\) 零次或一次（可选）	等同于 `(M \| ε)`
`M+`	匹配 \(M\) 一次或多次（至少一次）	等同于 `(M · M*)`
`.`	匹配除换行符外的任意单个字符	`a.c` 可匹配 `abc`、`a9c`
`"a.*"`	引号中的字符串按字面意义匹配	表示字符序列 `a.*` 本身,而不是“a 后跟任意字符”

下面,我们可以看一些例子:

if                                      { return IF; }
[a-z][a-z0-9]*                          { return ID; } 
[0-9]+                                  { return NUM; } 
([0-9]+"."[0-9]*)|([0-9]*"."[0-9]+)     { return REAL; }
("--"[a-z]*"\n")|(" "|"\n"|"\t")+       { /* do nothing */ }
.                                       { error(); }

if { return IF; }：遇到了保留字 if，直接返回 IF 这个 Token。
[a-z][a-z0-9]* { return ID; }：匹配以小写字母开头，后接零个或多个小写字母/数字的字符串。这就是前面定义的标识符规则，返回 ID。
[0-9]+ { return NUM; }：匹配一个或多个数字序列，返回整数型 Token NUM。
([0-9]+"."[0-9]*)|([0-9]*"."[0-9]+) { return REAL; }：左半部分匹配 123. 这种形式，右半部分匹配 .456 这种形式，共同构成了浮点数规则，返回 REAL。
("--"[a-z]*"\n")|(" "|"\n"|"\t")+ { /* do nothing */ }：用来匹配哪些Non-tokens
- 左边 "--"[a-z]*"\n" 用于匹配以 -- 开头的单行注释。
- 右边 (" "|"\n"|"\t")+ 用于匹配一个及以上的空格、换行或制表符（空白字符）。
. { error(); }：. 表示匹配除换行符以外的任何其他单字符。相当于一个兜底策略,如果前面的匹配都没对上,说明匹配出了问题,因此这里要返回一个报错

事实上,有了上面这些规则之后还无法完成词法分析的内容,因为仍然存在歧义

if8

"if8"既可以被识别为ID(if8),也可以被识别为IF NUM(8),我们应该如何区分这两种?

和计网里面学过的最长子网前缀匹配规则一样,当有一个串可以被多种方式匹配时,我们选择能匹配最长子串的方式,在这里就表现为ID(if8)
另外,如果两种方式都能匹配同样长的子串,我们按照匹配规则的重要性选择.因此,if会被当作IF而不是ID(if),因为保留字的匹配优先级更高.

词法分析¶

Lexical Token¶

正则表达式¶

评论