为动态语言创建单独的"boolean expression"规则

我正在用Bison为一种简单的动态类型语言创建语法。我有一个"一般"expression规则，这有点类似于 C 中的右值概念;表达式出现在赋值的右侧，它们也可以作为参数等发送到函数。该规则的简化版本如下：

constantExpression
: TOK_INTEGER_CONSTANT
| TOK_FLOAT_CONSTANT
| stringLiteral
;
expression
: constantExpression
| identifier
| booleanExpression
| booleanExpression TOK_QUESTION_MARK expression TOK_COLON expression
| TOK_LPAREN expression TOK_RPAREN
| expression TOK_PLUS expression
| expression TOK_MINUS expression
;

我还有一个专用的布尔表达式规则;布尔表达式在if语句中使用得最突出，但任何其他需要二进制真值的上下文当然也可以：

booleanExpression
: identifier
| expression '<' expression
| expression '<=' expression
| expression '==' expression
| expression '!=' expression
| expression '>' expression
| expression '>=' expression
| booleanExpression '&&' booleanExpression
| booleanExpression '||' booleanExpression
| '!' booleanExpression
| 'true'
| 'false'
;

问题在于：显然，上述规则存在大量的减少-减少冲突。根据上下文，标识符应简化为expression(例如，在诸如myVar2 = myVar1的语句中)或简化为booleanExpression(明显示例：if (myBoolVar))。

不仅如此，还存在与booleanExpresssion归约到expression相关的shift-reduce错误;当解析器解析了一个booleanExpression，并且它遇到一个&&令牌时，它可以移位并继续前进，或者归约到一个expression。booleanExpression需要简化为表达式以允许诸如

conditionVar = (var1 == 5) || (var2 > 10 && var3 < 20);
if (conditionVar) { ... }

我知道与运算符优先级相关的 shift-reduce 冲突，这不是问题，我已经使用运算符的%left规则修复了它。

我的问题：这个问题的最佳解决方案是什么？我的想法是

以

这样一种方式构建规则，尽管存在冲突，野牛做我想做的事，忽略警告 - 相当丑陋和不可维护
删除单独的booleanExpression规则并移动这一切都要expression- 好的，但需要在语义分析阶段;在我的语言中，字符串不是隐式的可转换为布尔值，因此像if ("foo")这样的代码是不合法的，但是将被解析器接受
使用 GLR 解析器 - 感觉有点对于如此简单的用例来说矫枉过正，但也许我错了

以上哪项是最好的主意？还有其他我没有考虑过的可能性吗？

传统智慧是：不要试图在你的语法中进行语义分析。

首先，它使语法复杂化，即使有可能，正如你所看到的。相比之下，在 AST 上的树上行走时，类型检查规则非常简单。

其次，这实际上是不可能的。由于您的语言是动态的，因此您实际上不知道任何变量的类型是什么。因此，编译时检查可能会导致三种情况，而不是两种情况：好、坏和未知。这在语法中会更加复杂，但在语义分析中只会稍微复杂一些。

但是，根据您的语言的确切性质，可以选择中间立场。通常，某些运算符(布尔运算符和比较)---绝对返回布尔值，而某些上下文肯定需要布尔值。因此，您可以添加一个boolean_expression非终端，用于指示结果肯定是布尔值的位置以及值必须是布尔值的位置。然后，您可以在语法中插入单个单元生产

boolean_expression: expression

具有将运行时检查节点插入 AST 的语义操作。

在语义分析期间，如果确定此检查始终成功，则可以消除此检查，如果确定此检查始终失败，则可以消除此检查。否则，最终将发出代码来执行检查。

此解决方案的优点是，语法随后显示需要布尔值的上下文，而不会受到完全强制要求所需的拜占庭式修改的影响。

