Pull to refresh

Comments 26

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

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

Можно добавить, что без отдельного лексического анализатора, грамматика будет явно содержать whitespace между токенами, что очень неудобно. Lexer же удаляет пробелы и комментарии.
Это решаемо, но опять же плодится огромное число лишних листьев.
Так что полностью согласен.
Я бы еще написал про возможность преобразования деревьев в LR. Скажем в ANTLR мне очень понравились правила преобразования «на лету», когда из второго вашего дерева в примере можно сразу получить ADD(12, 34). Работать с таким деревом гораздо приятнее (ничего лишнего).
Это не преобразование дерева вывода (prase tree), а построение новой сущности AST, abstract syntax tree. Это более высокоуровневая конструкция, которая слабо зависит от грамматики, если prase tree полностью опирается на грамматику, и имеет четкие правила построения (узел — нетерминал левой части, дочерние элементы — символы правой части). Тогда как в AST мы сами задаём формат, который может вообще не опираться ни на какие символы и правила.
Да, я не забыл про это, но я боялся написать слишком много — мало кто захочет читать такую простыню, пусть и немного разбавленную кодом и картинками :)
Вообще изначально планировал уместить всё в одну статью, но вовремя заметил то что объем увеличивается очень быстро. Что удивило меня весьма, ибо вроде воду не лью и стараюсь излагать лаконично.
> интеграция семантической логики напрямую в синтаксический анализатор, минуя стадию построения дерева
> Заметно то, что сложную грамматику так не описать

Достаточно спорное утверждение. Простыню кода можно спрятать в вызов функции.
Я опираюсь на свой опыт.
В частности мне нужно было встретив в дерево продукцию X,, у которой терминал a принимал определенное значение, пробежаться по дереву вверх до одной из родительских продукций.
Если честно, то как это сделать без дерева, я не представляю.
И таких ситуаций было больше одной, и даже больше десятка.
Разработчик может самостоятельно поддерживать дерево. Понятно, что если генератор парсера это делает за разработчика, то это круто. Но возникает вопрос: а если разработчику нужно чуть другая структура данных, а текущая структура наглухо прописана в годе генератора?
> Но возникает вопрос: а если разработчику нужно чуть другая структура данных, а текущая структура наглухо прописана в годе генератора?

Я думаю, начав статью («Написание компилятора LALR(1)-парсеров»), ответил на этот вопрос? :)
Это была одна из причин разработки велосипеда.
Спасибо. Но я видел довольно много постов про основы. А вот практическое построение синтаксического дерева разбора и последующий проход и компиляция — это было бы очень интересно почитать.
Интересно будет почитать продолжение. Я сейчас активно мучаю ANTLR в дипломном проекте, переехал на него после связки bison+flex. Очень волнует вопрос: а есть ли спрос на знания в области обработки языков? Я периодически просматриваю вакансии и ещё ничего даже близко похожего не нашёл.
Подозреваю, что в вакансиях вы такого почти наверняка и не найдете. Хотя знания эти очень полезны и могут сослужить добрую службу в самых неожиданных местах. Равно как и знание основ вычмата и прочих смежных к программированию дисциплин.

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

а есть ли спрос на знания в области обработки языков? Я периодически просматриваю вакансии и ещё ничего даже близко похожего не нашёл.
Спрос есть, а вот насколько он велик — вопрос открытый. Большинство вакансий на рынке — унылый ынтырпрайз и никакой обработки языков, увы.
Поищите вакансии на сайтах компаний-разработчиков различных IDE, там без этого никуда.
С точки зрения самого разбора ничего такого что мешало бы использовать bison+flex нет. ANTLR выбрал за родную поддержку Python, да и большую роль сыграл фактор «почему бы и нет» :)
UFO landed and left these words here
у меня задача синтаксического анализа одной грамматики. Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров.


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

При всем уважении, у Вас узкий кругозор. Надо было начинать с написания своей операционной системы.
> и Вы начали с написания своего генератора парсеров?
Не, я начал с того что примерно неделю пытался допиливать существующие решения.
А написание своего у меня заняло 3 дня.
Выгода во времени вроде очевидна?
Довольно спорное рассуждение. Берем Bison/Flex либо ANTLR и имеем профит.
Надеюсь, вы расскажете, что и как вам нужно парсить — всем, кто разбирается в теме, интересно, почему вам не хватает существующих решений.
Конечно, вполне возможно меня будут тыкать в более правильные варианты разработки без своего парсера :)
Тёмыч отличные статьи написал по синтаксическому анализу и компиляторам.
мне бы в этой статье было бы интереснее узнать почему существующие решения не подходили, я думаю если на то действительно существовали причины, то они могли бы вызвать живой интерес, ну если конечно эти причины вызваны не убеждениями или нежеланием, а конкретными предметными вещами.
Only those users with full accounts are able to leave comments. Log in, please.