mark_ablov Mar 15 2012 at 19:27

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

7 min

22K

Algorithms*Compilers*

+57

Comments 26

romy4 Mar 15 2012 at 19:57

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

abusalimov Mar 15 2012 at 20:15

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

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

mark_ablov Mar 15 2012 at 20:44

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

abusalimov Mar 15 2012 at 22:52

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

nikitadanilov Mar 15 2012 at 20:32

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

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

mark_ablov Mar 15 2012 at 20:35

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

Halt Mar 16 2012 at 08:13

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

mark_ablov Mar 16 2012 at 08:35

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

UncleAli Mar 15 2012 at 20:41

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

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

mark_ablov Mar 15 2012 at 20:49

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

UncleAli Mar 15 2012 at 20:57

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

mark_ablov Mar 15 2012 at 21:33

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

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

zim32 Mar 15 2012 at 21:49

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

tkirill128 Mar 15 2012 at 22:42

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

knekrasov Mar 16 2012 at 00:21

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

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

Maccimo Mar 18 2012 at 04:28

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

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

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

tkirill128 Mar 18 2012 at 11:30

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

UFO just landed and posted this here

OdobenusRosmarus Mar 16 2012 at 03:53

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

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

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

mark_ablov Mar 16 2012 at 06:19

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

Halt Mar 16 2012 at 08:15

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

burjui Mar 16 2012 at 14:47

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

mark_ablov Mar 16 2012 at 14:57

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

8bitjoey Mar 16 2012 at 14:39

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

FireStorm Mar 17 2012 at 23:11

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

olegdunkan Mar 17 2012 at 12:19

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