klvov Jun 1 2018 at 12:50

Про LL-парсинг: Подход к синтаксическому анализу через концепцию нарезания строки

10 min

13K

Programming*Algorithms*Compilers*

+12

Comments 6

h0tkey Jun 2 2018 at 10:37

Спасибо за статью. По-моему, у вас получилось довольно хорошее объяснение нисходящего разбора. Ожидал увидеть в статье отсылки к парсер-комбинаторам, потому что их идея очень близка: там парсер — это что-то, что может "откусить" префикс строки и выдать результат и оставшуюся строку, но их ещё и комбинируют, чтобы из простых парсеров (база — один токен) получать более сложные (вплоть до парсера всего языка).

klvov Jun 2 2018 at 16:59

Спасибо. Я так понимаю, вы имеете в виду то, что описано в статье «Функциональные парсеры». Но там, во-первых, все примеры на Gofer (как я понял, примерно то же самое, что Haskell), а во-вторых, это уже продвинутый уровень. Но есть ощущение, что это именно то направление, куда надо двигаться после освоения базовых принципов.

KvanTTT Jun 2 2018 at 12:51

Любопытно. А алгоритм ALL, который используется в ANTLR 4, не думали рассмотреть?

Не увидел в статье терминов LL(1) и LL(*), а ведь первый значительно проще и быстрее. Подходит для простых языков.

klvov Jun 2 2018 at 17:05

Спасибо. Про ANTLR знаю, для третьей версии есть отлично написанная книга самого Теренса Парра, но с чертвертой версией еще не разбирался.

Livid Jun 2 2018 at 17:14

Во-первых, LL-анализ и анализ методом рекурсивного спуска это не одно и то же. Классически, LL-анализ чисто предиктивный, то есть без возвратов. А анализ методом рекурсивного спуска запросто может быть с возвратами. Вы по сути реализовали вариант с возвратами, так что LL тут вообще-то немного ни при чём — это при том, что Ваша грамматика навскидку принадлежит LL(1).

А во-вторых, обработка ошибок разбора у Вас конечно совсем никакая, и никаких гарантий, что при успешном разборе на вход был подан синтаксически корректный текст у Вас нет, в отличие от нормальных анализаторов.

Даже как объяснение "на пальцах" Ваш подход как-то не очень, фишка LL(k) анализа таки как раз в том, что ему не нужно забегать вперёд и искать скажем там парную закрывающую фигурную скобку, за счёт чего достигается линейная скорость разбора. А у Вас ассимптотика в худшем случае квадратичная навскидку (по крайней мере если допустить что значение само может быть набором пар ключ-значение)

klvov Jun 4 2018 at 13:07

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

Самое, конечно, главное уточнение — что LL(...) и рекурсивный спуск — это не одно и то же. Мне они представлялись почти синонимами, а это не так.

Show the best of all time