Зубр исключить уменьшить / уменьшить конфликт между обнуляемыми нетерминалами?

Question

Я использую зубров (AFAIK они используют LL(1) разбор по умолчанию).

Моя грамматика говорит что-то вроде этого:

function_decl: ID '(' params ')' ':' TYPE ... // body may go here
function_call: ID '(' arguments ')'

params: ID ':' TYPE
     | params ',' ID ':' TYPE
     | %empty

arguments: ID
    | arguments ',' ID
    | %empty

Сейчас, bison предупреждает говоря reduce/reduce конфликт, потому что params а также arguments оба имеют нулевое значение (в случае нулевого параметра function()).

У меня вопрос, как я могу устранить (вместо того, чтобы подавить) этот конфликт?

Хотя кто-то предложил использовать другую технику синтаксического анализа, я хочу прояснить для себя, возможно ли это (и я должен это сделать), или я должен просто игнорировать это.

Answer 1

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

Вы совершенно правы, что конфликт является результатом как params а также arguments производя пустую строку. Поскольку синтаксический анализатор может только смотреть на один символ a, когда он читает ) в func()нужно решить, уменьшать ли пустую params (что заставит его продолжить function_decl) или пустой arguments (который передаст это function_call). Но невозможно узнать, пока не будет прочитан следующий токен.

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

function_decl: ID '(' params ')' ':' TYPE ... // body may go here
function_decl: ID '(' ')' ':' TYPE ... 
function_call: ID '(' arguments ')'
function_call: ID '(' ')'

params: ID ':' TYPE
     | params ',' ID ':' TYPE

arguments: ID
    | arguments ',' ID

Это работает, потому что позволяет анализатору отложить решение между вызовом и объявлением. Парсер LR может отложить принятие решений до тех пор, пока он не уменьшится; он может держать несколько производств открытыми одновременно, но он должен сократить производство, когда достигнет своего конца.

---

Обратите внимание, что даже без конфликта ваша оригинальная грамматика неверна. Как написано, это позволяет arguments (или же params) начинать с произвольного количества запятых. Ваше намерение не было позволить %empty как альтернативный базовый вариант, а скорее как альтернативное полное расширение. Правильная грамматика для необязательного списка через запятую требует двух нетерминалов:

arguments
    : %empty
    | argument_list
argument_list
    : argument
    | argument_list ',' argument