#parsing #compiler-construction #yacc #bison #lalr
#синтаксический анализ #компилятор-конструирование #yacc #bison #lalr
Вопрос:
У меня есть следующая грамматика bison (как часть более сложной грамматики):
expression:
IDENTIFIER
| CONST
| LAMBDA match_block
;
match_block:
pattern '=' expression
| match_block '|' pattern '=' expression
;
pattern:
IDENTIFIER
| CONST
;
которые описывают выражения, содержащие идентификаторы, константы и лямбда-функции с сопоставлением с шаблоном, который выглядит следующим образом:
lambda 0 = 1
| 1 = 2
| x = x
Проблема заключается в конфликте сдвига / уменьшения на 1, вызванном неоднозначностью вложенных совпадений, как в следующем примере:
lambda 0 = 1
| x = lambda 1 = 2
| y = 4
Правило заключается в том, что блок совпадений относится к ближайшей функции, как показано с отступом в примере выше.
Мои вопросы - как я могу переписать эту грамматику, чтобы устранить эту двусмысленность (без использования директив %left % right yacc)?
Ответ №1:
Если вы всегда хотите, чтобы | привязывалось к ближайшему LAMBDA , это в основном просто означает, что вы можете иметь только LAMBDA в ПОСЛЕДНЕМ | предложении match_block :
non_lambda_expression:
IDENTIFIER
| CONST
;
expression:
non_lambda_expression
| LAMBDA match_block
;
non_lambda_match_block:
pattern '=' non_lambda_expression
| non_lambda_match_block '|' pattern '=' non_lambda_expression
;
match_block:
pattern '=' expression
| non_lambda_match_block '|' pattern '=' expression
;
pattern:
IDENTIFIER
| CONST
;
По сути, вы разделяете expression и match_block на две версии - ту, которая допускает лямбды, и ту, которая этого не делает, - и используете соответствующую в каждом месте, чтобы избежать двусмысленности.
Комментарии:
1. Большое спасибо! Я видел один пример устранения неоднозначности ранее в dragon book (для "dangling else"), но я не смог сделать это с помощью этой грамматики.
2. @SJ: по сути, это точно такой же шаблон, как и в случае с висячим else - приведенное выше преобразование совпадает с тем, что описано в книге Dragon, с той лишь разницей, что перед окончательным lambda может быть несколько не-lambda match_blocks