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

Question

我正在 Bison 中为一种简单的动态类型语言创建语法。我有一个 "general" 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 这一事实相关的移位归约错误；当解析器解析了一个 booleanExpression 并且它遇到一个 && 标记时，它可以转移并继续前进，或者减少到一个 expression。 booleanExpression 需要简化为表达式以允许

之类的代码

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

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

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

以这样一种方式构建规则，尽管存在冲突，Bison 做我想做的，忽略警告——非常丑陋无法维护
删除单独的 booleanExpression 规则并移动全部到 expression - 好的，但需要更多检查语义分析阶段；在我的语言中，字符串不是隐含的可以转换为布尔值，所以像 if ("foo") 这样的代码是不合法的，但是将被解析器接受
使用 GLR 解析器 - 有点感觉对于这样一个简单的用例来说有点矫枉过正，但也许我错了

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

Answer 1

传统观点是：不要试图在语法中进行语义分析。

首先，它使语法复杂化，即使这是可能的，如您所见。相比之下，在遍历 AST 的树中执行时，类型检查规则非常简单。

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

但是，根据您的语言的确切性质，您可以选择一个中间立场。通常，一些运算符——布尔运算符和比较——肯定是 return 布尔值，而某些上下文肯定需要布尔值。所以你可以添加一个 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 ')'

但它确实对语言有一些限制。在上面介绍的最简单的化身中，布尔值只能在布尔上下文中使用，这可以防止布尔值成为 first-class 值。它们不能用作赋值的右侧或函数调用中的参数，例如，从上面的语法中可以清楚地看出。

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

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

在大多数语言中，可以根据定义的规则从其他值创建布尔值；按照惯例，转换为布尔值 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 ')'

如果您认为以上内容过于复杂，那么请遵循传统观点，避免在您的语法中散布语义。另一方面，如果您觉得它具有说明性价值并且您的语言可以接受这些限制，那么请根据您的目的对其进行调整。

备注：

该方案不依赖于任何“真实的”强制转换的存在，但如果布尔值是第一个class，就会有表达式只能确定为布尔值运行时间（布尔变量、函数 returning 布尔值等）。考虑运行时间检查布尔上下文中使用的值是否是布尔值，作为强制转换为真值的一种形式，其中只有 true 为真，只有 false 为假，而所有其他值都会引发错误。

就个人而言，我越来越喜欢有限的自动布尔强制转换。例如，如果文件对象处于错误状态，则文件对象为假，或者如果容器非空，则容器为真，这对我来说是完全合理的。将这些转换限制为明确的布尔上下文，例如条件语句中的条件，使我可以接受自动强制转换。但我并不坚持这个想法；不喜欢的请无视
这个名字不太好，但是truthy_or_falsy_expr好像太长了，boolish_expr也太奇怪了。欢迎提出建议。

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

Creating a separate "boolean expression" rule for a dynamic language

compiler-construction

grammar

parsing

bison

formal-languages

备注：