Skip to content

Bison实现句尾的可选分号 Optional semicolon grammar in Bison

Jump to bottom
西风逍遥游 edited this page Nov 8, 2021 · 5 revisions

句尾分号在Bison中一直是一个让人非常困扰的问题，绝大部分复杂的语法中，如果在两个语句中间不插入分号，会导致严重的歧义。这也是编程语言设计中，为何一定要添加分号的原因。试想下面的两条语句

int a = call
(b);

如果看做一条语句，可以认为是一条调用语句，如果看成两条语句，可以认为是一个赋值加一个表达式计算。这个歧义在bison中是不能通过简单的词语法设计来弥补的，原因如下：

  1. 如果词法分析器永远输出'\n'， 则必须讨论语法中换号符是可选的，则在语法定义中一定会出现这种结构： expr : expr oplb '+' oplb expr 。在各种位置都添加上oplb表示一个可选的换行符，但这种语法本身同样带有大量歧义，产生的歧义数量甚至比不引入';'还要多。

  2. 如果词法分析器永远不输出'\n'，则语法上，上面的例子则永远不能被识别为两条语句，因为bison是贪婪匹配的，永远想移入更多的符号，则用户无法通过分行来实现对语句的切割。

最好的方案是，如果语句确定不需要';'时，词法分析器忽略换行符'\n'，而用户在某些语句结尾需要分割时却没有分号';'，自动检测我们是否遇到了一个换行符'\n'，遇到后将其视为一个分号。

普通的手工写的LL parser由于可以精细控制什么时候lookahead，往往可以采用简单的代码实现。例如：

int getNextToken(bool requireSemicolon) {
    int token = yylex();
    if (token == '\n') 
        if (requireSemicolon) return ';';
        else return getNextToken(false);
    return token;
}

这种逻辑简单易懂，需要分号时，参数设置为true即可，自动将下一个回车符合换成';' 发送给你，如果不是回车，那么说明用户不想在此分割，继续贪婪匹配更长的语句即可。

这篇帖子分析了一下如何用bison实现类似效果，不过可惜并没有用：https://stackoverflow.com/questions/10970699/parsing-optional-semicolon-at-statement-end 楼主提出了一个很有用的思想，在lexer处理换行符前设置一个flag就可以完成了，他有如下的语法：

stmt: expr end_of_stmt { ... }
;
end_of_stmt: ';'
    | '\n'
;

// new version 
stmt: expr { state = STATEMENT_END } ';' { ... }

可以发现，他在新的实现方法中给词法分析器设置了一个状态，如果在 STATEMENT_END 时，则将'\n'返回给parser，其余时间则自动丢弃。但我们会发现这有一个严重的问题，bison会lookahead一个token，也就是说，{ state = STATEMENT_END }这条语句一定会在 ';' 被识别后才会被执行，此时，已经没有机会把被跳过的'\n'换成分号了。

由于bison LALR（1）算法必须要lookahead，回答者指出，解决的思路是向前挪一个token, 但很明显，前面是expr，一般非常复杂，而且在expr中的语法根本没法确定当前是不是stmt的结尾。

另外一个思路是使用Error Recovery，就是先假设各种位置都没有';'，等到语法出错时，使用异常恢复手段，把丢失是分号插入回来： https://stackoverflow.com/questions/52512739/bison-error-recovery-for-automatic-semicolon-insertion

然后我们上面其实也讨论过，如果完全不输出分号，则用户用换行分割的两条语句会被识别为一条，无法实现换行分割语句的效果，并且如果一但有类似语句：

int a = call
(b)[10];

call有可能会和(b)结合，从而使得parser的状态转移到错误的状态上，给异常恢复增加了大量困难。

这篇帖子提出了纯用词法分析器来插入分号的方法：https://stackoverflow.com/questions/10826744/semicolon-insertion-ala-google-go-with-flex 然而我们发现，词法分析器的插入方法由于不包含语法分析器的状态，仅对拥有特定词法的语言有效，很可能你构建的语法会失效。

目前最为理想的可选分号的实现

在考察了众多不同实现思路后，我找出了一种非常理想的可选分号的实现方案，简单思路是，首先lexer输出所有的'\n'符号，在yylex调用时，为其增加一个过滤器，我们一旦发现了'\n'符号，那么就假设它是一个分号。如果使用';'可以使得当前自动机正常运转，那么就说明这个地方用户就是想插入一个分号，来分割我们的语句。如果这个分号的插入会让我们的自动机进入异常状态，那么说明\n应该被忽略，所有的自动机运转部分都必须是单独进行一下尝试，而不是在bison的自动机上真的执行，等确定分号是否插入后，再向bison返回我们最终确定的符号。

这里我们就添加了一个新的过滤器函数，将yychar - lookahead符号， yystate - 当前的自动机状态， yyssp - 当前的自动机栈都传入进来，我们会对自动机进行模拟运行，在确定自动机可以进行shift操作时，认为分号插入正确，在遇到异常时，则返回下一个非'\n'的token表示跳过当前这一系列的换行，说明目前不适合插入分号。

要注意，自动机必须执行到下一个shift操作时才能知道是否遇到了异常，如果只执行一步reduce，有可能会在更高层级的语法上报错。下面这段核心代码，实际上和Bison的核心下推自动机执行语句是等价的。

/* This filter will try to use ';' instead '\n' as the next token.
 * If the transition works without error, we will issue a ';' token,
 * Othervise we will ignore '\n' and produce the next token
 */

int yyfilter(int yychar, int yyn, int yystate, yy_state_t *yyssp) {
    if (yychar == '\n') {
        yysymbol_kind_t yytoken = YYTRANSLATE (';');

start:  yyn = yypact[yystate];
        if (yypact_value_is_default (yyn)) goto defact;
        yyn += yytoken;
        if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken) {
            /* default action */
defact:     yyn = yydefact[yystate];
            if (yyn == 0) { 
                /* return yylex(); */
                do yychar = yylex(); while (yychar == '\n'); 
                return yychar;
            }
            else goto reduce;
        } else { // table contains action
            yyn = yytable[yyn];
            if (yyn <= 0)
            {  // reduce case
                yyn = -yyn;
reduce:         yyssp -= yyr2[yyn];
                const int yylhs = yyr1[yyn] - YYNTOKENS;
                const int yyi = yypgoto[yylhs] + *yyssp;
                yystate = (0 <= yyi && yyi <= YYLAST && yycheck[yyi] == *yyssp
                        ? yytable[yyi]
                        : yydefgoto[yylhs]);
                yyssp++;
                goto start;
            } else { // shift case
                return ';'; 
            }
        }
        return ';';
    }
    return yychar;
}

Bison本身是不提供yyfilter这个函数接口的，他是直接自己调用了yylex,但由于bison支持自定义skeleton,可以把对yyfilter的调用手工写到我们使用的skeleton中, 找到b4_yylex这段对yylex的生成语句，在后面添加了yyfilter的调用：

      if (yypushed_loc)
        yylloc = *yypushed_loc;]])])], [[
      yychar = ]b4_yylex[;]])[
      yychar = yyfilter(yychar, yyn, yystate, yyssp);
    }

同时我们需要在parser.y中指定使用的skeleton，可以使用的相对目录是相对parser.y的位置而言的，这里只需要把完整的skeleton放到parser.y同目录下，并添加如下指令即可找到：

%skeleton "./bison.m4"

以上完整代码示例在本项目的optional-semicolon目录下： https://github.com/sunxfancy/flex-bison-examples/tree/master/optional-semicolon

Clone this wiki locally