Написание компилятора LALR(1)-парсеров. Базовая теория

[@romy4]

Занятно, но что-то толкове откоментировать получится лишь после второй части, когда можно будет сравнить.

[@abusalimov]

Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров.

А какие генераторы вы рассматривали, и чем именно, если не секрет, они вам не подошли? Ничего не имею против самой статьи, просто интересна мотивация писать парсер с нуля.

[@mark_ablov]

Расскажу в следующей части :)
В общем-то рассматривал я все популярные — ANTLR, bison, Coco/R, Lemon, boost::spirit, GOLD, sablecc + еще парочка, которые не остались в моей памяти.

[@abusalimov]

Спасибо, значит, буду ждать следующую часть. )

[@nikitadanilov]

Зачем же нужен лексический анализатор, если он фактически может быть интегрирован в синтаксическую часть?

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

[@mark_ablov]

Это решаемо, но опять же плодится огромное число лишних листьев.
Так что полностью согласен.

[@Halt]

Я бы еще написал про возможность преобразования деревьев в LR. Скажем в ANTLR мне очень понравились правила преобразования «на лету», когда из второго вашего дерева в примере можно сразу получить ADD(12, 34). Работать с таким деревом гораздо приятнее (ничего лишнего).

[@mark_ablov]

Это не преобразование дерева вывода (prase tree), а построение новой сущности AST, abstract syntax tree. Это более высокоуровневая конструкция, которая слабо зависит от грамматики, если prase tree полностью опирается на грамматику, и имеет четкие правила построения (узел — нетерминал левой части, дочерние элементы — символы правой части). Тогда как в AST мы сами задаём формат, который может вообще не опираться ни на какие символы и правила.
Да, я не забыл про это, но я боялся написать слишком много — мало кто захочет читать такую простыню, пусть и немного разбавленную кодом и картинками :)
Вообще изначально планировал уместить всё в одну статью, но вовремя заметил то что объем увеличивается очень быстро. Что удивило меня весьма, ибо вроде воду не лью и стараюсь излагать лаконично.

[@UncleAli]

> интеграция семантической логики напрямую в синтаксический анализатор, минуя стадию построения дерева
> Заметно то, что сложную грамматику так не описать

Достаточно спорное утверждение. Простыню кода можно спрятать в вызов функции.

[@mark_ablov]

Я опираюсь на свой опыт.
В частности мне нужно было встретив в дерево продукцию X,, у которой терминал a принимал определенное значение, пробежаться по дереву вверх до одной из родительских продукций.
Если честно, то как это сделать без дерева, я не представляю.
И таких ситуаций было больше одной, и даже больше десятка.

[@UncleAli]

Разработчик может самостоятельно поддерживать дерево. Понятно, что если генератор парсера это делает за разработчика, то это круто. Но возникает вопрос: а если разработчику нужно чуть другая структура данных, а текущая структура наглухо прописана в годе генератора?

[@mark_ablov]

> Но возникает вопрос: а если разработчику нужно чуть другая структура данных, а текущая структура наглухо прописана в годе генератора?

Я думаю, начав статью («Написание компилятора LALR(1)-парсеров»), ответил на этот вопрос? :)
Это была одна из причин разработки велосипеда.

[@zim32]

Спасибо. Но я видел довольно много постов про основы. А вот практическое построение синтаксического дерева разбора и последующий проход и компиляция — это было бы очень интересно почитать.

[@tkirill128]

Интересно будет почитать продолжение. Я сейчас активно мучаю ANTLR в дипломном проекте, переехал на него после связки bison+flex. Очень волнует вопрос: а есть ли спрос на знания в области обработки языков? Я периодически просматриваю вакансии и ещё ничего даже близко похожего не нашёл.

[@knekrasov]

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

У меня кстати тоже курсовые работы были посвящены ANTLR и формальным языкам. Интересное было время. Сейчас им занимаюсь уже в качестве хобби.

[@Maccimo]

Расскажите, что такого у вас в дипломном проекте, для чего не хватило bison+flex? Я теряюсь в догадках.

а есть ли спрос на знания в области обработки языков? Я периодически просматриваю вакансии и ещё ничего даже близко похожего не нашёл.

Спрос есть, а вот насколько он велик — вопрос открытый. Большинство вакансий на рынке — унылый ынтырпрайз и никакой обработки языков, увы.
Поищите вакансии на сайтах компаний-разработчиков различных IDE, там без этого никуда.

[@tkirill128]

С точки зрения самого разбора ничего такого что мешало бы использовать bison+flex нет. ANTLR выбрал за родную поддержку Python, да и большую роль сыграл фактор «почему бы и нет» :)

[@VAK_53]

Что-нибудь изменилось с того времени?
PS Я ищу информацию и собираюсь писать для себя интерпретатор FORTH.

[@OdobenusRosmarus]

у меня задача синтаксического анализа одной грамматики. Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров.

То есть у Вас была задача анализа одной грамматики, и Вы начали с написания своего генератора парсеров?

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

[@mark_ablov]

> и Вы начали с написания своего генератора парсеров?
Не, я начал с того что примерно неделю пытался допиливать существующие решения.
А написание своего у меня заняло 3 дня.
Выгода во времени вроде очевидна?

[@Halt]

Довольно спорное рассуждение. Берем Bison/Flex либо ANTLR и имеем профит.

[@burjui]

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

[@mark_ablov]

Конечно, вполне возможно меня будут тыкать в более правильные варианты разработки без своего парсера :)

[@8bitjoey]

Для интересующихся темой, возможно, будут интересны следующие статьи:
habrahabr.ru/blogs/programming/99162/
habrahabr.ru/blogs/programming/99298/
habrahabr.ru/blogs/programming/99366/
habrahabr.ru/blogs/programming/99397/
и прочие из серии. На данный момент насчитывается 10 частей.

[@FireStorm]

Тёмыч отличные статьи написал по синтаксическому анализу и компиляторам.

[@olegdunkan]

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