Как стать автором
Обновить

Комментарии 36

Спасибо за ссылку. В начале первой части рассказал о своих мотивах - размять мозг, вспомнить C/C++, на котором не писал 18 лет (после Java). Для такой цели использовать генераторы смысла нет.

Хорошо разминает мозг составление BNF (https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form) — декларативно опишите кто есть кто, а в дополнение получите возможность сгенерировать по этому парсер. Даже если хотите написать парсер сами, BNF не будет лишней (говорю, т.к. имею опыт написания своей маленькой стековой машины и недоязыка)

Спасибо за наводку! Почитал про BNF и EBNF (слышал в студенчестве, но не вникал). Действительно, хорошо упорядочивает мысль такое формальное описание языка на примере ANSI C: https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm

Сразу наглядно видно все упущения и неопределённости моей реализации.

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

Да, я в самом начале процесса изучения современного C++ и многого о языке просто не знаю (smart pointers) - скатываюсь в C. По мере изучения новых (для меня) возможностей постараюсь переписать почище. Спасибо.

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

В ущерб ещё и лёгкости модификаций: добавил новую конструкцию в язык — нужно менять код в 100500 разных неочевидных местах.

Вам может быть любопытно, что в CPython до 3.9 был рукописный парсер, но к прошлом году с ним все настолько залюбились, что заменили на сгенерированный.
В ущерб ещё и лёгкости модификаций: добавил новую конструкцию в язык — нужно менять код в 100500 разных неочевидных местах.

Это смотря как парсер написать и что это за новая конструкция будет. Как правило, «архитектура» транслятора довольно четко разделяется на этапы и структуры, даже на Си. Например, если новая конструкция языка — синтаксический сахар, то затрагивать структуру AST не придется и можно обойтись только новым кодом непосредственно в парсере.


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


К слову —


Вам может быть любопытно, что в CPython до 3.9 был рукописный парсер ...

и он был, по моему скромному мнению, просто ужасен. С точки зрения реализации конечно, поскольку это был не просто парсер, а самодельный генератор LL-парсера по файлу грамматики. Так что, хорошо что они перешли на нормальный генератор.

и он был, по моему скромному мнению, просто ужасен. С точки зрения реализации конечно, поскольку это был не просто парсер, а самодельный генератор LL-парсера по файлу грамматики.

Он был ещё ужаснее, чем вы думаете, потому что кроме сгенерированной части была и полностью рукописная — наглядная демонстрация, во что превращается рукописный парсер за 20+ лет развития языка сотнями независимых людей.

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

Более того, это только транслятор из CST в AST — следствие использования изначально неправильного рукописного генератора.


Clang вдвое моложе CPython; интересно будет посмотреть на их парсер лет через десять.

Вроде как язык С не так часто меняется. Хотя кто знает, что нас ждет через 10 лет. Поживем увидим.

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

А для своего DSL, с более-менее строгим синтаксисом, ввод фичи потребует примерно столько же правок, что с грамматикой, что без. Считаем:
— завести новый тип ноды в AST,
— сделать компиляцию синтаксиса в эту ноду,
— сделать новые опкоды VM и учесть их в трансляторе AST,
— добавить обработку новых опкодов в интерпретатор VM/JIT.
Разница есть только на шаге 2. Ручной парсер — это плюс 10-15 строчек, с идеальной обработкой ошибок и т.п.
Для автоматического парсера недостаточно добавить 1 строку в грамматику: нужны и вспомогательные ф-ции для генерации узла AST, и обработка ошибок. По строчкам кода выйдет так же.

Бесспорный плюс подхода с грамматиками: бесплатно получаем документацию синтаксиса, абсолютно точную и актуальную. С ручным парсером придётся вести её где-то отдельно.

Вы некорректно оперировали терминами, приведёнными в статье:


Задача простая — "нарубить" массив символов (исходный код) на список классифицированных токенов, чтобы последующий разбор и компиляция не вызывали сложности.

Это задача лексического анализа, а не синтаксического, соответственно то, что вы обозвали парсером, на деле является лексером.


Задача синтаксического анализа заключается в том, чтобы определить образует ли последовательность полученных токенов предложение в заданной грамматике языка.
Как уже писали, советую составить грамматику в РБНФ и почитать про метод рекурсивного спуска. Это по сути разработка синтаксического анализатора через переписывание грамматики на языке программирования.

