移位归约分析

• 移位归约分析是将字符串归约为语法的起始符号的过程。
• 移位归约分析使用一个栈来保存语法，并使用一个输入带保存字符串。

• 移位归约分析执行两个动作：移位和归约。 这就是它被称为移位归约分析的原因。
  • 移位：此操作表示将输入指针移动到下一个输入符号，这称为移位符号。 在移位操作中，输入字符串中的当前符号被推入栈中。
  • 归约：在每次归约时，符号将被非终结符替换。 符号是产生式的右侧，而非终结符是产生式的左侧。

移位-归约分析中的基本操作

• 移位操作与将当前符号从输入缓冲区移动到栈相关。
• 当解析器知道句柄的右侧位于栈的顶部时，将应用归约操作到适用的产生式规则。
• 在执行移位和归约操作后，如果栈包含输入字符串的起始符号并且输入缓冲区为空，即包含 $ 符号，则认为输入字符串被接受。
• 如果解析器无法完成移位或归约操作，并且字符串也没有被接受，则称为错误条件。

移位归约解析器的运作方式

步骤1：最初，栈的顶部包含一个 $ 符号，输入缓冲区包含输入字符串，并在末尾带有一个 $ 符号。

步骤2：要执行移位-归约分析，将输入符号推到栈的顶部，直到句柄ß出现在栈的顶部。

步骤3：重复步骤1和步骤2，直到检测到错误或字符串被接受。

步骤4：最后，解析将成功完成。

示例 1

语法

将移位-归约分析应用于以下输入字符串

解决方案

创建解析表

示例 2

考虑以下语法

A → A + A

A -> A x A

A -> id

将移位-归约分析应用于以下输入字符串

id + id x id

解决方案

创建解析表

移位归约分析主要分为以下两类

1. 算符优先分析
2. LR-解析器

移位归约分析的优点

• 它可以解析各种编程语言。
• 它可以通过检测和处理错误来从错误中恢复。
• 它可以处理各种上下文无关文法。
• 它能够处理左递归和右递归文法。

移位归约分析的缺点

• 它很难解析歧义文法，对于给定的输入序列，存在多个可能的解析树。
• 在某些情况下，移位-归约分析产生的解析树可能比其他解析技术更复杂。

关于移位归约分析的常见问题

1. 列出移位-归约分析中执行的各种操作？

• 移位操作
• 归约操作
• 动作操作
• 错误操作

2. 移位-归约分析使用什么数据结构？

移位-归约分析使用堆栈数据结构来跟踪正在解析的符号。