尝试添加可选规则时，Bison中的Shift/Reduce冲突 [英] Shift/Reduce conflict in Bison, when trying to add optional rule

问题描述

我正在尝试解决野牛的转变/减少冲突.我有语法规则

new_expr:
    T_NEW class_name_reference optional_generics_list ctor_arguments
        { $$ = zend_ast_create(ZEND_AST_NEW, $2, $4, $3); }
|   T_NEW anonymous_class
        { $$ = $2; }

optional_generics_list:
    /* empty */     { $$ = NULL; }
|   generics_list   { $$ = $1; }

ctor_arguments:
    /* empty */ { $$ = zend_ast_create_list(0, ZEND_AST_ARG_LIST); }
|   argument_list { $$ = $1; }

这里的问题在于，optional_generics_list和ctor_arguments都可以为空.我如何指定(如果可以的话)，如果optional_generics_list和ctor_arguments都为空，那么ctor_arguments应该具有更高的优先级.也许我的问题是不正确的，而如何解决此冲突.

一些更新的信息: 也许生成的.output文件的输出会有所帮助:

    State 156 conflicts: 1 shift/reduce

State 156:

  303 new_expr: "new (T_NEW)" class_name_reference . optional_generics_list ctor_arguments

    '<'  shift, and go to state 304

    '<'       [reduce using rule 168 (optional_generics_list)]
    $default  reduce using rule 168 (optional_generics_list)

    optional_generics_list  go to state 305
    generics_list           go to state 306


State 305

  303 new_expr: "new (T_NEW)" class_name_reference optional_generics_list . ctor_arguments

    '('  shift, and go to state 229

    $default  reduce using rule 405 (ctor_arguments)

    argument_list   go to state 546
    ctor_arguments  go to state 552


State 306

  169 optional_generics_list: generics_list .

    $default  reduce using rule 169 (optional_generics_list)

解决方案

野牛输出文件指示的问题是new_expr后面可能跟有< 不是generics_list的一部分.例如，如果语法中也包含诸如此类的产生式:

term: new_expr
comparison: term '<' term

(当然，人们希望真实的语法比这具有更多的可能性，但那是必不可少的.)

换句话说，如果您的语法允许您比较两个新构造的对象，则解析器无法判断它看到的< 是generics_list的开始还是new_expr之后的简单比较运算符，其中同时省略了generics_list和ctor_arguments:

if new Foo < oldFoo then...

myFoo = new Foo<int>(42)

最简单的解决方法是，如果要在表达式中使用new_expr，则必须将其括在括号中.

对于它的价值，C ++通过知道名称是否已模板化来进行处理.如果名称可以使用模板参数，则名称后的< 会被解释为模板参数列表的开始.否则，它是一个小于运算符.因此，如果v是模板化的，则必须编写(new v) < ...，但是如果v只是一个简单的类型名，则可以省略括号:new int < ....实施起来很棘手；您需要某种词汇反馈，并且需要对可以放置模板声明的位置施加一些限制. C ++具有类似分辨率的其他一些独特的解析挑战.例如，new int * i是错误，因为使用规则说*被解析为指针类型修饰符，该规则说new表达式中的类型是可解析为类型的最长标记序列.

当new用作任何运算符的左参数时，我会使用强制括号，因为它对读者而言不那么混乱.它还简化了语法，这是一件好事，因为语法不仅仅用于语法分析；还包括语法分析.它们是该语言文档的重要组成部分，不必要的复杂语法使该语言变得不必要地难以学习和理解.

有趣的是，在编写有关C ++的上述说明的过程中，我发现了一个主要C ++编译器的解析器中的错误. (至少，我认为我知道哪个编译器是错误的；更准确地说，我发现两个流行的编译器的行为不一致，因此其中一个必定是错误的.)更简单的规则对任何编译器都没有影响.非人为设计的程序，这样就大大减少了该错误的发生(并且易于验证).因此，我不清楚在表达式中间允许无括号的new运算的附加值.

