Лимонный парсер уменьшить ошибку

Я пытаюсь написать грамматику для разбора чисел в английских предложениях, и я могу успешно разобрать до 999. Как только я добавляю логику для поддержки тысяч, я получаю reduce Разбор конфликта, и мне трудно понять, что его вызывает.

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

Я думаю, что я сталкиваюсь с проблемой, похожей на "болтаться еще", но с моим разделителем. Тем не менее, это обычно проявляется как shift-reduce ошибка, тогда как, похоже, у меня есть только reduce ошибка. Документация по Lemon немного скудна, и я не совсем уверен, как читать содержимое файла parser.out. Например, в строке HYPHEN reduce 15 ** Parsing conflict **, что это 15 даже сослаться на?

Любая помощь будет принята с благодарностью!

Часть моего файла грамматики:

final_number(A) ::= one_to_999999(B).
final_number(A) ::= ZERO.

one_to_999999(A) ::= thousands(B) separator one_to_999(C).
one_to_999999(A) ::= thousands(B).
one_to_999999(A) ::= one_to_999(B).

thousands(A) ::= one_to_999(B) separator THOUSAND.
thousands(A) ::= THOUSAND.

/* -------------------------------------- */

one_to_999(A) ::= hundreds(B) separator one_to_99(C).
one_to_999(A) ::= hundreds(B).
one_to_999(A) ::= one_to_99(B).

one_to_99(A) ::= tens(B) separator one_to_9(C).
one_to_99(A) ::= tens(B).
one_to_99(A) ::= ten_to_19(B).
one_to_99(A) ::= one_to_9(B).

hundreds(A) ::= one_to_9(B) separator HUNDRED.
hundreds(A) ::= HUNDRED.

separator ::= WHITESPACE.
separator ::= HYPHEN.
separator ::= .

Часть parser.out с ошибкой:

State 5:
          one_to_99 ::= tens * separator one_to_9
     (15) one_to_99 ::= tens *
          separator ::= * WHITESPACE
          separator ::= * HYPHEN
     (65) separator ::= *

                             $ reduce       15     one_to_99 ::= tens
                      THOUSAND reduce       15     one_to_99 ::= tens
                    WHITESPACE shift-reduce 63     separator ::= WHITESPACE
                    WHITESPACE reduce       15      ** Parsing conflict **
                        HYPHEN shift-reduce 64     separator ::= HYPHEN
                        HYPHEN reduce       15      ** Parsing conflict **
                     separator shift        4      
                     {default} reduce       65     separator ::=
Источник

1 ответ

Решение

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

Это означает, что проблема в том, что синтаксический анализатор распознал tens (это было бы "двадцать", "тридцать", ..., "девяносто", верно?) и теперь нужно separator (что может быть необязательным). Если маркер предпросмотра является фактическим разделителем, он должен решить, следует ли уменьшить tens немедленно one_to_99 (как прелюдия к завершению one_to_999 без запятой) или сдвиньте WHITESPACE или же HYPHEN символ для того, чтобы расширить tens с separator и одна цифра (one_to_9).

Парсер действительно не может принять такое решение, просто взглянув на маркер-разделитель. Необходимо знать, что следует (например, THOUSAND или же ONEсреди других возможностей).

Этого не происходит до того, как вы добавите тысячи к грамматике, потому что без возможности THOUSAND, если в конце номера нет ни одной цифры, разделитель после tens токен тоже. Так что, если есть явный разделитель, то должна быть цифра, и, следовательно, требуется смещение. Как только вы добавите THOUSAND Опция существования токена разделителя больше не является адекватным руководством.

Попытка явно сопоставить пробел в парсере похожа на то, что обычно называют "синтаксическим анализом без сканера", хотя здесь это не совсем так, поскольку у вас, вероятно, действительно есть сканер. Однако сканер не выполняет свою работу должным образом; он не может отбросить токены, которые не имеют синтаксического значения. В то время как есть люди, которым нравится анализ без сканера, все согласны с тем, что он имеет тенденцию повышать требования к будущему. [Примечание 1] Поскольку вы не можете увеличить время ожидания для анализатора лимона (как и для многих других генераторов синтаксического анализатора на основе yacc), анализ без сканера проблематичен с такими инструментами.

В этом случае трудно понять, что вы можете получить, заставив синтаксический анализатор работать с разделителями, и очевидно, что вы потеряли (LALR(1) parsability), поэтому я рекомендую вам просто удалить пробелы и дефисы на полу в вашем сканере, и удалите их из вашего анализатора. Вы можете утверждать, что это допустит неправильные предложения, такие как three hundred forty---two, Это правда, но ваша нынешняя грамматика позволяет three hundred-forty two (что неправильно в любом руководстве по стилю, которое я когда-либо видел), и может запретить forty - twoв зависимости от того, какой шаблон ваш сканер использует для распознавания дефисов.

Если вы хотите быть "дефис-корректными", непременно верните дефисы (но не пробелы) с вашего сканера, а затем принимайте их только там, где это полезно:

one_to_99 ::= tens
            | tens one_to_9
            | tens HYPHEN one_to_9
            ;

что не приведет к сдвигу / уменьшению конфликтов.

Заметки

  1. Я не из тех, кто любит разбор без сканера, поэтому я даже не буду пытаться объяснить, почему это считается хорошей идеей.
Источник
Другие вопросы по тегам