Я взглянул на код автора заметки — де-факто выражение разбирается рекурсивным спуском (технически рекурсии, впрочем, пока нет — она появится, когда автор реализует скобки — когда VMCompiler::parseFactor начнёт вызывать VMCompiler::parseExpression для обработки выражения в скобках), простая грамматика выражений понятна из кода — конечно, выписать её полезно. Выделение фазы синтаксического анализа нет, это — однопроходный компилятор.


Меня больше расстраивает, что автор пишет на смеси некоторых элементов современного C++ (constexpr, enum class) и низкоуровневого C (везде указатели, не ссылки, рискованная адресная арифметика, невнятные отношения владения без смартпойнтеров — сырой указатель на вектор токенов tokens, пары указатель / длина) — не понятна цель упражнения "вспомнить C/C++", зачем это вспоминать, можно же писать более чисто и безопасно на современном C++. Жалко.

Спасибо за комментарий! Действительно смесь C и C++ - "дикая". Всё банально - я просто этого не знал. Теперь хоть пойму что изучать, почитаю и перепишу почище.

Отлично! У меня (пишу на C++ на работе) под рукой пара рекомендаций (я сам стараюсь быть в курсе развития языка, хотя именно на работе далеко не всегда имеется возможность применить те или иные улучшения):


https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines — живой, развивающийся документ, рекомендации от ведущих специалистов комитета стандартизации.


https://github.com/changkun/modern-cpp-tutorial — учебник по основным новым фичам, появившимся в последних 4-х итерациях стандарта.


Есть пара очень недавно вышедших книг (у одной автор Slobodan Dmitrović, у другой Jason Turner), не могу уверенно рекомендовать, так как сам не прочитал, листал только.


Оговорюсь, что может показаться, что стремление использовать новые возможности языка — сходна к желанию поиграть в новые блестящие игрушки. Это не совсем так! Изменения и нововведения делаются для решения определённых проблем, они действительно полезны в долгосрочной перспективе. Документ Cpp Core Guidelines иногда объясняет смысл нововведений, я часто в него заглядываю по практической нужде.

Можно страуструпа перечитать, и Майерса (в плюсах это мастхэв, у него и по современным фичам есть книги)

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

Да, есть неправильное применение терминов. Исправлю.

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

Всё же не «определить образует ли» — от булева ответа никакой пользы нет — а построить дерево разбора.
НЛО прилетело и опубликовало эту надпись здесь
Исправил термины, добавил иллюстрации. Спасибо за комментарий.
Тоже делал что-то подобное, но у меня был ещё одно промежуточное представление: AST, из которого уже генерировались опкоды, а не напрямую из вектора токенов. Наверное, вы к этому придёте, когда будет компилировать операторы типа if/while, а не только арифметические выражения.

Начинать с грамматики лучше, явно выписать ее. Потом только парсер подбирать, лучше готовым движком воспользоваться. Раз пишете на плюсах, возьмите flex+bison, он удобен, хоть и древний.

Для типичной задачи компилятора — создания AST — довольно много кода придётся писать руками. Мне не понравилось, как это выглядит — C++ код для создания нод синтаксического дерева и их связывания вперемежку с правилами грамматики. Дебажить это (а придётся, т.к. пишется много ручного кода) то ещё удовольствие.

Вот если бы создание AST описывалось полностью декларативно и привязывалось к грамматике… Но такого генератора нет?
Есть, почитайте маны к bison-у. Там к каждому правилу грамматики можно (и по факту нужно) дописать код, который выполняет свертку физически и формирует узел AST
Обычно сильно перемешивается си-код и грамматика, например тут, это ужасно выглядит.

Хотя я нашёл более-менее читаемый вариант.

Ещё момент, который не понравился с bison. Ручной парсер может выдавать очень подробные, информативные ошибки. Например, «в строке 75 в столбце 12 для оператора if ожидается булевское выражение, а найдено строковое». Парсеры по грамматике могут только сказать «извините, входной текст не соответствует грамматике, идите на фиг».
Ну то, что авторы примера не умеют писать нормальный код, не говорит об инструменте плохо. Мы в 2013м году по-моему просто писали статические функции для свертки, и прописывали их вызов в файле грамматики, код смотрелся красиво и аккуратно. Про предупреждения об ошибках — вы тоже не правы, там раздел целый вроде был про это, все прекрасно можно сделать.

