LALR(1) shift/reduce 错误使用 % 作为百分比和 mod

Question

我开始了一个项目，其中的语法使用 %（和单词 mod）作为 modulus 运算符，现在我想添加 %作为尾部一元运算符除以 100。

一些注意事项，我不使用基于 C 的语言，我使用 bison 的 XML 输出实现了我自己的 tokenizer/compiler。我选择的步骤对我的实施至关重要。

有没有一种方法可以让我的语法在 LALR(1) 编译器中编译时没有任何 shift/reduce 错误？

基本上以下说法都是有效的：

5% -> 0.05
5%%5 -> 0.05 mod 5
5%%%5 -> 0.0005 mod 5 等等

我只是不知道如何将其表达为我的语法：

%token S_NUM

%%

default: mod_term ;

mod_term: _mod_value
    | percent_term ;

_mod_value: mod_term O_PERCENT percent_term ;

percent_term: _percent_value
    | value ;

_percent_value: value O_PERCENT ;

value: S_NUM ;

%%

我也是用下面的语句编译的： bison -v --report=all --warnings=no-other -Werror=conflicts-sr --xml test.y -o test.y.xml

（由于我的环境，我强制 shift/reduce 作为错误）

有什么想法吗？我玩过 %left 和 %right 说明符，但没有运气。

Answer 1

如果您愿意接受解析器复杂性的增加，您始终可以通过添加 %glr-parser 指令将其变成 GLR 解析器。这意味着解析器在到达冲突点时将拆分并探索这两个状态，然后一旦它处理了足够的标记，它将删除无法解析的状态。不过，这确实需要足够新的 bison 版本。然而，就像其他人建议的那样，重新设计语言可能会更好。鉴于 Bison 对 GLR 解析器的现有限制，使用 GLR 解析器意味着您可能最终会使用连续百分比数量的指数数量的内存。

Answer 2

这里的歧义在于 '%' 是后缀运算符还是中缀运算符。这与 '-' 既是前缀运算符又是中缀运算符的常见表达式解析器问题非常相似，您可以使用显式 %prec 指令以相同的方式解决它。传统的写法是：

%left '%'            /* left-associative infix operator */
%nonassoc POSTFIX    /* postfix operations are higher precedence */
%token VAL
%%

expr: expr '%' expr
    | expr '%' %prec POSTFIX
    | VAL
    ;

使用优先级来解决中缀-% 的关联歧义以及中缀和后缀之间的优先级歧义。

要在没有优先规则的情况下解决它，你需要这样的东西：

%token S_NUM O_PERCENT
%%

default: mod_term ;

mod_term: _mod_value
    | _mod_value O_PERCENT mod_term ;

_mod_value: _mod_value O_PERCENT ;
    | S_NUM
    ;

这使得中缀-% 右结合而不是左结合。不幸的是，如果不使用也使 infix-% 左结合的优先规则，我看不到解决这个问题的方法。这是因为您无法确定给定的 '%' 标记是中缀还是后缀，直到您看到 after 标记，因此非终结符之前两条规则的 '%' 必须相同（此处 _mod_value 或 %prec 代码中的 expr）

LALR(1) shift/reduce 错误使用 % 作为百分比和 mod

LALR(1) shift/reduce error using % for both percent and mod

bison

lalr

shift-reduce-conflict