I am trying to solve shift/reduce conflict in Bison. I have following grammar rules

new_expr:
    T_NEW class_name_reference optional_generics_list ctor_arguments
        { $$ = zend_ast_create(ZEND_AST_NEW, $2, $4, $3); }
|   T_NEW anonymous_class
        { $$ = $2; }

optional_generics_list:
    /* empty */     { $$ = NULL; }
|   generics_list   { $$ = $1; }

ctor_arguments:
    /* empty */ { $$ = zend_ast_create_list(0, ZEND_AST_ARG_LIST); }
|   argument_list { $$ = $1; }

The problem here lies in that fact, that both optional_generics_list and ctor_arguments can be empty. How can I specify (if I could) that if both optional_generics_list and ctor_arguments are empty, then ctor_arguments should have higher priority. Or maybe my question is not correct, and how can solve this conflict instead.

Some updated info: Maybe output of generated .output file will help:

    State 156 conflicts: 1 shift/reduce

State 156:

  303 new_expr: "new (T_NEW)" class_name_reference . optional_generics_list ctor_arguments

    '<'  shift, and go to state 304

    '<'       [reduce using rule 168 (optional_generics_list)]
    $default  reduce using rule 168 (optional_generics_list)

    optional_generics_list  go to state 305
    generics_list           go to state 306


State 305

  303 new_expr: "new (T_NEW)" class_name_reference optional_generics_list . ctor_arguments

    '('  shift, and go to state 229

    $default  reduce using rule 405 (ctor_arguments)

    argument_list   go to state 546
    ctor_arguments  go to state 552


State 306

  169 optional_generics_list: generics_list .

    $default  reduce using rule 169 (optional_generics_list)

解决方案

The problem indicated by the bison output file is that it is possible that a new_expr could be followed by an < which is not part of a generics_list. That would be the case if, for example, the grammar also contained productions like:

term: new_expr
comparison: term '<' term

(Of course, one would expect a real grammar to have a lot more possibilities than that, but those are the essential ones.)

In other words, if your grammar allows you to compare two newly-constructed objects, then the parser cannot tell whether the < that it sees is the start of a generics_list, or a simple comparison operator after a new_expr where both the generics_list and the ctor_arguments have been omitted:

if new Foo < oldFoo then...

myFoo = new Foo<int>(42)

The simplest fix would be to insist that a new_expr be parenthesized if it is going to be used in an expression.

For what it's worth, C++ handles this by knowing whether names are templated or not. If a name can take template arguments, then a < following the name is interpreted as starting the template argument list; otherwise it's a less-than operator. So if v is templated, then you have to write (new v) < ..., but if v is just a simple typename, you can leave out the parentheses: new int < .... implementing that is tricky; you need some kind of lexical feedback, and you need to impose some restrictions on where template declarations can be placed. C++ has some other unique parsing challenges with similar resolutions. For example, new int * i is an error because the * is parsed as being a pointer type modifier, using a rule which says that the type in a new expression is the longest sequence of tokens parseable as a type.

I'd go for mandatory parentheses when new is used as the left argument of any operator, since it's less confusing for the reader. It also simplifies the grammar, and that's a Good Thing because grammars are not just for parsing; they are an essential part of the documentation of the language, and unnecessarily complicated grammars make the language unnecessarily hard to learn and understand.

Interestingly, in the course of writing the above note about C++, I discovered a bug in the parser of one major C++ compiler. (At least, I think I know which compiler is buggy; it would be more accurate to say that I discovered that two popular compilers have inconsistent behaviour, so one of them must be wrong.) A simpler rule would have had no effect on any non-contrived program, and would have made the bug much less likely (and much easier to verify). So it is not at all clear to me the value added of permitting unparenthesized new operations in the middle of an expression.

这篇关于尝试添加可选规则时，Bison中的Shift/Reduce冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！