Если вам нравится разделять код и грамматику, то смотрите про ANTLR. Единственное — он адаптированный LL-ный, а значит, более капризный, в то время как bison — это честный LALR(1), значит он ест больше грамматик, и неоднозначные (в которых есть конфликты типа сдвиг/свертка, например) — в том числе
Но это всё далеко не бесплатно.
Откуда парсер узнает, что если зашёл в if, то откатываться из этого правила уже нельзя? Какая-то разметка в грамматике?
Откуда парсер узнает, что для if допустимы только bool-expressions и выдаст соответствующую ошибку?
Как-то так?
STMT: IF '(' INT_EXPR ')' { error("int expression in if, expected boolean"); }
| IF '(' STR_EXPR ')' { error("string expression in if, expected boolean"); }
| IF '(' BOOL_EXPR ')' OP { $$ = new ifop($3, $5); }

То есть, загаживаем грамматику ради подробной диагностики?

Справедливости ради, такие проверки можно делать на другом этапе трансляции — анализа. Иметь дело с готовым деревом при ручной обработке проще. Кроме того, на этом же этапе можно сразу разрешать таблицу символов, выводить типы и даже производить какие-никакие оптимизации.

Да, можно. Но это будет та же ручная работа.
А мы хотим декларативно описать как можно больше.

Кроме того, у bool- и int-expressions могут быть разные разрешённые синтаксические конструкции, потому есть смысл, чтобы парсер знал о типах.
Я в 2010 постил на хабр туториал по созданию при помощи bison игрушечного компилятора в нативный код: habr.com/ru/post/99397

Грамматика вместе с кодом построения AST получалась такой
PROGRAM: OPS                            // обработка дерева программы
;

OPS:    OP                              // inherit
|       OPS OP                          { $$ = new block($1, $2); }
;

OP1:    '{' OPS '}'                     { $$ = $2; }
|       EXPR ';'                        { $$ = new exprop($1); }
|       IF '(' EXPR ')' OP1 ELSE OP1    { $$ = new ifop($3, $5, $7); }
|       WHILE '(' EXPR ')' OP1          { $$ = new whileop($3, $5); }
|       EXIT ';'                        { $$ = new exitop(); }
;

OP2:    IF '(' EXPR ')' OP              { $$ = new ifop($3, $5, new block()); }
|       IF '(' EXPR ')' OP1 ELSE OP2    { $$ = new ifop($3, $5, $7); }
|       WHILE '(' EXPR ')' OP2          { $$ = new whileop($3, $5); }
;

OP:     OP1 | OP2 ;                     // inherit

EXPR:   EXPR1                           // inherit
|       ID '=' EXPR                     { $$ = new assign($1, $3); }

EXPR1:  EXPR2                           // inherit
|       EXPR1 EQ EXPR2                  { $$ = new binary("==", $1, $3); }
|       EXPR1 LE EXPR2                  { $$ = new binary("<=", $1, $3); }
|       EXPR1 GE EXPR2                  { $$ = new binary(">=", $1, $3); }
|       EXPR1 NE EXPR2                  { $$ = new binary("!=", $1, $3); }
|       EXPR1 '>' EXPR2                 { $$ = new binary(">", $1, $3); }
|       EXPR1 '<' EXPR2                 { $$ = new binary("<", $1, $3); }
;

EXPR2:  TERM                            // inherit
|       EXPR2 '+' TERM                  { $$ = new binary("+", $1, $3); }
|       EXPR2 '-' TERM                  { $$ = new binary("-", $1, $3); }
;

TERM:   VAL                             // inherit
|       TERM '*' VAL                    { $$ = new binary("*", $1, $3); }
|       TERM '/' VAL                    { $$ = new binary("/", $1, $3); }
;

VAL:    NUM                             { $$ = new value($1); }
|       '-' VAL                         { $$ = new unary("-", $2); }
|       '!' VAL                         { $$ = new unary("!", $2); }
|       '(' EXPR ')'                    { $$ = $2; }
|       ID                              { $$ = new value($1); }
|       ID '(' ARGS ')'                 { $$=new funcall($1, $3); }
;

ARGS:                                   { $$.clear(); }
|       ARG                             { $$.clear(); $$.push_back($1); }
|       ARGS ',' ARG                    { $$ = $1; $$.push_back($3); }
;

ARG:    EXPR                            // inherit
|       STRING                          { $$=new value('"'+replaceAll($1, "\n", "\\n")+'"'); }
;

По-моему, всё вполне прозрачно, никакой мешанины.
Спасибо! И опять же, ждем продолжения! :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации