Shift/уменьшить конфликт в Happy грамматике

Question

я получил следующее (сильно урезанная) Happy грамматику

%token 
    '{' { Langle } 
    '}' { Rangle } 
    '..' { DotDot } 
    '::' { ColonColon } 
    '@' { At } 
    mut { Mut } 
    ident { Ident } 

%% 

pattern 
    : binding_mode ident at_pat { error "identifier pattern" } 
    | expr_path     { error "constant expression" } 
    | expr_path '{' '..' '}'  { error "struct pattern" } 

binding_mode 
    : mut      { } 
    |       { } 

at_pat 
    : '@' pat     { } 
    |       { } 

expr_path 
    : expr_path '::' ident  { } 
    | ident      { } 

который имеет конфликтов сдвиг/свёртка вокруг идентификаторов шаблонов. По умолчанию Happy выбирает смещение, но в этом случае это не то, что я хочу: он пытается обучить все в constant expression, даже когда это может быть identifier pattern.

Я читал, что приоритет/ассоциативность - это способ решить эту проблему, но ничего, что я добавил, не удалось сдвинуть грамматику в правильном направлении (честно говоря, я принимал в основном выстрелы в темноте).

Используя некоторые очевидные лексемизацию, я хотел бы иметь:

• x с получением identifier pattern
• mut x с получением identifier pattern
• std::pi с получением constant expression
• point{..} с получением struct pattern
• std::point{..} с получением struct pattern

В основном, если не является { или :: маркер ждет, чтобы быть потреблен, идентификатор должен идти в identifier pattern случае.

---

Я прошу прощения, если мой вопрос не ясно - часть проблемы заключается в том, что у меня трудное время точного определения того, что проблема даже есть. :(

Answer 1

Во-первых, важно понять, что такое сдвиг. Сдвиг является результатом принятия следующего входного токена и помещения его в стек парсера (где он в конечном итоге будет частью производства, но он не нужно знать, какой из них еще нет.) Снижение снимает ноль или больше токенов с верхней части стека, которые соответствуют правой стороне какой-либо продукции, и заменяя их левой стороной.

Когда парсер решает создать identifier pattern из binding_mode ident at_pat, где at_pat пуст, он не сдвигается, он уменьшается. Фактически, он уменьшается дважды: сначала он уменьшает нулевые символы в пустой at_pat, а затем уменьшает три верхних символа стека вidentifier pattern. Если бы не было binding_mode, он мог бы уменьшить ident до expr_path, а затем уменьшить expr_path до constant_expression. Так что это будет конфликт сокращения/сокращения.

Но есть еще одна проблема, именно потому, что binding_mode имеет значение NULL. Когда синтаксический анализатор видит ident, он не знает, будет ли возможно binding_mode, поэтому он не знает, следует ли уменьшить пустой binding_mode или сдвинуть ident. Это конфликт смены/сокращения. Так как он предпочитает сдвиг для уменьшения, он выбирает сдвиг ident, что означает, что пустой binding_mode не может быть произведен, что, в свою очередь, исключает конфликт уменьшения/уменьшения (и предотвращает распознавание ident @ pat.)

Чтобы распутать все это, мы должны начать, избегая необходимости уменьшить пустой binding_mode. Мы делаем это с помощью обычного алгоритма исключения с нулевым производством, который включает в себя создание двух копий правой части, один с нулевым нетерминалом, а другой без; мы затем удаляем нулевую продукцию. Как только мы это сделаем, возникает конфликт сокращения/сокращения.

Чтобы избежать конфликта сокращения/сокращения, нам необходимо четко указать, какая продукция является предпочтительной. Сокращение/уменьшение конфликтов не может быть разрешено с помощью объявлений приоритетов, поскольку алгоритм приоритета всегда предполагает сравнение между производством (которое может быть уменьшено) и терминалом (который может быть сдвинут). Таким образом, разрешение должно быть явным, и это означает, что нам нужно сказать, что голый ident является шаблоном, а expr_path, который не является ident, является постоянным выражением. Это оставляет нам следующее:

(Обратите внимание, что я использовал нетерминалы для обозначения трех разных производств для pattern, вместо того, чтобы полагаться на действия. Для меня это облегчает думать и читать.)

pattern: identifier_pattern | constant_expression | struct_pattern 

Вот нулевая ликвидация производства:

identifier_pattern: ident at_pat 
        | binding_mode ident at_pat 

Вот явный запрет на идент:

constant_expression: complex_expr_path 

struct_pattern:  expr_path '{' '..' '}' 

binding_mode больше не обнуляемый:

binding_mode: mut 

at_pat 
    : '@' pat 
    | %empty 

Здесь мы создаем два различные expr_paths:

complex_expr_path 
    : complex_expr_path '::' ident 
    | ident '::' ident 

expr_path: ident | complex_expr_path 

Я надеюсь, что решение имеет какое-то отношение к исходной грамматике.