Почему у бизонов конфликт сдвига / уменьшения с однозначной грамматикой? - PullRequest
Новая
       49

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

0 голосов
/ 11 января 2019

Я использую бизона и столкнулся с конфликтом сдвига / уменьшения. Зубр определил один сдвиг / уменьшить конфликт. Я не могу найти неоднозначность в этом языке: 

start
    : IDENT trailer EQUAL atom trailer SEMICOLON
    | atom trailer SEMICOLON
    ;

atom
    : LPAR atom trailer RPAR
    | IDENT
    ;

trailer
    : %empty
    | LPAR RPAR
    ;

Эта проблема также описана в документации по грамматике python внизу. Я могу устранить неоднозначность, используя решение, описанное в этой документации (измените строку 2 на atom trialer EQUAL atom trailer SEMICOLON.

Теперь, когда это исправлено, я могу двигаться дальше, но мне все еще любопытно, что это за проблема. Пожалуйста, опишите мне проблему с грамматикой выше и приведите пример предложения на языке, который имеет два уникальных дерева разбора.

РЕДАКТ. 1
После дальнейшего изучения, у следующего есть конфликт сдвига / уменьшения: 

start
    : IDENT LPAR RPAR EQUAL atom LPAR RPAR SEMICOLON
    | atom LPAR RPAR SEMICOLON
    ;

atom
    : IDENT
    ;

но здесь нет конфликта сдвига / уменьшения: 

start
    : IDENT LPAR RPAR EQUAL IDENT LPAR RPAR SEMICOLON
    | IDENT LPAR RPAR SEMICOLON
    ;

Это кажется мне очень подозрительным, потому что в первой грамматике атом вынужден производить ИДЕНТ, поэтому эти две грамматики по сути одинаковы. Мне все еще понадобятся некоторые объяснения.

1 Ответ

0 голосов
/ 11 января 2019

Перемещение / уменьшение конфликтов не обязательно означает, что ваша грамматика неоднозначна. Все неоднозначные грамматики приведут к конфликту «сдвиг / уменьшение» или «уменьшение / уменьшение», но обратное не обязательно верно.

В вашем случае представьте, что анализатор запустился и только что прочитал токен IDENT, а затем LPAR. У него есть два варианта действий. Во-первых, это может быть случай, когда вы создаете первую (более длинную) ветвь стартового нетерминала. В этом случае вам следует переместить LPAR с планом сокращения всего длинного выражения в дальнейшем. Во-вторых, возможно, вы создаете вторую (более короткую) ветвь стартового нетерминала, что означает, что вы должны уменьшить IDENT обратно до атома. Знание того, что следующим терминалом является LPAR, не поможет вам различить эти случаи, следовательно, конфликт сдвига / уменьшения.

С другой стороны, вторая версия вашей грамматики не требует принятия решения о том, как обрабатывать IDENT на фронте, пока не станет доступно больше контекста, и, таким образом, не возникнет конфликта.

...