为动态语言创建单独的"布尔表达式"规则

Question

我正在Bison中创建一个语法,用于简单的动态类型语言.我有一个"通用" expression规则,它有点类似于C中rvalue的概念; 表达式出现在赋值的右侧,它们也可以作为参数等发送给函数.规则的大大简化的版本如下:

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减少到a的事实有关的减少- 减少错误expression; 当解析器解析了一个booleanExpression,并且它遇到一个&&令牌时,它可以移位并继续前进,或者缩小为一个expression.甲booleanExpression需要减少到一个表达式,以允许代码如

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

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

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

1. 以这样一种方式构建规则,即尽管存在冲突,Bison仍然按照我的意愿行事,并忽略警告 - 相当丑陋和难以理解
2. 删除单独的booleanExpression规则并将其全部移动到expression- 好吧,但需要在语义分析阶段进行更多检查; 在我的语言中,字符串不能隐式转换为布尔值,因此代码if ("foo")不合法,但会被解析器接受
3. 使用GLR解析器 - 对于这样一个简单的用例感觉有点过分,但也许我错了

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

Answer 1

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

首先,正如你所看到的那样,即使有可能,它也会使语法复杂化.相比之下,类型检查规则在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称为"truthy"值.这可能非常方便,但如果强制性质的纬度太大,它也会有点危险.[注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 ')'

如果您认为上述内容过于复杂,那么请遵循传统观点,避免语法中出现语法错误.另一方面,如果您认为它具有说明性价值且您的语言是可接受的,那么请根据您的目的进行调整.

笔记:

1. 该方案不依赖于任何"truthy"强制的存在,但如果布尔值是第一类,则将存在只能在运行时确定为布尔值的表达式(布尔变量,返回布尔值的函数等).考虑运行时检查,布尔上下文中使用的值是一个布尔值,是一种强制转换true为真值的形式,其中只有true而且只有falsefalse,而所有其他值都会抛出错误.

   就个人而言,我喜欢有限的自动布尔强制.例如,如果文件对象处于错误状态,那么文件对象就是假的,或者如果容器是非空的,那么它就是真正的,这对我来说是完全合理的.将这些转换限制为显式布尔上下文,例如条件语句中的条件,使得我可以接受自动强制.但我不坚持这个想法; 如果你不喜欢它,请忽略这个想法.

2. 这不是一个很好的名字,但truthy_or_falsy_expr似乎太长了,boolish_expr似乎太奇怪了.欢迎提出建议.