在 Lemon 中使用 midaction 规则来解释 "let" 表达式
Using midaction rules in Lemon to interpret "let" expression
我正在尝试使用 Flex + Lemon 编写一个 "toy" 解释器,它支持非常基本的 "let" 语法,其中变量 X 临时绑定到表达式。例如,"letx 3 + 4 in x + 8" 的计算结果应为 15。
本质上,我"like"要说的规则是:
expr(E) ::= LETX expr(N) IN expr(O). {
environment->X = N;
E = O;
}
但这行不通,因为 O
是在 X = N
赋值之前计算的。
我知道通常的解决方案是中间规则操作。 Lemon 没有明确支持这一点,但我在其他地方读到过,无论如何都是 syntactic sugar。
所以我尝试组合一个中间规则动作,在解释 O
:
之前完成我对 X = N
的赋值
midruleaction ::= /* mid rule */. { environment->X = N; }
expr(E) ::= LETX expr(N) IN midruleaction expr(O). { E = O; }
但这行不通,因为 midruleaction
规则无法访问 N
,或者至少 none 我可以在柠檬 docs/examples 中看到.
我想我在这里遗漏了一些东西。我知道我可以建一棵树,然后再走一遍。我可能最终会这样做,但我想先了解如何更直接地解决这个问题。
有什么建议吗?
在解析器中立即求值确实不是一个可扩展性很强的解决方案。见下文。
确实,中间规则动作(大部分)是语法糖。但是,在大多数情况下,它们不是 "markers"(右侧为空的非终结符)的语法糖,而是代表生产前缀的非终结符。例如,您可以这样编写 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。
我正在尝试使用 Flex + Lemon 编写一个 "toy" 解释器,它支持非常基本的 "let" 语法,其中变量 X 临时绑定到表达式。例如,"letx 3 + 4 in x + 8" 的计算结果应为 15。
本质上,我"like"要说的规则是:
expr(E) ::= LETX expr(N) IN expr(O). {
environment->X = N;
E = O;
}
但这行不通,因为 O
是在 X = N
赋值之前计算的。
我知道通常的解决方案是中间规则操作。 Lemon 没有明确支持这一点,但我在其他地方读到过,无论如何都是 syntactic sugar。
所以我尝试组合一个中间规则动作,在解释 O
:
X = N
的赋值
midruleaction ::= /* mid rule */. { environment->X = N; }
expr(E) ::= LETX expr(N) IN midruleaction expr(O). { E = O; }
但这行不通,因为 midruleaction
规则无法访问 N
,或者至少 none 我可以在柠檬 docs/examples 中看到.
我想我在这里遗漏了一些东西。我知道我可以建一棵树,然后再走一遍。我可能最终会这样做,但我想先了解如何更直接地解决这个问题。
有什么建议吗?
在解析器中立即求值确实不是一个可扩展性很强的解决方案。见下文。
确实,中间规则动作(大部分)是语法糖。但是,在大多数情况下,它们不是 "markers"(右侧为空的非终结符)的语法糖,而是代表生产前缀的非终结符。例如,您可以这样编写 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。