AFAIK, Happy это LALR (1) парсер. Ну, моя грамматика LALR (1) ... в основном. К сожалению, есть один конфликт уменьшения-уменьшения, который я (глупый я) заметил слишком поздно, когда большая часть кода, связанного с Happy, уже была написана.
Правило, которое является виновником, выглядит так:
Symbol : Nonterm1 Nonterm2 Nonterm3
| Nonterm3
Проблема в том, что Nonterm1 и Nonterm3 - хотя и не одинаковы - все еще достаточно похожи, чтобы вызвать конфликты уменьшения-уменьшения. Может быть Я мог бы переписать их таким образом, чтобы устранить эти конфликты, но, поскольку они оба довольно сложны, я не думаю, что я справлюсь с задачей (для этого потребуется значительное количество дублирования, Я полагаю).
С другой стороны, Nonterm2 достаточно прост - он всегда сводится к одному символу (а именно :), который не появляется ни в Nonterm1, ни в Nonterm3.
Следовательно, единственное изменение, необходимое для избавления от конфликтов уменьшения-уменьшения, это:
Symbol : Nonterm1 Nonterm2 Nonterm3
| Nonterm2 Nonterm3
Это работает, но ... мне это не нравится. Требуется загромождать входные файлы с : в довольно неловких местах.
Я верю, что грамматика однозначна даже в том виде, в котором она была изначально написана. Конфликты уменьшения-уменьшения могут быть устранены вручную, по крайней мере, двумя способами:
- Посмотрите в будущее и посмотрите, стоит ли двоеточие или любой другой символ, который не может появиться в
Nonterm1, на первом месте. Если это двоеточие, вернитесь назад и уменьшите до Nonterm1 Nonterm2 Nonterm3. В противном случае уменьшите до Nonterm3.
- Просто попробуйте любое из этих двух правил. Если разбор успешен, он был правильным. В противном случае вернитесь и попробуйте другой.
Есть ли в Happy функция, которая бы помогла в этом случае? Помогут ли монадические парсеры, упомянутые в их документации? Или это время для использования GLR? Но я прочитал в их документах, что GLR для неоднозначных грамматик, чтобы позволить возвращать много возможных разборов; но моя грамматика, я думаю, однозначна.