什么是 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 1 + id 2 * id 3。在每个步骤中查找句柄。

每一步的处理

右句子形式
处理
生产使用
id1 + id2 * id3
编号1
E → id1
E + 身份证2 * 身份证3
编号2
E → id2
E + E * id 3
编号3
E → id3
E + E * E
E * E
E → E ∗ E
E + E
E + E
E → E + E



Example3 - 考虑以下语法

S → CC

C → cC

C → d

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


输入字符串
行动
$
ccdd$   Shift
$c
光盘$   Shift
$cc
dd$   Shift
$CCD
d$   Reduce by C → id
$抄送
d$   Reduce by C → cC
$cc
d$   Reduce by C → cC
$C
d$   Shift
$镉
$   Reduce by C → d
$CC
$   Reduce by S → CC
$S
$    接受

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

以上是 什么是 Shift Reduce 解析器? 的全部内容, 来源链接: utcz.com/z/363393.html

回到顶部