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

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

0 голосов
/ 28 февраля 2019

Я использую Bison (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()).

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

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

1 Ответ

0 голосов
/ 01 марта 2019

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

Вы совершенно правы, что конфликт является результатом как 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
...