从语法器中删除左记录时如何修改语义动作

Question

是否有任何算法告诉我们如何修改与左获取语法相关的语义动作？例如，我们有以下语法及其相关的语义动作：

$ s rightarrow id = expr $ {ss = expr.size}

s $ rightarrow $如果expr，则$ s_1 $ else $ s_2 $ {$ s_1.t = st + 2; $ $ s_2.t = st + 2; $ $ ss = expr.size + s_1.size + s_2.size + 2; $}

s $ rightarrow $而expr do $ s_1 $ {$ s_1.t = st + 4; $ $ ss = expr.size + s_1.s + 1; $}

s $ rightarrow $ $ $ s_1 $; $ s_2 $ {$ s_1.t = s_2.t = st; $ $ ss = s_1.s + s_2.s; $}

显然，语法的非恢复版本是：

s $ rightarrow $ id = expr t t

s $ rightarrow $如果Expr，则$ s_1 $ else $ s_2 $ t

s $ rightarrow $，而expr do $ s_1 $ t

t $ rightarrow $; $ s_2 $ t

t $ rightarrow $ $ epsilon $

但是我们还需要相应地改变语义动作。有什么想法如何完成？

Answer 1

从我发现的东西来看，没有一般技术可以在删除左记录时修改语义动作。取而代之的是，最好的方法是以代表性的示例，绘制解析树，然后检查哪些语义动作给我们带来与以前的语法相同的结果。

Answer 2

我有一个部分解决方案（我正在寻找一般解决方案）。如果您的语法没有Epsilon的作品，则没有非终端是无效的。这意味着要删除左递归的算法经过（尽管它引入了Epsilon Productions）。

如果添加表单操作的语义动作（标签，计数），以识别空字符串，并使用Shift/降低解析器并检查所有**替代方案，则根本不需要重新组织解析树。解析时，如果识别终端，则将属性推到解析器堆栈上，这是一个换档动作。当遇到操作时，它会从堆栈中弹出n个值，并用指定的标签推出一个节点，并在儿童的情况下以相反的方式从堆栈中弹出。这是减少动作。

解析器必须传播当前的位置和解析器堆栈，而换档和减少的操作应使用功能更新而不是突变进行。然后清楚地比重构语法不会改变移动的顺序并减少动作，因此所得的解析树在重构下是不变的。

这意味着，如果您生成AST而不是解析树，则必须按数字参考属性。机械之所以起作用，是因为解析器堆栈和控制堆栈被解耦，并且重构仅会更改控制堆栈。困难是，语法最初必须没有epsilon，因为减少动作术语本身是无效的。

**对所有替代方案进行了检查，以使考虑顺序无关紧要。尽管重构产生同等语法，但没有自动保证，除非检查所有可能性，否则所得的解析树将是相同的。在这种情况下，订购仍然不确定，但结果集将相等。