(在下面的示例中，我只显示一个布尔运算符、一个比较运算符和一个算术运算符。显然，真正的语言会有更多的每个，但它根本不会改变呈现方式。我也没有打扰序言，它必须包括运算符的优先声明。

program : stmt_list
stmt_list:%empty
| stmt_list stmt
stmt    : assign
| call
| empty
| while
| '{' stmt_list '}'
assign  : IDENTIFIER '=' expr ';'
call    : expr '(' expr_list ')' ';'
| expr '(' ')' ';'
empty   : ';'
while   : "while" '(' boolean_expr ')' stmt
expr_list
: expr
| expr_list ',' expr
boolean_expr
: boolean_term
| boolean_expr "or" boolean_expr
| expr '<' expr
boolean_term
: "true" | "false"
| expr               { /* insert conversion from expr to boolean */ }
expr    : term
| expr '+' expr
term    : INTEGER
| IDENTIFIER
| '(' expr ')'

但它确实对语言施加了一些限制。在上面介绍的最简单的化身中，除了在布尔上下文中之外，永远不能使用布尔值，这会阻止布尔值成为一等值。例如，它们不能用作赋值的右侧或函数调用中的参数，从上面的语法中可以清楚地看出。

此外，上述语法不允许在布尔表达式周围使用多余的括号。

这不是很令人满意，但是我们可以通过将布尔结果与布尔值分开来做得更好，但代价是语法略有复杂。

在大多数语言中，布尔值可以根据其他值的定义规则创建;按照惯例，转换为布尔true的值称为"真"值。这可能非常方便，但如果胁迫的性质有太多的自由度，也可能有点危险。[注1]为了控制损害，我们可能只允许在显式布尔上下文中自动强制布尔值，而永远不允许布尔值自动强制转换为非布尔值。如果您愿意接受这些限制，那么我们仍然可以使用语法作为记录布尔上下文和强制的工具。

在下文中，我们介绍四个非终端，它们都代表了某种表达的味道：

expr：非布尔表达式
boolean_expr：一个特定的布尔表达式;相应的产品列出了必须具有布尔结果的语法。

truthy_expr

表达式或非布尔表达式，可以强制转换为布尔表达式。此非终端用于需要布尔值的地方。[注2]
either_expr：布尔表达式或非布尔表达式，在上下文中可能没有强制出现(例如赋值和函数参数)。

请注意，最后两个非终端具有完全相同的制作，但语义非常不同(因此语义操作也不同)。由于它们可能出现的上下文是不连续的，因此不会产生冲突。

除了上述非终端的定义及其在各种上下文中的使用外，语法没有太大变化：

program : stmt_list
stmt_list:%empty
| stmt_list stmt
stmt    : assign
| call
| empty
| while
| '{' stmt_list '}'
assign  : IDENTIFIER '=' either_expr ';'
call    : expr '(' expr_list ')' ';'
| expr '(' ')' ';'
empty   : ';'
while   : "while" '(' truthy_expr ')' stmt
expr_list
: either_expr
| expr_list ',' either_expr
truthy_expr
: boolean_expr
| expr               { /* insert conversion from expr to boolean */ }
either_expr
: boolean_expr
| expr
boolean_expr
: boolean_term
| truthy_expr "or" truthy_expr
| expr '<' expr
boolean_term
: "true"
| "false"
| '(' boolean_expr ')'
expr    : term
| expr '+' expr
term    : INTEGER
| IDENTIFIER
| '(' expr ')'

如果您认为上述内容太复杂，请遵循传统智慧，避免在语法中穿插语义。另一方面，如果您觉得它具有说明性价值，并且您的语言可以接受限制，那么请使其适应您的目的。

<小时 />

注释：

该方案不依赖于任何"真实"强制的存在，但如果布尔值是第一类，则存在只能在运行时确定为布尔值的表达式(布尔变量、返回布尔值的函数等)。考虑运行时检查，布尔上下文中使用的值是否为布尔值，这是一种强制进入真实性的形式，其中只有true为真，只有false为假，而所有其他值都引发错误。
就我个人而言，我越来越喜欢有限的自动布尔强制。例如，如果文件对象处于错误状态，则文件对象是伪造的，或者如果容器为非空，则容器是真实的，这对我来说是完全有意义的。将这些转换限制为显式布尔上下文，例如条件语句中的条件，使自动强制对我来说是可以接受的。但我不坚持这个想法;如果你不喜欢它，忽略这个想法。
这不是一个很好的名字，但truthy_or_falsy_expr似乎太长了，boolish_expr似乎太奇怪了。欢迎提出建议。

注释：

相关内容

最新更新

热门标签：