实现try-catch-finally语法时如何解决bison shift/reduce？

Question

我正在尝试用我的玩具语言 Bison 实现 try-catch-finally 表达式。

另一件事是，受 Scala grammar 的启发，try-catch-finally 中的项目是一个表达式，而不是块语句。

这是 grammar.y:

%code top {
#include <cstdio>
}

%union {
    int n;
    Ast *ast;
}

%code requires {
class Ast;
int yylex(void);
void yyerror(const char *msg);
}

%token<n> NUM
%token<n> PLUS '+'
%token<n> MINUS '-'
%token<n> TIMES '*'
%token<n> DIVIDE '/'
%token<n> SEMICOLON ';'
%token<n> NEWLINE '\n'
%token<n> IF "if"
%token<n> ELSE "else"
%token<n> TRY "try"
%token<n> CATCH "catch"
%token<n> FINALLY "finally"
%token<n> LPAREN '('
%token<n> RPAREN ')'

%type<ast> prog expr primaryExpr

/* grammar precedence */
%nonassoc "try_catch" /* lower than finally */
%nonassoc "try_catch_finally"

/* operator precedence is higher than grammar precedence (try-catch-finally) */
%left PLUS MINUS
%left TIMES DIVIDE


%start prog

%%

prog : expr
     ;

expr : "try" expr "catch" expr %prec "try_catch" { $$ = nullptr; }
     | "try" expr "catch" expr "finally" expr %prec "try_catch_finally" { $$ = nullptr; }
     | primaryExpr
     ;

primaryExpr : NUM { $$ = nullptr; }
            | primaryExpr '+' NUM { $$ = nullptr; }
            | primaryExpr '-' NUM { $$ = nullptr; }
            | primaryExpr '*' NUM { $$ = nullptr; }
            | primaryExpr '/' NUM { $$ = nullptr; }
            ;

%%

void yyerror(const char *msg) {
    fprintf(stderr, "%s\n", msg);
}

正在生成文件：bison --debug --verbose -Wcounterexamples -o grammar.tab.cpp --defines=grammar.tab.h grammar.y，我们有一个具有 shift/reduce 冲突的 grammar.output 文件：

Terminals unused in grammar

    PLUS
    MINUS
    TIMES
    DIVIDE
    SEMICOLON
    ';'
    NEWLINE
    '\n'
    "if"
    "else"
    LPAREN
    '('
    RPAREN
    ')'


State 17 conflicts: 1 shift/reduce


Grammar

    0 $accept: prog $end

    1 prog: expr

    2 expr: "try" expr "catch" expr
    3     | "try" expr "catch" expr "finally" expr
    4     | primaryExpr

    5 primaryExpr: NUM
    6            | primaryExpr '+' NUM
    7            | primaryExpr '-' NUM
    8            | primaryExpr '*' NUM
    9            | primaryExpr '/' NUM


Terminals, with rules where they appear

    $end (0) 0
    '\n' <n> (10)
    '(' <n> (40)
    ')' <n> (41)
    '*' <n> (42) 8
    '+' <n> (43) 6
    '-' <n> (45) 7
    '/' <n> (47) 9
    ';' <n> (59)
    error (256)
    NUM <n> (258) 5 6 7 8 9
    PLUS <n> (259)
    MINUS <n> (260)
    TIMES <n> (261)
    DIVIDE <n> (262)
    SEMICOLON <n> (263)
    NEWLINE <n> (264)
    "if" <n> (265)
    "else" <n> (266)
    "try" <n> (267) 2 3
    "catch" <n> (268) 2 3
    "finally" <n> (269) 3
    LPAREN <n> (270)
    RPAREN <n> (271)
    "try_catch" (272)
    "try_catch_finally" (273)


Nonterminals, with rules where they appear

    $accept (27)
        on left: 0
    prog <ast> (28)
        on left: 1
        on right: 0
    expr <ast> (29)
        on left: 2 3 4
        on right: 1 2 3
    primaryExpr <ast> (30)
        on left: 5 6 7 8 9
        on right: 4 6 7 8 9


State 0

    0 $accept: • prog $end

    NUM    shift, and go to state 1
    "try"  shift, and go to state 2

    prog         go to state 3
    expr         go to state 4
    primaryExpr  go to state 5


State 1

    5 primaryExpr: NUM •

    $default  reduce using rule 5 (primaryExpr)


State 2

    2 expr: "try" • expr "catch" expr
    3     | "try" • expr "catch" expr "finally" expr

    NUM    shift, and go to state 1
    "try"  shift, and go to state 2

    expr         go to state 6
    primaryExpr  go to state 5


State 3

    0 $accept: prog • $end

    $end  shift, and go to state 7


State 4

    1 prog: expr •

    $default  reduce using rule 1 (prog)


State 5

    4 expr: primaryExpr •
    6 primaryExpr: primaryExpr • '+' NUM
    7            | primaryExpr • '-' NUM
    8            | primaryExpr • '*' NUM
    9            | primaryExpr • '/' NUM

    '+'  shift, and go to state 8
    '-'  shift, and go to state 9
    '*'  shift, and go to state 10
    '/'  shift, and go to state 11

    $default  reduce using rule 4 (expr)


State 6

    2 expr: "try" expr • "catch" expr
    3     | "try" expr • "catch" expr "finally" expr

    "catch"  shift, and go to state 12


State 7

    0 $accept: prog $end •

    $default  accept


State 8

    6 primaryExpr: primaryExpr '+' • NUM

    NUM  shift, and go to state 13


State 9

    7 primaryExpr: primaryExpr '-' • NUM

    NUM  shift, and go to state 14


