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

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

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

Заданный ввод с повторяющимися 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)?

1 Ответ

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

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

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

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

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

...