Bison

Question

我正在使用 Bison 和 Flex 来尝试解析提供给我的简单语法。在这个语法中（几乎）所有东西都被认为是一个表达式并具有某种价值；没有声明。更重要的是，语法的 EBNF 定义带有某些歧义：

expression OP expression 其中 op 可能是 '+'、'-' '&' 等。这可以很容易地使用 bison 的关联运算符并根据通用语言标准设置 %left、%right 和 %nonassoc 来解决.
IF expression THEN expression [ELSE expression] 以及 DO expression WHILE expression，为此忽略了常见的悬空 else 问题，我想要以下行为：

In if-then-else as well as while expressions, the embedded expressions are taken to be as long as possible (allowed by the grammar). E.g 5 + if cond_expr then then_expr else 10 + 12 is equivalent to 5 + (if cond_expr then then_expr else (10 + 12)) and not 5 + (if cond_expr then then_expr else 10) + 12

鉴于语言中的一切都被认为是一个表达式，我找不到一种方法以不引起冲突的形式重写产生式规则。我尝试过的一件事是：

expression: long_expression
    | short_expression
    ;

long_expression: short_expression
    | IF long_expression THEN long_expression
    | IF long_expression long_expression ELSE long_expression
    | WHILE long_expression DO long_expression
    ;

short_expression: short_expression '+' short_expression
    | short_expression '-' short_expression
    ...
    ;

但这似乎不起作用，我不知道如何调整它才能工作。请注意，我（假设我）已经解决了悬空的 ELSE 问题，使用 nonassoc 的 ELSE 和 THEN 以及上面的结构，如某本书中所建议的，但我不确定这在没有语句而只有表达式的情况下是否有效。请注意，已为所有其他运算符（例如 +、- 等）设置关联性。是否有解决此问题的解决方案或提示或示例？

------------ 编辑：最小示例----------------

我试图包括所有具有特定关联性的标记的产生式，包括一些额外的产生式以显示一些语法。请注意，我实际上并没有使用上面解释的想法。另请注意，我包含了一个二元和一元运算符只是为了使代码更短一些，所有运算符的规则都是相同的形式。带有 -Wall 标志的 Bison 发现与这些声明没有冲突（但我很确定它们不是 100% 正确）。

%token<int> INT32 LET IF WHILE INTEGER OBJECTID TYPEID NEW
%right <str> THEN ELSE STR
%right '^' UMINUS NOT ISNULL ASSIGN DO IN
%left '+' '-'
%left '*' '/'
%left <str> AND '.'
%nonassoc '<' '='
%nonassoc <str> LOWEREQ
%type<ast_expr> expression
%type ... 

exprlist: expression { ; }  
    | exprlist ';' expression { ; };

block: '{' exprlist '}' { ; };

args: %empty { ; }
    | expression { ; }  
    | args ',' expression { ; };

expression: IF expression THEN expression { ; }
    | IF expression THEN expression ELSE expression { ; }
    | WHILE expression DO expression { ; }  
    | LET OBJECTID ':' type IN expression { ; }
    | NOT expression { /* UNARY OPERATORS */ ; }
    | expression '=' expression { /* BINARY OPERATORS */ ; }
    | OBJECTID '(' args ')' { ; }
    | expression '.' OBJECTID '(' args ')'  { ; }
    | NEW TYPEID { ; }
    | STR  { ; }
    | INTEGER { ; }
    | '(' ')' { ; }
    | '(' expression ')' { ; }
    | block { ; }
    ;

Answer 1

以下关联性声明解决了所有 shift/reduce 冲突并产生了预期的输出（至少在我能想到的所有测试中）：

...
%right <str> THEN ELSE
%right DO IN

%right ASSIGN
%left <str> AND
%right NOT
%nonassoc '<' '='  LOWEREQ
%left '+' '-'
%left '*' '/'
%right UMINUS ISNULL
%right '^'
%left '.'
...
%%
...
expression: IF expression THEN expression
    | IF expression THEN expression ELSE expression
    | WHILE expression DO expression
    | LET OBJECTID ':' type IN expression
    | LET OBJECTID ':' type ASSIGN expression IN expression
    | OBJECTID ASSIGN expression 
    ...
    | '-' expression %prec UMINUS 
    | expression '=' expression 
    ...
    | expression LOWEREQ expression
    | OBJECTID '(' args ')' 
    ...
...

请注意，所有符号的关联性声明顺序和优先级规则都很重要！我没有包含所有的产生式规则，但是 if-else-then、while-do、let in、一元和二元操作数是产生冲突或不同关联性声明的错误结果的规则。

Bison - 最长匹配表达式的产生式

Bison - Productions for longest matching expression

compiler-construction

grammar

parsing

ambiguity