State 10

    8 primaryExpr: primaryExpr '*' • NUM

    NUM  shift, and go to state 15


State 11

    9 primaryExpr: primaryExpr '/' • NUM

    NUM  shift, and go to state 16


State 12

    2 expr: "try" expr "catch" • expr
    3     | "try" expr "catch" • expr "finally" expr

    NUM    shift, and go to state 1
    "try"  shift, and go to state 2

    expr         go to state 17
    primaryExpr  go to state 5


State 13

    6 primaryExpr: primaryExpr '+' NUM •

    $default  reduce using rule 6 (primaryExpr)


State 14

    7 primaryExpr: primaryExpr '-' NUM •

    $default  reduce using rule 7 (primaryExpr)


State 15

    8 primaryExpr: primaryExpr '*' NUM •

    $default  reduce using rule 8 (primaryExpr)


State 16

    9 primaryExpr: primaryExpr '/' NUM •

    $default  reduce using rule 9 (primaryExpr)


State 17

    2 expr: "try" expr "catch" expr •
    3     | "try" expr "catch" expr • "finally" expr

    "finally"  shift, and go to state 18

    "finally"  [reduce using rule 2 (expr)]
    $default   reduce using rule 2 (expr)

    shift/reduce conflict on token "finally":
        2 expr: "try" expr "catch" expr •
        3 expr: "try" expr "catch" expr • "finally" expr
      Example: "try" expr "catch" "try" expr "catch" expr • "finally" expr
      Shift derivation
        expr
        ↳ "try" expr "catch" expr
                             ↳ "try" expr "catch" expr • "finally" expr
      Reduce derivation
        expr
        ↳ "try" expr "catch" expr                        "finally" expr
                             ↳ "try" expr "catch" expr •



State 18

    3 expr: "try" expr "catch" expr "finally" • expr

    NUM    shift, and go to state 1
    "try"  shift, and go to state 2

    expr         go to state 19
    primaryExpr  go to state 5


State 19

    3 expr: "try" expr "catch" expr "finally" expr •

    $default  reduce using rule 3 (expr)

让我们关注冲突部分：

State 17

    2 expr: "try" expr "catch" expr •
    3     | "try" expr "catch" expr • "finally" expr

    "finally"  shift, and go to state 18

    "finally"  [reduce using rule 2 (expr)]
    $default   reduce using rule 2 (expr)

    shift/reduce conflict on token "finally":
        2 expr: "try" expr "catch" expr •
        3 expr: "try" expr "catch" expr • "finally" expr
      Example: "try" expr "catch" "try" expr "catch" expr • "finally" expr
      Shift derivation
        expr
        ↳ "try" expr "catch" expr
                             ↳ "try" expr "catch" expr • "finally" expr
      Reduce derivation
        expr
        ↳ "try" expr "catch" expr                        "finally" expr
                             ↳ "try" expr "catch" expr •

对于 "try" expr "catch" "try" expr "catch" expr "finally" expr，在默认 reduce 中，"finally" 绑定到第一个 "try" 而不是第二个 "try"。我认为这与 Java/Scala 行为不同。

并且我尝试用%prec调整优先级来解决，但是失败了

我该如何解决这个问题？

Answer 1

如注释中所示，try – catch – finally 语句中的可选 finally 子句造成的 shift-reduce 冲突与中的可选 else 子句完全相同if – then – else 语句，so-called“悬而未决的其他”。

因为“最终悬挂”与“悬挂其他”是同一个问题，我们可以预期解决方案是相同的。在解决方案中，最简单的是使用优先级声明，其中最简单的是

%right "if" "else" "catch" "finally"

将这些令牌（以及因此，最后终端是这些令牌之一的产品）声明为 %right 意味着当涉及这些令牌之一的冲突发生时，shift 应选择操作。由于这是 bison 的默认冲突解决方案（见注释 2），该优先级声明的唯一作用是抑制有关冲突的警告消息。

已编辑问题中的 over-engineered 解决方案也可以使用，但我会警告不要不必要地使用 %nonassoc。 [注1] 但是，仅添加注释是不够的：

%nonassoc "try_catch" /* lower than finally */

您实际上还需要添加声明

%right finally

上面显示的优先解决方案的优点是self-contained。它不仅不依赖于其他优先级声明，也不依赖于 %prec 声明，后者也很容易被意外省略。

虽然与如何解决问题的问题没有特别的关系，但值得注意的是你误解了bison的报告输出。 Bison 将状态 17 中的状态转换报告为：

    "finally"  shift, and go to state 18

    "finally"  [reduce using rule 2 (expr)]
    $default   reduce using rule 2 (expr)

应该这样理解：

当"finally"是前瞻时，转移前瞻令牌并转到状态18。
前瞻标记 "finally" 也存在冲突操作：reduce 至 expr 使用规则 2。此操作已被冲突解决算法 [注 2] 消除。（Bison 将动作放在括号中（[reduce using rule 2 (expr)] 表示该动作已被冲突解决消除。）
对于所有其他先行标记 ($default)，将减少到expr使用规则 2.

请注意，Bison 不会报告被优先声明消除的解析操作。那些被默默地丢弃了。

备注

如果要在不指定关联性的情况下声明优先关系，请使用%precedence。与 %nonassoc 不同，它不会默默地隐藏语法错误。
默认的冲突解决算法是：
- 如果有shift动作，就用吧。（永远不会有超过一种可能的转变。）
- 如果没有shift动作，则使用规则号最小的reduce动作；即语法文件中排在第一位的那个。

实现try-catch-finally语法时如何解决bison shift/reduce？

How to solve bison shift/reduce when implementing try-catch-finally grammar?

c

parsing

scala

bison

备注