编译器的两种解析器

本文概述

• 自上而下的解析
• 自底向上解析

解析器是一种编译器, 用于将数据分解为来自词法分析阶段的较小元素。

解析器以令牌序列的形式获取输入, 并以解析树的形式生成输出。

解析有两种类型：自上而下的解析和自下而上的解析。

自上而下的解析

• 自上而下的解析称为递归解析或预测解析。
• 自下而上的解析用于为输入字符串构造一个解析树。
• 在自上而下的解析中, 解析从起始符号开始, 然后将其转换为输入符号。

输入字符串“ acdb”的解析树表示如下：

自底向上解析

• 自下而上的解析也称为移位减少解析。
• 自下而上的解析用于为输入字符串构造一个解析树。
• 在自下而上的解析中, 解析从输入符号开始, 然后通过反向找出最右边的字符串派生, 来构造解析树直至起始符号。

例

生产

E → T
T → T * F
T → id
F → T
F → id

输入字符串“ id * id”的解析树表示如下：

自下而上的解析分为各种解析。这些如下：

1. Shift-Reduce解析
2. 运算符优先级解析
3. 表驱动的LR解析

1. LR（1）
2. 单反相机（1）
3. CLR（1）
4. LALR（1）