0

我正在向 Beaver 解析器生成器提供（生成的）语法。多个 shift-reduce 冲突是由该规则中的悬空 else 问题引起的：

Condition
    = IF LPAR Expression.expression RPAR Statement.trueStatement OptionalStatement_1.elem2  
    ;
OptionalStatement_1
    = ELSE StatementArray3.falseStatement   
    |   
    ;

我认为悬空 else 不会有问题，因为该工具默认选择 SHIFT，这是对悬空 else 问题 AFAIK 的公认解决方案。但是，有一些问题，因为我有 16 个其他警告，我不明白为什么：

grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (ELSE: SHIFT; goto 93) over (ELSE: REDUCE OptionalStatement_1 = ) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (LBR: SHIFT; goto 5) over (LBR: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (IF: SHIFT; goto 18) over (IF: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (RETURN: SHIFT; goto 95) over (RETURN: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (DO: SHIFT; goto 100) over (DO: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (READ: SHIFT; goto 107) over (READ: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (WRITE: SHIFT; goto 110) over (WRITE: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (SEMICOLON: SHIFT; goto 113) over (SEMICOLON: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (WHILE: SHIFT; goto 114) over (WHILE: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (LPAR: SHIFT; goto 63) over (LPAR: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (PLUSPLUS: SHIFT; goto 71) over (PLUSPLUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (PLUS: SHIFT; goto 73) over (PLUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (EXCL: SHIFT; goto 75) over (EXCL: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (MINUS: SHIFT; goto 77) over (MINUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (MINUSMINUS: SHIFT; goto 79) over (MINUSMINUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (VALUE: SHIFT; goto 81) over (VALUE: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (IDENT: SHIFT; goto 82) over (IDENT: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.

结果是在 StatementArray3 中有垃圾注入到 else 分支中（完全错误的类型，一个 List 而不是 Optional，充满了从以下语句中吞噬的东西）。有人可以解释一下，所有这些减少班次的冲突是由什么引起的（除了明显的第一个冲突）吗？请注意，语法是从类模型生成的，所以这个问题的非常具体的解决方案不是最好的，我需要一般地解决这类问题，或者改变语法。

由另一种方法生成的前面的语法（我想避免）产生了这个语法：

Condition
    = IF LPAR Expression.expression RPAR Statement.trueStatement    
    | IF LPAR Expression.expression RPAR Statement.trueStatement ELSE Statement.falseStatement  
    ;

在编译过程中没有冲突，但是对于以下输入：

{
  if(b == 21)
    c = 10;
  else
    c = 15;
}

解析器在运行时失败，只是跳过 else 并将第二个分配视为顶级：

4,4-4,7: Syntax Error: unexpected token "else"
4,4-4,7: Recovered: removed unexpected token "else"

完整的有问题的语法（去掉 %import、%typeof 和{: ... :}）：

%terminals PERC, ASSIGNDIV, LT, RPAR, VALUE, DO, ASSIGN, PLUSPLUS, QUESTION, MINUS, WRITE, RETURN, LPAR, SEMICOLON, ASSIGNADD, ELSE, LBR, IF, COMMA, RBR, OR, SLASH, MINUSMINUS, COLON, EQ, GT, READ, ASSIGNMUL, STAR, IDENT, ASSIGNSUB, ASSIGNMOD, AND, GTE, WHILE, NEQ, EXCL, LTE, PLUS;

%left LPAR, RPAR;
%nonassoc PLUSPLUS, MINUSMINUS;
%left PREC_13_1, EXCL, PREC_13_2;
%left PERC, SLASH, STAR;
%left PLUS, MINUS;
%left LT, LTE, GT, GTE;
%left NEQ, EQ;
%left AND;
%left OR;
%left QUESTION, COLON;
%right ASSIGN, ASSIGNADD, ASSIGNMUL, ASSIGNDIV, ASSIGNSUB, ASSIGNMOD;


%goal Program;

Number
    = VALUE.value   
    ;

Program
    = FunctionArray1.functions Block.main   
    ;

UnaryOperation
    = PLUSPLUS Expression.expression    
    | PLUS Expression.expression @ PREC_13_1    
    | EXCL Expression.expression    
    | MINUS Expression.expression @ PREC_13_2   
    | MINUSMINUS Expression.expression  
    ;

Block
    = LBR StatementArray3.statements RBR    
    ;

BinaryOperation
    = Expression.expression1 NEQ Expression.expression2 
    | Expression.expression1 OR Expression.expression2  
    | Expression.expression1 PERC Expression.expression2    
    | Expression.expression1 EQ Expression.expression2  
    | Expression.expression1 PLUS Expression.expression2    
    | Expression.expression1 LT Expression.expression2  
    | Expression.expression1 MINUS Expression.expression2   
    | Expression.expression1 LTE Expression.expression2 
    | Expression.expression1 SLASH Expression.expression2   
    | Expression.expression1 GT Expression.expression2  
    | Expression.expression1 ASSIGN Expression.expression2  
    | Expression.expression1 STAR Expression.expression2    
    | AssignmentGeneric.val 
    | Expression.expression1 GTE Expression.expression2 
    | Expression.expression1 AND Expression.expression2 
    ;

Expression
    = LPAR Expression.val RPAR  
    | Expression.expression1 QUESTION Expression.expression2 COLON Expression.expression3   
    | UnaryOperation.val    
    | Number.val    
    | Variable.val  
    | FunctionCall.val  
    | BinaryOperation.val   
    ;

ParameterArray2
    = ParameterArray2.list COMMA Parameter.elem 
    |   
    | Parameter.elem    
    ;

Statement
    = Block.val 
    | Condition.val 
    | ReturnFunction.val    
    | ExpressionStatement.val   
    | DoWhile.val   
    | Read.val  
    | Write.val 
    | EmptyStatement.val    
    | WhileStatement.val    
    ;

Parameter
    = IDENT.ident   
    ;

Write
    = WRITE Expression.expression SEMICOLON 
    ;

OptionalStatement_1
    = ELSE StatementArray3.falseStatement   
    |   
    ;

FunctionArray1
    = FunctionArray1.list Function.elem 
    |   
    ;

WhileStatement
    = WHILE LPAR Expression.expression RPAR Statement.statement 
    ;

ExpressionArray4
    = ExpressionArray4.list COMMA Expression.elem   
    |   
    | Expression.elem   
    ;

ExpressionStatement
    = Expression.expression SEMICOLON   
    ;

Variable
    = IDENT.ident   
    ;

EmptyStatement
    = SEMICOLON 
    ;

Read
    = READ IDENT.ident SEMICOLON    
    ;

FunctionCall
    = IDENT.ident LPAR ExpressionArray4.expressions RPAR    
    ;

Condition
    = IF LPAR Expression.expression RPAR Statement.trueStatement OptionalStatement_1.elem2  
    ;

DoWhile
    = DO Statement.statement WHILE LPAR Expression.expression RPAR SEMICOLON    
    ;

Function
    = IDENT.ident LPAR ParameterArray2.parameters RPAR Block.body   
    ;

ReturnFunction
    = RETURN Expression.expression SEMICOLON    
    ;

StatementArray3
    = StatementArray3.list Statement.elem   
    |   
    ;

AssignmentGeneric
    = Expression.expression1 ASSIGNADD Expression.expression2   
    | Expression.expression1 ASSIGNMUL Expression.expression2   
    | Expression.expression1 ASSIGNDIV Expression.expression2   
    | Expression.expression1 ASSIGNSUB Expression.expression2   
    | Expression.expression1 ASSIGNMOD Expression.expression2   
    ;
4

1 回答 1

0

语法生成有问题。应该是

OptionalStatement_1
    = ELSE Statement.falseStatement   
    |   
    ;

不是StatementArray3.falseStatement

在正确生成ELSE Statement.falseStatement替代方案后，只会出现一个移位减少冲突，我可以依赖默认的 SHIFT 操作。

于 2020-08-18T17:42:59.190 回答