Как разрешить уменьшить уменьшить конфликты в бизоне?

Во-первых, я уже упоминал здесь много подобных вопросов, но не смог разрешить конфликты.

У меня есть этот кусок в моем файле .y

.
.
.
obj
    : INT { $$ = objNew($1, INT_T); }
    | FLOAT { $$ = objNew($1, FLOAT_T); }
    | STR { $$ = objNew($1, STR_T); }
    ;

var
    : IDEN { $$ = varLookup($1); }
    ;

atom
    : '(' expression ')' { $$ = $2; }
    ;

index
    : '[' obj ']' { $$ = $2; }
    ;

primary_expr
    : obj { $$ = objExpr($1); }
    | var { $$ = varExpr($1); }
    | atom { $$ = atmExpr($1); }
    | expression index { $$ = idxExpr($1, $2); }
    ;

unary_expr
    : primary_expr { $$ = $1; }
    | '+' unary_expr { $$ = unExpr(UPLUS, $2); }
    | '-' unary_expr { $$ = unExpr(UMINUS, $2); }
    ;

power_expr
    : unary_expr { $$ = $1; }
    | power_expr '^' unary_expr { $$ = biExpr('^', $1, $3); }
    ;

multiplicative_expr
    : power_expr { $$ = $1; }
    | multiplicative_expr '*' power_expr { $$ = biExpr('*', $1, $3); }
    | multiplicative_expr '/' power_expr { $$ = biExpr('/', $1, $3); }
    ;

additive_expr
    : multiplicative_expr { $$ = $1; }
    | additive_expr '+' multiplicative_expr { $$ = biExpr('+', $1, $3); }
    | additive_expr '-' multiplicative_expr { $$ = biExpr('-', $1, $3); }
    ;

relational_expr
    : additive_expr { $$ = $1; }
    | relational_expr '>' additive_expr { $$ = biExpr('>', $1, $3); }
    | relational_expr '<' additive_expr { $$ = biExpr('<', $1, $3); }
    | relational_expr '=' additive_expr { $$ = biExpr('=', $1, $3); }
    ;

referential_expr
    : relational_expr { $$ = $1; }
    | referential_expr IS relational_expr { $$ = biExpr(IS, $1, $3); }
    ;

conjunction_expr
    : referential_expr { $$ = $1; }
    | conjunction_expr AND referential_expr { $$ = biExpr(AND, $1, $3); }
    ;

disjunction_expr
    : conjunction_expr { $$ = $1; }
    | disjunction_expr OR conjunction_expr { $$ = biExpr(OR, $1, $3); }
    ;

conditional_expr
    : disjunction_expr { $$ = $1; }
    | disjunction_expr '?' disjunction_expr ':' conditional_expr { $$ = trExpr('?', $1, $3, $5); }
    ;

sequence
    : conditional_expr { $$ = seqChain(NULL, $1); }
    | sequence ',' conditional_expr { $$ = seqChain($1, $3); }
    ;

assignment_expr
    : sequence { $$ = seqAssign($1, NULL); }
    | sequence ASS assignment_expr { $$ = seqAssign($1, $3); }
    ;

expression
    : assignment_expr { $$ = $1; }
    ;

statement
    : ';' { $$ = NULL; }
    | expression ';' { $$ = exprStmt($1); }
    ;

routine
    : routine statement { $$ = rtnChain($1, $2); }
    | { $$ = NULL; }
    ;

program
    : routine { compile($1); exit(0); }
    ;

.
.
.

Этот грамматик порождает много конфликтов приведения/уменьшения. Например:

State 81

   18 power_expr: unary_expr .
   19           | power_expr '^' unary_expr .

    '+'       reduce using rule 18 (power_expr)
    '+'       [reduce using rule 19 (power_expr)]

У меня много подобных конфликтов. Но я не понимаю этого.
Насколько я знаю, это говорит о том, что когда производство unary_expr или когда оно power_expr '^' unary_expr, а затем выглядит как '+', возникает конфликт уменьшения\уменьшения. Но почему возникает конфликт уменьшения\уменьшения? Когда у него есть часть power_expr '^', он может использовать правило 19 (и должен использовать, поскольку в противном случае производство будет power_expr '^' power_expr, которое не определено в грамматике.), а когда нет части power_expr '^', он должен использовать правило 18. Где здесь возникает двусмысленность? , и как это решить.


person Sourav Kannantha B    schedule 31.01.2021    source источник
comment
Покажите всю грамматику, пожалуйста (или покажите полную сокращенную грамматику, которая демонстрирует ту же проблему). Проблема, несомненно, заключается в невидимой части грамматики. Я мог бы догадаться о причине, но я бы предпочел знать, о чем говорю.   -  person rici    schedule 31.01.2021
comment
@rici Я добавил всего грамматика. Проверь это сейчас.   -  person Sourav Kannantha B    schedule 31.01.2021
comment
Я рад, что не пытался предугадать, потому что я бы догадался неправильно.   -  person rici    schedule 31.01.2021
comment
Вы пытались запустить bison -Wcounterexamples?   -  person akim    schedule 14.02.2021
comment
@akim Я думаю, что это не будет работать в Windows. Я получаю bison: invalid argument 'counterexamples' for '--warning' ошибку.   -  person Sourav Kannantha B    schedule 14.02.2021
comment
@SouravKannanthaB Не имеет отношения к ОС, но относится к версии Bison: она была представлена ​​​​в Bison 3.7.   -  person akim    schedule 15.02.2021


Ответы (1)


Проблема связана с правилом

primary_expr: expression index 

Это правило не может быть правильным, так как оно подразумевает, что a+b[3] можно разобрать, применив [3] к expression a+b. Но его также можно разобрать, как если бы он был написан a+(b[3]). Эта неоднозначность порождает конфликты уменьшения-уменьшения.

Мы знаем, что только вторая интерпретация верна, что настоятельно предполагает, что правило должно быть

primary_expr: primary_expr index 

Я верю, что перемены разрешат ваши конфликты.

person rici    schedule 31.01.2021
comment
Спасибо большое. Мгновенно разрешились все конфликты уменьшения\уменьшения. Но как ты это нашел? Это ваш опыт? или я бы тоже нашел его только на основе .output бизона? (Это первый раз, когда я использую yacc/bison) - person Sourav Kannantha B; 31.01.2021
comment
@SouravKannanthaB: я нашел это, ища использование expression в вашей грамматике. Это была догадка, основанная на опыте. В общем, когда вы видите неожиданное сокращение в таблице состояний, вам нужно работать в обратном направлении, чтобы ответить на вопрос, как синтаксический анализатор мог добраться до этого сокращения?; текстовый редактор, который позволяет вам легко искать текст (например, до состояния 81), может упростить навигацию назад по выходным данным таблицы состояний bison. - person rici; 31.01.2021
comment
@SouravKannanthaB: Другое дело, что вы сосредоточились на постановках для ^, как в тексте вашего вопроса, так и при первоначальном выборе постановок для показа. Но проблема не в этом. Ключом к проблеме является упреждающий токен, который ее запускает (или, что более вероятно, большой набор упреждающих токенов), потому что может быть задействована большая цепочка сокращений. (Это просто эвристика, но, по крайней мере, она может привести к поиску в нужном месте.) - person rici; 31.01.2021