Пузырьковый вычислитель выражений: простейший синтаксический LR-анализатор вручную

[sshikov]

Не скажу про все курсы, но что касается книги дракона — тут все довольно определенно, она просто не для начинающих, вот и все. Есть книги попроще, где разница между LL и LR вполне доступно объясняется, может и не на пальцах, но и без лишней математики (которая тут реально без надобности). Математика нужна, когда вы пытаетесь построить анализатор из BNF, например, но не для понимания того, как это работает.

Мне в свое время очень понравилась книга авторов Льюис, Розенкранц и Стирнз, Теоретические основы проектирования компиляторов, но были и другие.

[klvov]

Спасибо, заглянул одним глазом. Честно говоря, не показалось, что сильно проще, чем Dragon book, но повеяло таким духом 70-х годов прошлого века ) Впрочем, я сильно внимательно не вчитывался, возможно, она и в самом деле понятнее.

[sshikov]

Ну, первую очередь все-таки Dragon Book сложная, а эта более практическая, если угодно.

[tgz]

Хорошо написано.

[klvov]

Спасибо.

[Comdiv]

Напоследок упомяну про LL-анализ (рекурсивный спуск). Исторически он появился раньше, чем LR, более или менее общим мнением является то, что LL-анализаторы сравнительно просто писать вручную

По-моему, их куда проще написать и понять, чем приведённый Вами код. Я как-то написал в экспериментальных целях вычислитель схожих выражений expression-parser на Go. Сравните, стоило ли обращаться к «пузырьковому вычислителю» вместо рекурсивного спуска?

[klvov]

Да, у вас классический рекурсивный спуск. Для каждого нетерминального символа создается процедура, которая его разбирает.

Насчет «стоило ли» колхозить «пузырьковый вычислитель» — думаю, что все же да, стоило. Потому что задача — проиллюстрировать концепцию LR-разбора, чтобы увидеть, как это — когда разбор происходит на вершине стэка. И чтобы потом более серьезные статьи и книги по теме было легче понимать.

На Go писать не довелось, но как код выглядит — нравится. Очень лаконично, особенно если сравнивать с Java.

[Comdiv]

Если главная цель показать концепцию LR, то да, имело смысл. Не уверен, что получилось так уж просто, но я не знаю как сделать лучше.
Но я понял изначальный посыл, как желание разобраться с синтаксическим разбором в принципе, а не конкретно с LR. А тогда лучше бы начать с более простых вещей.

[sshikov]

LL конечно писать и понимать проще. По большому счету LL(1) — это один небольшой цикл + кучка несложных таблиц (да даже одна таблица, в общем-то).

Но тут дело в другом — не для всякого языка вы сможете вот так вот легко построить грамматику, пригодную для любого разбора. А та грамматика, которую вы нарисуете «из головы», с некоторой вероятностью окажется пригодна для LR, но не для LL, и не для рекурсивного спуска.

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

[Comdiv]

грамматика, которую вы нарисуете «из головы», с некоторой вероятностью окажется пригодна для LR

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

А что до рекурсивного спуска, кстати, то LL (да и LR) строятся по грамматике полностью автоматически, а если рекурсивный спуск ручками писать — вы не гарантированы от ошибок

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

[sshikov]

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