手写词法分析器（二）

学习目标

通过本集的学习，你将能够：

学会识别标识符
学会识别关键字
学会识别运算符
掌握状态机的完整实现

1. 识别标识符

1.1 标识符的规则

标识符通常以字母或下划线开头，后面可以跟字母、数字或下划线。

标识符的正则表达式：
[a-zA-Z_][a-zA-Z0-9_]*

例子：
✓ count
✓ _temp
✓ myVar123
✗ 123abc  （不能以数字开头）
✗ my-var  （不能包含连字符）

1.2 标识符的状态机

状态转换图：

     开始
      │
      ▼
   [a-zA-Z_] → 标识符状态 ─┐
      │                     │
      └──── [a-zA-Z0-9_] ───┘
      │
      └─── 其他字符 ──→ 结束

状态说明：
- START：初始状态
- IN_IDENT：正在识别标识符

1.3 代码实现

def identifier(self):
    result = ''
    while (self.current_char is not None and 
           (self.current_char.isalnum() or 
            self.current_char == '_')):
        result += self.current_char
        self.advance()
    
    # 检查是否是关键字
    keywords = {'if', 'else', 'while', 'for', 'return'}
    if result in keywords:
        return ('KEYWORD', result)
    else:
        return ('IDENTIFIER', result)

2. 识别关键字

2.1 关键字表

关键字是编程语言预定义的特殊标识符。我们通常使用一个集合或字典来存储关键字。

# 关键字集合
KEYWORDS = {
    'if': 'IF',
    'else': 'ELSE',
    'while': 'WHILE',
    'for': 'FOR',
    'return': 'RETURN',
    'int': 'INT',
    'float': 'FLOAT',
    'void': 'VOID'
}

2.2 关键字识别流程

识别标识符后：
    ┌─────────────────────────┐
    │  检查是否在关键字表中？  │
    └──────────┬──────────────┘
           是│              │否
            ▼              ▼
    返回关键字Token    返回标识符Token

3. 识别运算符

3.1 运算符的种类

运算符可以是单字符或多字符的：

单字符运算符：
+  -  *  /  =  <  >  !  &  |

多字符运算符：
==  !=  <=  >=  &&  ||  +=  -=  *=  /=

3.2 运算符的最长匹配原则

最长匹配原则（Maximal Munch）：
在有歧义时，选择最长的有效运算符。

例子：
输入 "==" 应该识别为 "=="，而不是两个 "="
输入 "!=" 应该识别为 "!="，而不是 "!" 后跟 "="

3.3 运算符识别代码

def operator(self):
    # 先看当前字符
    char = self.current_char
    self.advance()
    
    # 检查是否是多字符运算符
    if char == '=' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '==')
    elif char == '!' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '!=')
    elif char == '<' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '<=')
    elif char == '>' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '>=')
    elif char == '+' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '+=')
    elif char == '-' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '-=')
    else:
        # 单字符运算符
        return ('OPERATOR', char)

4. 完整的词法分析器实现

4.1 完整代码

class Lexer:
    def __init__(self, source):
        self.source = source
        self.pos = 0
        self.current_char = self.source[0] if source else None
        
        # 关键字表
        self.KEYWORDS = {
            'if': 'IF',
            'else': 'ELSE',
            'while': 'WHILE',
            'for': 'FOR',
            'return': 'RETURN'
        }
    
    def advance(self):
        self.pos += 1
        if self.pos < len(self.source):
            self.current_char = self.source[self.pos]
        else:
            self.current_char = None
    
    def skip_whitespace(self):
        while self.current_char is not None and self.current_char.isspace():
            self.advance()
    
    def number(self):
        result = ''
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        return ('NUMBER', int(result))
    
    def identifier(self):
        result = ''
        while (self.current_char is not None and 
               (self.current_char.isalnum() or 
                self.current_char == '_')):
            result += self.current_char
            self.advance()
        
        if result in self.KEYWORDS:
            return (self.KEYWORDS[result], result)
        else:
            return ('IDENTIFIER', result)
    
    def get_next_token(self):
        while self.current_char is not None:
            if self.current_char.isspace():
                self.skip_whitespace()
                continue
            elif self.current_char.isalpha() or self.current_char == '_':
                return self.identifier()
            elif self.current_char.isdigit():
                return self.number()
            elif self.current_char in '+-*/=<>!':
                # 这里简化了运算符处理
                char = self.current_char
                self.advance()
                return ('OPERATOR', char)
            elif self.current_char == '(':
                self.advance()
                return ('LPAREN', '(')
            elif self.current_char == ')':
                self.advance()
                return ('RPAREN', ')')
            elif self.current_char == '{':
                self.advance()
                return ('LBRACE', '{')
            elif self.current_char == '}':
                self.advance()
                return ('RBRACE', '}')
            elif self.current_char == ';':
                self.advance()
                return ('SEMICOLON', ';')
            else:
                raise Exception(f'Invalid character: {self.current_char}')
        
        return ('EOF', None)

4.2 使用词法分析器

# 测试词法分析器
source = '''
if (x == 10) {
    return x + 5;
}
'''

lexer = Lexer(source)

while True:
    token = lexer.get_next_token()
    print(token)
    if token[0] == 'EOF':
        break

输出：

('IF', 'if')
('LPAREN', '(')
('IDENTIFIER', 'x')
('OPERATOR', '=')
('OPERATOR', '=')
('NUMBER', 10)
('RPAREN', ')')
('LBRACE', '{')
('RETURN', 'return')
('IDENTIFIER', 'x')
('OPERATOR', '+')
('NUMBER', 5)
('SEMICOLON', ';')
('RBRACE', '}')
('EOF', None)

5. 实用案例

5.1 案例1：处理多字符运算符

def operator(self):
    char = self.current_char
    self.advance()
    
    # 检查双字符运算符
    if char == '=' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '==')
    elif char == '!' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '!=')
    elif char == '<' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '<=')
    elif char == '>' and self.current_char == '=':
        self.advance()
        return ('OPERATOR', '>=')
    else:
        return ('OPERATOR', char)

5.2 案例2：添加更多关键字

# 扩展关键字表
self.KEYWORDS = {
    'if': 'IF',
    'else': 'ELSE',
    'while': 'WHILE',
    'for': 'FOR',
    'return': 'RETURN',
    'break': 'BREAK',
    'continue': 'CONTINUE',
    'int': 'INT',
    'float': 'FLOAT',
    'string': 'STRING',
    'void': 'VOID',
    'true': 'TRUE',
    'false': 'FALSE',
    'null': 'NULL'
}

6. 自测问题

如何识别标识符？
如何区分关键字和标识符？
什么是最长匹配原则？
如何处理多字符运算符？
词法分析器的主循环是如何工作的？

7. 下集预告

下一集我们将学习手写词法分析器（三），包括处理空白字符、注释和字符串字面量！

参考资料

《编译原理》（龙书）
《现代编译原理》（虎书）