在编译器设计中，移进规约分析的栈实现是什么？

移进规约分析器是一种自下而上的分析器。它使用一个栈来保存语法符号。分析器不断将输入符号移入栈中，直到栈顶出现句柄。当栈顶出现句柄时，它执行规约操作。

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

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

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

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

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

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

• 错误：发出语法错误发现信号，并调用错误恢复例程。

例如，考虑以下文法：

S → aAcBe
A → Ab|b
B → d

字符串为 abbcde。

它可以将此字符串规约为 S。它可以扫描字符串 abbcde，查找与某个产生式右部匹配的子串。子串 b 和 d 符合条件。

让我们选择最左边的 b 并将其替换为 A（产生式 A → b 的左部），得到字符串 aAbcde。可以识别 Ab、b 和 d 各自与某个产生式的右部连接。假设这次可以选择将子串 Ab 用 A（产生式 A → Ab 的左部）替换，可以得到 aAcde。

因此，将 d 替换为 B（产生式 B → d 的左部），可以得到 aAcBe。可以将此字符串替换为 S。上述过程中，将产生式的右部替换为左部的每个替换都称为规约。

移进规约分析的缺点

• 移进/规约冲突 − 有时，SR 分析器无法确定是移进还是规约。

• 规约/规约冲突 − 有时，分析器无法确定应该使用哪个产生式进行规约。

示例 − 为进行移进规约分析的栈实现，考虑以下文法：

E → E + E
E → E ∗ E
E → (E)
E → id

输入字符串为 $id_{1} + id_{2} * id_{3}$。

Ginni

更新于：2021年10月29日

6K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习