什么是移进规约分析器？

移进规约分析器是一种自底向上的分析器。它从叶子节点生成语法树到根节点。在移进规约分析器中，输入字符串将被规约到起始符号。这种规约可以通过反向处理最右推导来产生，即从起始符号到输入字符串。

移进规约分析器需要两种数据结构

  • 输入缓冲区
  • 栈

移进规约分析的步骤如下：

移进规约分析的步骤如下：

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

  • 在栈的底部和输入缓冲区输入字符串的右端插入$。

  • 移进 - 分析器将零个或多个输入符号移入栈，直到句柄位于栈顶。

  • 规约 - 分析器规约或替换栈顶的句柄为产生式的左部，即弹出产生式的右部，并压入左部。

  • 接受 - 重复步骤 3 和步骤 4，直到检测到错误或栈包含起始符号 (S) 且输入缓冲区为空，即包含$。

示例 1 - 对给定字符串和语法执行自底向上分析，即显示以下语法中字符串 abbcde 的规约

S → a A B e

A → A b c | b

B → d

它可以通过在每一步应用最右推导的反向将字符串 abbcde 规约到起始符号 S。

句柄 - 在上述过程中，用左部替换产生式的右部被称为“规约”，每次替换被称为“句柄”。

示例 2 - 考虑以下语法

E → E + E 

E → E * E 

E → (E) 

E → id

执行最右推导字符串 id1 + id2 * id3。在每一步找到句柄。

每一步的句柄

右句型
句柄
使用的产生式
id1 + id2 * id3
id1
E → id1
E + id2 * id3
id2
E → id2
E + E * id3
id3
E → id3
E + E * E
E * E
E → E ∗ E
E + E
E + E
E → E + E
E


示例 3 - 考虑以下语法

S → CC

C → cC

C → d

使用移进规约分析检查输入字符串“ccdd”是否被接受。

栈
输入字符串
动作
$
ccdd$
   移进
$ c
cdd$
   移进
$ cc
dd$
   移进
$ ccd
d$
   根据 C → id 规约
$ ccC
d$
   根据 C → cC 规约
$cC
d$
   根据 C → cC 规约
$C
d$
   移进
$Cd
$
   根据 C → d 规约
$CC
$
   根据 S → CC 规约
$S
$
   接受

∴ 最后，栈包含起始符号 S，输入缓冲区为空。它将接受该字符串。

更新于： 2021年11月2日

12K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告