第71集：语法分析器是什么？
学习目标
- 理解语法分析的核心任务
- 掌握语法分析器在编译过程中的位置和作用
- 了解语法错误的概念和处理方式
- 认识语法树的结构和作用
一、语法分析的任务
语法分析是编译过程的第二个阶段，紧随词法分析之后。如果说词法分析是将源代码分解为一个个 Token（词法单元），那么语法分析就是将这些 Token 按照语言的语法规则组织成有意义的结构。
核心任务
- 结构识别：分析 Token 序列是否符合语言的语法规则
- 语法树构建：将符合语法规则的 Token 序列构建成语法树（Syntax Tree）
- 错误检测：当发现语法错误时，及时报告错误位置和类型
- 错误恢复：在遇到错误时，尝试恢复分析过程，以便发现更多错误
输入与输出
- 输入：词法分析器生成的 Token 序列
- 输出：语法树（或抽象语法树 AST）
二、语法分析器的位置
在整个编译过程中，语法分析器位于词法分析器和语义分析器之间，起到承上启下的作用：
┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ 词法分析器 │────>│ 语法分析器 │────>│ 语义分析器 │────>│ 中间代码生成 │
└─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘
↑ ↑ ↑ ↑
│ │ │ │
字符流 Token 流 语法树 中间代码与其他组件的关系
- 与词法分析器：语法分析器从词法分析器获取 Token，是词法分析的直接消费者
- 与语义分析器：语法分析器生成的语法树是语义分析的输入
- 与错误处理：语法分析器需要检测和报告语法错误，为后续处理提供错误信息
三、语法错误
在编译过程中，语法错误是常见的问题，语法分析器需要能够有效地检测和处理这些错误。
常见的语法错误
缺少符号：例如缺少分号、括号等
int main() { printf("Hello") // 缺少分号 }多余符号：例如多余的分号、括号等
int main() { int a = 10;; // 多余的分号 }符号顺序错误：例如运算符顺序错误
int main() { int a = 10 = b; // 赋值运算符顺序错误 }结构不完整：例如缺少函数体、循环体等
int main() // 缺少函数体
错误处理策略
- 错误检测：识别不符合语法规则的 Token 序列
- 错误报告：向用户报告错误的位置、类型和可能的原因
- 错误恢复：尝试从错误中恢复，继续分析后续代码
- 错误计数：统计错误数量，决定是否继续编译
四、语法树的作用
语法树是语法分析器的核心输出，它是源代码的结构化表示，具有重要的作用。
语法树的结构
语法树以树状结构表示源代码的语法结构，其中：
- 根节点：表示整个程序或主要结构
- 内部节点：表示运算符、语句、表达式等
- 叶节点：表示终结符（如标识符、常量、运算符等）
例如，表达式 a + b * c 的语法树：
+
/ \
a *
/ \
b c语法树的作用
- 结构表示：清晰地表示源代码的语法结构
- 语义分析基础：为语义分析提供结构化的输入
- 代码生成基础：为后续的代码生成提供基础
- 优化基础：为代码优化提供分析对象
- 错误定位：帮助精确定位语法错误的位置
抽象语法树（AST）
在实际编译器中，通常使用抽象语法树（Abstract Syntax Tree, AST），它是语法树的简化版本，去除了一些语法细节，更加专注于语义结构。
例如，表达式 a + b * c 的抽象语法树：
Add
/ \
a Mul
/ \
b c五、语法分析器的类型
根据分析方法的不同，语法分析器可以分为两大类：
1. 自顶向下分析（Top-Down Parsing）
- 基本思想：从语法的开始符号出发，逐步推导产生与输入 Token 序列匹配的结构
- 代表算法：
- 递归下降分析（Recursive Descent Parsing）
- LL(1) 分析
- 特点：实现简单，易于理解，适合手写
2. 自底向上分析（Bottom-Up Parsing）
- 基本思想：从输入 Token 序列出发，逐步归约为语法的开始符号
- 代表算法：
- 移进-归约分析（Shift-Reduce Parsing）
- LR 分析（包括 LR(0)、SLR(1)、LR(1)、LALR(1)）
- 特点：功能强大，能处理更多类型的文法，适合自动生成
六、代码示例：简单的语法分析器框架
下面是一个使用递归下降法实现的简单语法分析器框架，用于分析简单的算术表达式：
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def current_token(self):
if self.pos < len(self.tokens):
return self.tokens[self.pos]
return None
def eat(self, token_type):
if self.current_token() and self.current_token()[0] == token_type:
self.pos += 1
return True
return False
def factor(self):
"""分析因子：数字或括号包围的表达式"""
token = self.current_token()
if token and token[0] == 'NUMBER':
self.eat('NUMBER')
return {'type': 'NUMBER', 'value': token[1]}
elif token and token[0] == 'LPAREN':
self.eat('LPAREN')
node = self.expr()
if self.eat('RPAREN'):
return node
else:
raise SyntaxError("Missing closing parenthesis")
else:
raise SyntaxError(f"Unexpected token: {token}")
def term(self):
"""分析项：因子的乘除运算"""
node = self.factor()
while self.current_token() and self.current_token()[0] in ['MUL', 'DIV']:
token = self.current_token()
if token[0] == 'MUL':
self.eat('MUL')
node = {'type': 'MUL', 'left': node, 'right': self.factor()}
elif token[0] == 'DIV':
self.eat('DIV')
node = {'type': 'DIV', 'left': node, 'right': self.factor()}
return node
def expr(self):
"""分析表达式：项的加减运算"""
node = self.term()
while self.current_token() and self.current_token()[0] in ['ADD', 'SUB']:
token = self.current_token()
if token[0] == 'ADD':
self.eat('ADD')
node = {'type': 'ADD', 'left': node, 'right': self.term()}
elif token[0] == 'SUB':
self.eat('SUB')
node = {'type': 'SUB', 'left': node, 'right': self.term()}
return node
def parse(self):
"""开始分析"""
return self.expr()
# 测试
if __name__ == "__main__":
# 假设我们有一个 Token 序列
tokens = [
('NUMBER', 1),
('ADD', '+'),
('NUMBER', 2),
('MUL', '*'),
('NUMBER', 3)
]
parser = Parser(tokens)
try:
ast = parser.parse()
print("解析成功！")
print(ast)
except SyntaxError as e:
print(f"语法错误：{e}")七、自测题
- 语法分析器的主要任务是什么？
- 语法分析器在编译过程中的位置是什么？
- 什么是语法错误？请举例说明常见的语法错误。
- 语法树的作用是什么？
- 自顶向下分析和自底向上分析的区别是什么？
八、总结与展望
本集介绍了语法分析器的基本概念、任务、位置、语法错误处理以及语法树的作用。语法分析是编译过程中的重要环节，它将词法分析器生成的 Token 序列组织成有意义的结构，为后续的语义分析和代码生成奠定基础。
在接下来的几集中，我们将深入学习语法分析的具体方法和技术，包括：
- 上下文无关文法回顾
- 消除左递归
- 提取左公因子
- 递归下降分析器实现
- LL(1) 分析表构造
通过这些学习，我们将能够理解和实现各种语法分析器，为构建完整的编译器打下坚实的基础。
九、参考资料
- 《编译原理》（龙书）- Alfred V. Aho 等
- 《现代编译原理》（虎书）- Andrew W. Appel
- 《编译器设计》- Keith D. Cooper 等
- LLVM 项目文档