什么是 Shift Reduce 解析器？

Shift Reduce Parser 是一种自下而上的解析器。它生成从叶子到根的解析树。在 Shift Reduce Parser 中，输入字符串将被缩减为起始符号。这种减少可以通过反向处理最右边的推导来产生，即从起始符号到输入字符串。

Shift Reduce Parser 需要两个数据结构

• 输入缓冲器

• 堆

Shift Reduce Parsing 的各个步骤如下 -

Shift Reduce Parsing 的各个步骤如下 -

• 它使用堆栈和输入缓冲区。

• 将 $插入堆栈底部和 Input Buffer 中输入字符串的右端。

• Shift - 解析器将零个或多个输入符号移到堆栈上，直到句柄位于堆栈顶部。

• Reduce - 解析器将堆栈顶部的句柄减少或替换到生产的左侧，即生产的 RHS 被弹出，LHS 被推送。

• Accept - 将重复第 3 步和第 4 步，直到它检测到错误或直到堆栈包含开始符号 (S) 并且输入缓冲区为空，即它包含 $。

Example1 - 在语法上对给定字符串执行自下而上解析，即显示以下语法上字符串abbcde的缩减

S → a AB e

A → A bc | b

B → d

它可以通过在每一步反向应用最右边的推导，将字符串 abbcde 简化为起始符号 S。

Handle - 在上述过程中，左侧每次替换生产的右侧称为“减少”，每次替换称为“Handle”。

Example2 - 考虑语法

E → E + E 

E → E * E 

E → (E) 

E → 身份证

执行最右推导字符串 id ₁ + id ₂ * id ₃。在每个步骤中查找句柄。

每一步的处理

Example3 - 考虑以下语法

S → CC

C → cC

C → d

使用 Shift-Reduce 解析检查输入字符串“ccdd”是否被接受。

∴ 最后，Stack 包含起始符号 S，输入 Buffer 为空。它将接受字符串。