LR (0) Parsing Example
LR grammar is shift-reduction parser
⮚ L: left to right scanning
⮚ R: right-most reduction
⮚ LR (k): lookahead k input symbols
How to find a sentence to reduce
e.g. S→bBB
⮚ S→•bBB ←shift state: an input ‘b’ is expected. If it appears, shift b into stack
⮚ S→b•BB ← ready to be reduced state: after move ‘b’ to stack,
⮚ S→bB•B we expect to reduce B and B
⮚ S→bBB • ←reduction state: reduce BB to start symbol
当然可以！下面将详细解读**LR解析（LR Parsing）**的各个方面，包括其定义、核心概念以及如何在解析过程中进行移进和归约操作。我们将特别关注LR文法作为一种移进-归约解析器的特性，并通过具体的例子说明如何确定何时进行归约操作。
1. LR解析概述
LR解析是一种自底向上的解析方法，用于语法分析器（解析器）在编译过程中将输入的符号序列（通常是源代码）解析为语法树。LR解析器基于**移进（Shift）和归约（Reduce）**两种基本操作，通过逐步构建解析栈，最终将整个输入串归约为起始符号，验证其是否符合文法规则。
1.1 LR文法
LR文法是一类适用于LR解析器的无二义性的上下文无关文法。它的特点在于：
• 移进-归约解析器：LR解析器通过移进和归约操作处理输入串。
• 确定性：在任何给定的解析状态下，解析器可以唯一地决定下一步操作（移进或归约），保证解析过程的确定性和高效性。
1.2 LR解析器的分类
LR解析器根据其使用的前瞻符号数量（lookahead symbols）分类：
• LR(0)：不使用任何前瞻符号，仅根据当前状态决定操作。
• LR(1)：使用一个前瞻符号，基于当前符号和下一个符号做出决定。
• LR(k)：使用k个前瞻符号，通常用于处理更复杂的文法。
本文将重点讨论基本的LR解析器及其工作原理，特别是LR(0)的概念。
2. LR解析的核心组成
2.1 L: 从左到右扫描（Left to Right Scanning）
LR解析器从左到右扫描输入串，即从输入串的起始位置开始，逐步读取每一个符号，按照文法规则进行处理。
2.2 R: 右最导出归约（Right-most Reduction）
在每一步归约操作中，LR解析器选择右最导出（Right-most）的非终结符进行归约。这意味着解析器总是优先归约输入串中最右侧的可归约部分，确保解析过程的正确性和一致性。
2.3 LR(k): 前瞻k个输入符号（Lookahead k Input Symbols）
LR(k)解析器使用k个前瞻符号来帮助决定下一步的操作。前瞻符号是指在当前解析位置之后的k个输入符号。前瞻符号的使用增强了解析器的决策能力，减少解析冲突。
• LR(0)：k=0，不使用任何前瞻符号。
• LR(1)：k=1，使用一个前瞻符号。
• LR(k)：k>1，使用多个前瞻符号。
3. 移进（Shift）与归约（Reduce）操作
在LR解析过程中，解析器通过移进和归约两种操作逐步处理输入串，并将其归约为起始符号。
3.1 移进（Shift）
移进操作的含义是将输入缓冲区中的下一个符号读取并推入解析栈的顶部。这表示解析器已经接受了该符号，并准备将其纳入当前的归约过程。
• 作用：
• 扩展解析栈，增加新的符号以便进行进一步的归约。
• 移进操作通常在无法立即进行归约时执行。
3.2 归约（Reduce）
归约操作的含义是根据文法中的某个产生式，将解析栈顶部的一组符号序列替换为对应的非终结符。这表示解析器已经识别出一个符合某个产生式右侧的符号序列，可以将其简化为产生式的左侧符号。
• 作用：
• 合并符号序列，逐步构建语法树的高层结构。
• 归约操作用于确认并简化语法结构，验证输入串的合法性。
4. 如何决定何时进行归约
在LR解析中，决定何时进行归约是确保解析器正确性的关键。解析器需要根据当前解析状态和前瞻符号，判断是否可以执行归约操作。这一过程通常依赖于解析表（Parsing Table），其中包含了在不同状态下应执行的操作指令。
4.1 解析表的作用
解析表由两部分组成：
动作表（Action Table）：指示在当前状态和当前输入符号下，解析器应执行的操作（移进、归约、接受或错误）。
转移表（Goto Table）：指示在归约后，解析器应转移到的新状态。
4.2 决定归约规则
解析器在执行归约操作时，需要根据当前解析状态和前瞻符号，选择适当的产生式进行归约。具体步骤如下：
识别可归约序列：检查解析栈顶部的符号序列是否匹配某个产生式的右侧。
查找归约规则：根据当前状态和前瞻符号，查找解析表中的归约动作，确定应使用哪条产生式。
执行归约：将匹配的符号序列替换为产生式的左侧非终结符。
4.3 处理解析冲突
在某些情况下，解析器可能无法唯一地决定是执行移进还是归约操作，或者存在多条归约规则可供选择。这类问题称为解析冲突（Parsing Conflicts），主要包括：
• 移进-归约冲突（Shift-Reduce Conflict）：解析器无法决定是移进下一个符号还是归约当前符号序列。
• 归约-归约冲突（Reduce-Reduce Conflict）：解析器有多个归约规则可供选择，无法唯一决定应使用哪一条。
为了解决这些冲突，解析器设计者通常需要通过文法重构、明确操作符优先级和结合性，或者使用更强大的解析技术（如LR(1)）来消除二义性。
5. 如何确定归约的位置
确定何时对解析栈中的符号序列进行归约，是LR解析的核心。以下是确定归约位置的关键步骤：
5.1 项目表示法（Item Notation）
在LR解析中，文法的产生式通常用**项目（Item）**表示，项目中包含一个点（•）来标示已解析和待解析的部分。
• 表示形式：$A \rightarrow \alpha \cdot \beta$
其中，$A \rightarrow \alpha\beta$ 是一个产生式，点（•）表示当前解析位置。$\alpha$ 是已解析的部分，$\beta$ 是待解析的部分。
5.2 归约的标识
当一个项目的点（•）位于产生式的最右端时，表示该产生式的右侧部分已经全部匹配，可以执行归约操作。
• 归约标识：$A \rightarrow \alpha \cdot$
这表示可以将符号序列$\alpha$归约为非终结符$A$。
6. LR解析的具体步骤与示例
为了更清晰地理解上述概念，以下将通过一个具体的例子详细说明LR解析的过程，重点展示如何决定何时进行移进或归约操作。
6.1 示例文法
考虑以下文法：
$S \rightarrow bBB$
$B \rightarrow b$
$B \rightarrow b$
注：为了简化，规则2和规则3都定义了相同的产生式$B \rightarrow b$，可视为一个单一产生式。
6.2 输入句子
解析输入句子：bBB
6.3 解析过程详解
以下是逐步解析输入句子bBB的过程，重点展示解析栈的变化和决定何时进行移进或归约操作。
初始状态
• 解析栈：[]
• 输入缓冲区：b B B
• 动作：开始解析
步骤1：移进b
• 动作：Shift
• 解析栈：[b]
• 输入缓冲区：B B
步骤2：准备归约b为B
• 动作：根据解析表，识别b可以归约为B
• 解析栈：[B]
• 输入缓冲区：B B
步骤3：移进B
• 动作：Shift
• 解析栈：[B, B]
• 输入缓冲区：B
步骤4：移进B
• 动作：Shift
• 解析栈：[B, B, B]
• 输入缓冲区：[]（输入结束）
步骤5：准备归约B B B为bBB
• 动作：识别栈顶的B B B匹配产生式$S \rightarrow bBB$
• 解析栈：[S]
• 输入缓冲区：[]
步骤6：接受
• 动作：Accept
• 解析栈：[S]
• 输入缓冲区：[]
LR (0) Parsing
⮚ input buffer
⮚ a stack on which it keeps a list of states it has been in
⮚ an action table that tells it to what new state it should move
⮚ a goto table that tells it which grammar rule it should use given the state it is currently in and the terminal or non-terminal it has just read on the input stream
解读LR(0) 解析的工作流程
LR (0) Parsing