这种转变/减少冲突从何而来?

Question

我试图通过在Jison (javascript解析器)中定义一种非常简单的语言来获得解析的技巧。它接受与bison相同/非常相似的语法。

下面是我的语法:

%token INT TRUE FALSE WHILE DO IF THEN ELSE LOCATION ASSIGN EOF DEREF
%left "+"
%left ">="
/* Define Start Production */
%start Program 
/* Define Grammar Productions */
%%
Program
    : Statement EOF
    ;
Statement
    : Expression
    | WHILE BoolExpression DO Statement
    | LOCATION ASSIGN IntExpression
    ;
Expression
    : IntExpression
    | BoolExpression
    ;
IntExpression
    : INT IntExpressionRest
    | IF BoolExpression THEN Statement ELSE Statement
    | DEREF LOCATION
    ;   
IntExpressionRest
    : /* epsilon */
    | "+" IntExpression
    ;
BoolExpression
    : TRUE
    | FALSE
    | IntExpression ">=" IntExpression
    ;
%%

我得到一个轮班/减少冲突。Jison的输出如下:

Conflict in grammar: multiple actions possible when lookahead token is >= in state 6
- reduce by rule: Expression -> IntExpression
- shift token (then go to state 17)
States with conflicts:
State 6
  Expression -> IntExpression . #lookaheads= EOF >= THEN DO ELSE
  BoolExpression -> IntExpression .>= IntExpression #lookaheads= EOF DO THEN ELSE >=

Answer 1

您的移位减少冲突被检测到，因为>=在Expression非终结符的后续集合中。这主要是由于Statement可以是Expression, IntExpression可以以statement结束。考虑下面的输入IF c THEN S1 ELSE S2 >= 42，如果您有括号来消除歧义，那么它可以被解释为(IF c THEN S1 ELSE S2) >= 42和IF c THEN S1 ELSE (S2 >= 42)。

Answer 2

你的问题来自

 IF BoolExpression THEN Statement ELSE Statement

如果THEN之后的语句包含一个If，你怎么知道ELSE是属于第一个还是第二个If ?更多信息请看这里:http://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html

唯一100%无歧义的修复是要求在if/else语句周围使用某种分隔符(大多数语言使用括号"{"one_answers"}")。前,

 IF BoolExpression THEN '{' Statement '}' ELSE '{' Statement '}'