Генератор синтаксического анализатора Beaver конфликты сдвига-уменьшения, связанные с зависанием else

Я скармливаю (сгенерированную) грамматику генератору синтаксического анализатора Beaver. Множественные конфликты сдвиг-уменьшение вызваны, кажется, проблемой висячего 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   
    ;

parser-generator shift-reduce-conflict lalr dangling-else beaver
person Hawk    schedule 18.08.2020    source источник
comment
Я вижу, вы работаете с движком YAJCO. У меня возникают проблемы с тем, что сгенерированный мной синтаксический анализатор не пропускает символы SPACE во входной строке. Я использовал аннотацию @Skip("\\s"), чтобы указать внутри файла package-info.java, что парсер должен пропускать символ. Есть ли что-то особенное, что нужно настроить для синтаксического анализатора, сгенерированного Beaver, для выполнения этой работы?   -  person Sara Bean    schedule 14.04.2021
comment
@Sara Bean Я использовал отдельные символы: skips = { @Skip(" "), @Skip("\\t"), @Skip("\\n"), @Skip("\\r") }   -  person Hawk    schedule 16.04.2021
comment
спасибо, проблема, однако, непростая, потому что я использовал несколько вариантов, но, похоже, ничего не работало. Работает только после того, как я воссоздал проект с нуля.   -  person Sara Bean    schedule 16.04.2021

Ответы (1)


arrow_upward
0
arrow_downward

Есть проблема в создании грамматики. Это должно было быть

OptionalStatement_1
    = ELSE Statement.falseStatement   
    |   
    ;

не StatementArray3.falseStatement

после правильного создания альтернативы ELSE Statement.falseStatement возникает только один конфликт сдвига-уменьшения, и я могу полагаться на действие SHIFT по умолчанию.

person Hawk    schedule 18.08.2020