这一节主要介绍另一种解析器，自底向上解析器。以及相关的LR(1)语法。

自底向上解析器

自底向上解析器（Bottom-up parser）是一种从输入符号开始，逐步构建语法树的解析方法。它的主要特点包括：

1. 从输入符号开始，逐步归约到起始符号
2. 使用移进-归约（shift-reduce）策略
3. 能够处理更广泛的语法形式
4. 通常使用栈来保存中间状态

自底向上解析器的工作过程：

1. 将输入符号移入栈中
2. 当栈顶符号序列与某个产生式的右部匹配时，进行归约
3. 重复上述过程，直到归约到起始符号

常见的自底向上解析器包括：

• LR(0)解析器
• SLR(1)解析器：简单LR解析器（Simple LR Parser），是LR(0)解析器的改进版本。它使用LR(0)项集，但通过查看下一个输入符号（lookahead）来减少冲突。SLR(1)解析器比LR(0)更强大，但比LR(1)解析器简单。
• LR(1)解析器：LR(1)解析器是LR(0)解析器的扩展，它使用LR(0)项集，并通过查看下一个输入符号（lookahead）来减少冲突。LR(1)解析器比SLR(1)解析器更强大，但比LR(0)解析器复杂。

LR(1)语法

LR(k)语法是指：
L-means"left-to-right'’ scan of input
L-meanss "Reverse rightmost derivation"
k-means“predict based on k tokens of lookahead"

LR(1)语法是一种自底向上的语法分析方法，采用从左到右扫描输入、最右推导的逆过程，并且只向前查看1个符号。

LR解析样例

考虑以下简单语法：

1. S → E
2. E → E + T
3. E → T
4. T → id

输入字符串：id + id

解析过程：

栈	输入	动作
0	id + id $	移进
0 id	+ id $	归约 T → id
0 T	+ id $	归约 E → T
0 E	+ id $	移进
0 E +	id $	移进
0 E + id	$	归约 T → id
0 E + T	$	归约 E → E + T
0 E	$	接受

解析成功，输入字符串符合语法规则。 下一节会介绍如何构造LR(1)解析表。来决定进行规约还是移进。

更新日志

2025/1/12 02:51

查看所有更新日志

• 578c3-更新自底向上和LR(1)语法于 2025/1/12