LALR(1) shift/reduce 错误使用 % 作为百分比和 mod
LALR(1) shift/reduce error using % for both percent and mod
我开始了一个项目,其中的语法使用 %
(和单词 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
说明符,但没有运气。
如果您愿意接受解析器复杂性的增加,您始终可以通过添加 %glr-parser
指令将其变成 GLR 解析器。这意味着解析器在到达冲突点时将拆分并探索这两个状态,然后一旦它处理了足够的标记,它将删除无法解析的状态。不过,这确实需要足够新的 bison 版本。然而,就像其他人建议的那样,重新设计语言可能会更好。鉴于 Bison 对 GLR 解析器的现有限制,使用 GLR 解析器意味着您可能最终会使用连续百分比数量的指数数量的内存。
这里的歧义在于 '%'
是后缀运算符还是中缀运算符。这与 '-'
既是前缀运算符又是中缀运算符的常见表达式解析器问题非常相似,您可以使用显式 %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
)
我开始了一个项目,其中的语法使用 %
(和单词 mod
)作为 modulus 运算符,现在我想添加 %
作为尾部一元运算符除以 100。
一些注意事项,我不使用基于 C 的语言,我使用 bison 的 XML 输出实现了我自己的 tokenizer/compiler。我选择的步骤对我的实施至关重要。
有没有一种方法可以让我的语法在 LALR(1) 编译器中编译时没有任何 shift/reduce 错误?
基本上以下说法都是有效的:
5%
-> 0.055%%5
-> 0.05 mod 55%%%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
说明符,但没有运气。
如果您愿意接受解析器复杂性的增加,您始终可以通过添加 %glr-parser
指令将其变成 GLR 解析器。这意味着解析器在到达冲突点时将拆分并探索这两个状态,然后一旦它处理了足够的标记,它将删除无法解析的状态。不过,这确实需要足够新的 bison 版本。然而,就像其他人建议的那样,重新设计语言可能会更好。鉴于 Bison 对 GLR 解析器的现有限制,使用 GLR 解析器意味着您可能最终会使用连续百分比数量的指数数量的内存。
这里的歧义在于 '%'
是后缀运算符还是中缀运算符。这与 '-'
既是前缀运算符又是中缀运算符的常见表达式解析器问题非常相似,您可以使用显式 %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
)