Почему у меня сдвиг/конфликт на ')', а не на '('?

Question

У меня есть синтаксис вроде

%(var)

и

%var

и (var)

Мои правила что-то вроде

optExpr:
    | '%''('CommaLoop')'
    | '%' CommaLoop

CommaLoop:
    val | CommaLoop',' val

Expr:
    MoreRules
    | '(' val ')'

Проблема в том, что он, похоже, не может определить, принадлежит ли ) %(CommaLoop) или % (val) но он жалуется на ) вместо (.Какого черта?разве оно не должно жаловаться на (?и как мне исправить ошибку?я думаю сделать %( токен — хорошее решение, но я хочу знать, почему $( это не ошибка, прежде чем делать это.

Answer 1

Это связано с тем, как работает анализ LR.Анализ LR фактически осуществляется снизу вверх: токены группируются в соответствии с правой частью ваших грамматических правил и заменяются на левую.Когда парсер «смещается», он помещает токен в стек, но на самом деле еще не соответствует правилу.Вместо этого он отслеживает частично совпадающие правила по текущему состоянию.Когда он достигает состояния, соответствующего концу правила, он может сокращаться, извлекая символы для RHS из стека и помещая обратно один символ, обозначающий LHS.Поэтому, если есть конфликты, они не проявляются до тех пор, пока парсер не дойдет до конца какого-то правила и не сможет решить, следует ли сокращать (или что сокращать).

В вашем примере, увидев % ( вал, это то, что будет в стеке (здесь верх находится справа).Когда просмотр вперед ), он не может решить, следует ли извлечь значение и уменьшить его с помощью правила Запятая:вал, или если это должно сдвинуть ) поэтому он может затем вытолкнуть 3 вещи и уменьшить их по правилу Выражение:'(' вал ')'

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

Answer 2

Сейчас ваше объяснение и ваша грамматика не совпадают.В вашем объяснении вы показываете, что все три фразы имеют «var», но ваша грамматика показывает, что те, которые начинаются с «%», допускают список, разделенный запятыми, а фраза без него допускает только одно «val».

На данный момент я предполагаю, что все три должны допускать список, разделенный запятыми.В этом случае я бы расценил грамматику примерно так:

optExpr: '%' aList

aList: CommaLoop
    | parenList

parenList: '(' CommaLoop ')'

CommaLoop: 
    | val 
    | CommaLoop ',' val

Expr: MoreRules
    | parenList

Я изменил optExpr и Expr, поэтому ни один из них не может соответствовать пустой последовательности - я думаю, вы, вероятно, изначально не собирались этого делать.Я детализировал это достаточно, чтобы пропустить это через byacc;он не выдает никаких предупреждений или ошибок.