LINUX.ORG.RU

Parser combinators и LL(2)

 ,


0

1

Здравствуйте!

Можно ли совместить LL(1)/LL(2) парсеры и parser combinators?
Или это невозможно?

Насколько я понимаю, допустим, LL(2) парсер имеет lookahead = 2, т.е. он может смотреть на 2 токена вперед (кстати, что есть токен в данном случае - один символ или именно целый токен?).
Это сильно ограничивает backtracking (нельзя, например, прочитать 10 токенов, подумать, а потом откатиться назад).
А без backtracking'а по сути не будут работать многие parser combinators, да? Например, комбинатор `and`: допустим, он распарсил успешно 5 токенов, а на 6м зафейлил, следовательно, вся цепочка должна зафейлиться, но откатить 5 токенов мы уже не можем.
Или parser combinators являются LL(infinity) парсерами?
Можно ли сделать parser combinators поверх потоков (streams)?

★★★★★

Если ты разделяешь лексер и парсер, то в твоем случае токен—это конечно какое-то «слово».

Комбинаторы с классическими LL(k) кмк не стыкуются. Поверх потоков делать можно, если дать потоку свойство восстановления какой-то позиции, т.е. ты сделал предположение, распарсил, неудача, восстанавливаешь лексер в прежнее состояние, делаешь следующее предположение и т.д. Тут для потокового лексера напрашивается оптимизация по хранению infinity-кеша известных лексем.

staseg ★★★★★ ()
Ответ на: комментарий от staseg

Ничто не мешает сбрасывать кеш в top-level комбинаторе, но это все равно не сделает его не-infinity.

staseg ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.