LR(1) сдвиг / уменьшение неоднозначности

Question

Заданный ввод с повторением BLOCKс, где каждый блок имеет повторяющиеся BEGIN EVENT а также END EVENT записи (END EVENT всегда следует за BEGIN EVENT):

[TIMESTAMP] BLOCK
[TIMESTAMP] BEGIN EVENT
[TIMESTAMP] END EVENT
[TIMESTAMP] BEGIN EVENT
[TIMESTAMP] END EVENT
...
[TIMESTAMP] BLOCK

Как вы устраните неоднозначность этой грамматики с помощью LR(1)? Я использую LALRPOP, и минимальный пример этого:

Timestamp = "[TIMESTAMP]";
BlockHeader = Timestamp "BLOCK";
Begin = Timestamp "BEGIN" "EVENT";
End = Timestamp "END" "EVENT";

Block = BlockHeader (Begin End)+;
pub Blocks = Block*

Поскольку LR (1) может смотреть вперед только на один токен, эта грамматика неоднозначна, как подсказывает вам LALRPOP (частичная ошибка):

Local ambiguity detected

  The problem arises after having observed the following symbols in the input:
    BlockHeader (Begin End)+
  At that point, if the next token is a `"[TIMESTAMP]"`, then the parser can proceed in two different ways.

  First, the parser could execute the production at
  /home/<snip>.lalrpop:51:9: 51:32, which would consume
  the top 2 token(s) from the stack and produce a `Block`. This might then yield a parse tree like
    BlockHeader (Begin End)+ Block
    ├─Block────────────────┤     │
    ├─Block+───────────────┘     │
    └─Block+─────────────────────┘

  Alternatively, the parser could shift the `"[TIMESTAMP]"` token and later use it to construct a
  `Timestamp`. This might then yield a parse tree like
    (Begin End)+ "[TIMESTAMP]" "BEGIN" "EVENT" End
    │            ├─Timestamp─┘               │   │
    │            └─Begin─────────────────────┘   │
    └─(Begin End)+───────────────────────────────┘

Я вижу, что он говорит мне, что после анализа BlockHeader, Begin и End он не может определить, является ли следующий токен другим Begin или началом другого блока. Я не нашел способа устранить это в LR(1), но я могу только предположить, что это отсутствие понимания с моей стороны, а не наследственное ограничение грамматик LR(1)?

Answer 1

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

Timestamp = "[TIMESTAMP]";
BlockHeader = Timestamp "BLOCK";
Begin = Timestamp "BEGIN" "EVENT";
End = Timestamp "END" "EVENT";
Event = Begin End;
Item = BlockHeader | Event;
pub Input = Item*

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

Альтернативный вариант, когда требуемый упуск является небольшим и ограниченным, состоит в том, чтобы иметь дело с этим в вашем токенизаторе. Я не знаком с LALRPOP, но должна быть возможность "объединить" [TIMESTAMP] токены с непосредственно следующими ключевыми токенами (так что временные метки не будут присутствовать в грамматике, а просто являются атрибутом ключевых слов), и в этом случае все будет хорошо работать с одним токеном.