在 Lemon 中使用中间操作规则来解释"let"表达式

Question

我正在尝试使用Flex + Lemon编写一个"玩具"解释器，它支持非常基本的"let"语法，其中变量X临时绑定到表达式。例如，"letx 3 + 4 in x + 8"的值应该是15。

实际上，我想要的规则是:

expr(E) ::= LETX expr(N) IN expr(O). {
                                         environment->X = N;  
                                         E = O; 
                                     }

但是这不起作用，因为O是在X = N赋值之前求值的。

我理解通常的解决方案是一个中间规则的行动。Lemon并没有明确支持这一点，但我在其他地方读到过，这在任何情况下都只是语法糖。

所以我试着把一个中间规则动作放在一起，在解释O之前完成我对X = N的分配:

midruleaction ::=  /* mid rule */.                   { environment->X = N; }    
expr(E)  ::= LETX expr(N) IN midruleaction expr(O).  {  E = O; }

但是这不起作用，因为midruleaction规则没有办法访问N，或者至少我在柠檬文档/示例中看不到。

我想我遗漏了一些东西。我知道我可以造一棵树，然后再走一遍。我最终可能会这样做，但我想先了解如何更直接地解决这个问题。

有什么建议吗?

Answer 1

要在解析器中立即求值，这确实不是一个非常可扩展的解决方案。见下文.

确实，中间规则操作(大部分)是语法糖。然而，在大多数情况下，它们不是"标记"(右侧为空的非终结符)的语法糖，而是表示生产前缀的非终结符。例如，可以这样编写letx规则:

expr(E)     ::= letx_prefix IN expr(O). { E = O; }
letx_prefix ::= LETX expr(N).           { environment->X = N; }  

或者你可以这样做:

expr(E)       ::= LETX assigned_expr IN expr(O). { E = O; }
assigned_expr ::= expr(N).                       { environment->X = N; }

第一个是前缀脱糖;第二个是我要用的，因为我觉得它能更好地分离关注点。重要的一点是，environment->X = N;操作需要访问RHS前缀的语义值，因此它必须是前缀规则的一部分(至少包括需要其语义值的符号)，而不是标记，它根本不能访问任何语义值。

说了这么多，在解析过程中立即求值是一种非常有限的策略。它不能处理大量需要延迟求值的构造，比如循环和函数定义。它不能清晰地处理可能抑制求值的构造，例如条件和短路操作符。(这些可以使用mra和包含求值抑制标志的有状态环境来处理，但这非常难看。)

另一个问题是，在语法错误被发现之前，语法错误的表达式可能已经被部分求值了，用户可能无法立即看出表达式的哪些部分求值了，哪些部分没有求值。

总的来说，您最好在解析期间构建一个易于求值的AST，并在解析成功完成时求值AST。