Комментарии 36
en.wikipedia.org/wiki/Comparison_of_parser_generators
Спасибо за ссылку. В начале первой части рассказал о своих мотивах - размять мозг, вспомнить 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++ программисты, такой стиль может их озадачить.
А почему нет? Недавно интересовался внутренностями языка Gravity, в нем компилятор полностью написан вручную. По моему там все просто и логично. А главное, такой подход дает больше контроля над выходными структурами, обработкой ошибок и всем процессом в целом. Но да, в ущерб затраченному времени конечно.
Вам может быть любопытно, что в 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 иногда объясняет смысл нововведений, я часто в него заглядываю по практической нужде.
Можно страуструпа перечитать, и Майерса (в плюсах это мастхэв, у него и по современным фичам есть книги)
Да, есть неправильное применение терминов. Исправлю.
Задача синтаксического анализа заключается в том, чтобы определить образует ли последовательность полученных токенов предложение в заданной грамматике языка.
Всё же не «определить образует ли» — от булева ответа никакой пользы нет — а построить дерево разбора.
Начинать с грамматики лучше, явно выписать ее. Потом только парсер подбирать, лучше готовым движком воспользоваться. Раз пишете на плюсах, возьмите flex+bison, он удобен, хоть и древний.
Вот если бы создание AST описывалось полностью декларативно и привязывалось к грамматике… Но такого генератора нет?
Хотя я нашёл более-менее читаемый вариант.
Ещё момент, который не понравился с bison. Ручной парсер может выдавать очень подробные, информативные ошибки. Например, «в строке 75 в столбце 12 для оператора if ожидается булевское выражение, а найдено строковое». Парсеры по грамматике могут только сказать «извините, входной текст не соответствует грамматике, идите на фиг».
Если вам нравится разделять код и грамматику, то смотрите про 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); }То есть, загаживаем грамматику ради подробной диагностики?
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")+'"'); }
;
По-моему, всё вполне прозрачно, никакой мешанины.
andreaferretti.github.io/factor-tutorial
rosettacode.org/wiki/Category:Factor
Разработка стековой виртуальной машины и компилятора под неё (часть II)