сдвиг / уменьшение конфликта в грамматике с необязательной точкой с запятой

Образец репозитория

Я бы хотел сделать что-то вроде этого:

// match used as a statement, semicolon is optional
match (1) {}

// match used as an expression, semicolon is required
1 + match (2) {};
statement
    : expression_without_block T_SEMICOLON
    | expression_with_block
;

expression
    : expression_without_block
    | expression_with_block
;

expression_without_block
    : scalar
    | expression_without_block T_PLUS expression
    | T_PLUS expression
;

expression_with_block
    : T_MATCH T_LEFT expression T_RIGHT T_CURLY_LEFT T_CURLY_RIGHT
;

Идея состоит в том, что expression_with_block нельзя использовать в начале оператора, что делает однозначным следующее:

match (1) {}
+2;

// Can't mean
(match (1) {} + 2);
// because of the line "expression_without_block T_PLUS expression"

Грамматика вызывает конфликты сдвига / уменьшения, но я понятия не имею, почему. В выводе говорится следующее (но я не уверен, что с этим делать):

State 11 conflicts: 1 shift/reduce

...

State 11

    5 expression: expression_without_block .
    8 expression_without_block: expression_without_block . T_PLUS expression

    T_PLUS  shift, and go to state 14

    T_PLUS    [reduce using rule 5 (expression)]
    $default  reduce using rule 5 (expression)

Полный выходной файл можно найти здесь .

Я также даже не уверен, что это правильный подход, потому что тогда что-то вроде этого не сработает:

// `match` can't be at the lhs of an expression, even in sub-expressions
func_call(match (10) {} + 20);

Есть ли способ достичь того, что я описываю здесь, на зубрах? Я не эксперт по зубрам, поэтому буду очень признателен за помощь. Спасибо!


person IluTov    schedule 11.04.2020    source источник
comment
Я не думаю, что понимаю, как предложенное вами грамматическое ограничение реализует требование. Я предполагаю, что вы намерены (в основном) разрешить использование точек с запятой в конце операторов как необязательных (как в Javascript или Awk), но это намного сложнее, чем кажется на первый взгляд. В любом случае, я не думаю, что решение здесь связано с точкой с запятой. Или сопоставьте выражения, если на то пошло. Основная проблема заключается в том, что если вы позволяете выражениям операторов начинаться с унарных операторов (или с выражений в скобках), вы создаете двусмысленность, если предыдущий оператор был выражением ...   -  person rici    schedule 11.04.2020
comment
Один из способов решить эту проблему - запретить (возможно) унарным или (возможно) постфиксным операторам следовать за новой строкой. См., Например, запрет Javascript на expr<NL>++. Есть много других возможностей.   -  person rici    schedule 11.04.2020


Ответы (1)


Это очень классический вид конфликта, который происходит с леворекурсивными правилами, но, поскольку разрешение конфликта сдвига / уменьшения по умолчанию - сдвиг, то здесь все будет хорошо.

Вот как следует читать след бизона:

T_PLUS  shift, and go to state 14              -- when next token is T_PLUS shift action is selected

T_PLUS    [reduce using rule 5 (expression)]   -- the action between [] was disabled by Bison default conflict resolution

Чтобы переопределить стандартное разрешение конфликтов Bison (что здесь не обязательно), мы можем использовать приоритет оператора (см. https://www.gnu.org/software/bison/manual/bison.html#Precedence-Decl) или приоритет для неоператоров (см. https://www.gnu.org/software/bison/manual/bison.html#Non-Operators)

person P. PICARD    schedule 11.04.2020
comment
Ваш комментарий был чрезвычайно полезным, спасибо! Оказывается, мой пример не полностью воспроизвел проблему. В реальном репо это фактически конфликт уменьшения / уменьшения. gist.github.com/iluuu1994/ Видно конфликт между инфиксными и двоичными операторами _1 _ / _ 2_. Я до сих пор не понимаю, почему именно это происходит. Но я принимаю ваш ответ, поскольку вы правильно ответили на мой первоначальный вопрос. - person IluTov; 11.04.2020
comment
Добро пожаловать. Ваша грамматика неоднозначна, потому что +<expr_with_block>+<expr> может быть получен из двух допустимых синтаксических деревьев: (+<expr_with_block>)(+ <expr>) и (+<expr_with_block>+<expr>). Тогда мы не сможем выбрать между двумя действиями уменьшения. Боюсь, вам придется ставить конечную точку с запятой в конце всех ваших выражений. Если нужно, я могу подробно рассказать свой ответ в новом посте. - person P. PICARD; 11.04.2020
comment
Я нашел очень неоптимальный способ реализовать это: github.com/ilu-u199 commit / Мне пришлось продублировать огромный блок, посмотрю, смогу ли я избавиться от дублирования. В очередной раз благодарим за помощь! - person IluTov; 11.04.2020