时间戳

首页 > 解决方案 > 实现try-catch-finally语法时如何解决bison shift/reduce？

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

问题描述

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

还有一件事是，受Scala 语法的启发，try-catch-finally 中的 item 是一个表达式，而不是块语句。

这是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，我们有一个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"绑定到第 1"try"个而不是第 2 个"try"。我认为这与 Java/Scala 行为不同。

我尝试使用%prec调整优先级来解决它，但失败了。

我应该如何解决这个问题？

标签： cscalaparsingbison

解决方案

正如评论中所指出的，语句中的可选finally子句造成的移位减少冲突与语句中的可选子句try – catch – finally完全相同，即所谓的“悬空 else”。elseif – then – else

由于“最终悬空”与“悬空 else”是同一个问题，我们可以预期解决方案是相同的。在这些解决方案中，最简单的是使用优先声明，其中最简单的是

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

将这些标记（因此，最后一个终端是这些标记之一的产生式）声明为%right意味着当涉及这些标记之一的冲突出现时，应该选择移位动作。由于这是 bison 的默认冲突解决方案（见注 2），该优先级声明的唯一效果是抑制有关冲突的警告消息。

已编辑问题中过度设计的解决方案也可以使用，尽管我会警告不要不必要地使用%nonassoc. [注 1] 但是，仅添加注释是不够的：

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

您实际上还需要添加声明

%right finally

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

尽管它与如何解决问题的问题并不特别相关，但值得注意的是，您误解了 bison 的报告输出。Bison 将状态 17 中的状态转换报告为：

    "finally"  shift, and go to state 18

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

这应该读作如下：

  1. 何时"finally"是前瞻，移动前瞻令牌并转到状态 18。

  2. 前瞻令牌还有一个冲突操作"finally"：减少到expr使用规则 2。冲突解决算法消除了此操作 [注 2]。（Bison 将动作放在括号中（[reduce using rule 2 (expr)]表示该动作已通过解决冲突消除。）

  3. 对于所有其他前瞻标记 ( $default)，减少到expr使用规则 2。

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

笔记

  1. 如果要声明优先关系而不指定关联性，请使用%precedence. 不同%nonassoc的是，它不会默默地隐藏语法错误。

  2. 默认的冲突解决算法是：

    • 如果有换档动作，请使用它。（永远不会有超过一种可能的转变。）
    • 如果没有 shift 动作，则使用规则编号最小的 reduce 动作；也就是说，在语法文件中最先出现的那个。

推荐阅读