Нужны ли компиляторам универсальные парсеры?

Ну, clang/swift это просто проги, которые используют фреймворк llvm. В llvm уже как свои утилиты и кишки для создания парсеров/лексеров/оптимизаторов и причём чуть ли не многоуровневых. Там (с этим llvm) можно упороться и написать шо хошь пр желании, при этом llvm в активной разработке. Это я не затрагивал ещё слой компилятора и т.п., только фронтенд часть.

Что именно ты хочешь вытаскивать из кода на си? Статистику? Тебе однозначно надо покрутить с месяцок llvm и clang, и посмотреть как они устроены. Поверх clang можно написать всё, что тебе надо

Сейчас разрабатываю компилятор для своего яп, когда начинал, стоял выбор использовать всякие бизоны или писать самому. Решил использовать готовые решения, но посмотрев учебники по различным анализаторам, понял, что за время которые я потрачу на изучение какого-либо анализатора, я могу 3 три раза все сам написать.

fpc

что-то своё

что посоветуете

или

Сразу скажу, я не лазил в гцц или цланг, но писал много парсеров и пару компиляторов.

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

Генераторы парсеров хороши для простых грамматик. Для чуть более сложных случаев (например приоритет операторов в си-подобных языках), тебе уже придётся изголяться с грамматикой, т.е. можешь сразу забыть об интуитивно понятных правилах типа ‘expr + expr’, парсер на этом просто зациклится, приготовься писать промежуточные термы, много. В бизоне есть расширения синтаксиса описания грамматик, чтобы частично нивелировать это, но все равно это сложно и по моему мнению write-only. Это только арифметика, для которой в бизоне есть какие-никакие костыли.

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

Как только ты начнёшь писать парсер, самый очевидный путь — top-down approach. Тут ты опять попадёшь в ловушку зацикливания парсера на простых выражениях вроде a + b и постепенному пониманию, что этот подход хоть и кажется интуитивным для человеческого мозга, описать алгоритм компьютеру будет сложно.

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

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

Пойти по классике и упороться flex-ом

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

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

Жду рассказов людей, которые туда погружались и выплыли

Туда не надо погружаться, это известно. У них рукописные парсеры. В прошлом в gcc были flex/bison.

что посоветуете человеку, который хочет что-то вытаскивать из написанного людьми (*) кода на C или C++

libclang, практически без вариантов.

C++? Пойти по классике и упороться flex-ом

Во-первых, flex не классика. Во-вторых, упарываться придется в основном yacc/bison. В третьих, ты не упорешься настолько чтобы осилить C++. C еще можно.

так-то понятно … по-бырому сделать «парсер» на регулярках

Эм… Нет. Тебе даже близко не понятно. А инженерное и юниксвейное (даже для тех кому понятно) - libclang.

И второй вопрос — что посоветуете человеку, который хочет что-то вытаскивать из написанного людьми (*) кода на C или C++? Пойти по классике и упороться flex-ом или?..

Только libclang.

П.С. flex - это лексер, им конечно можно упороться, как и регулярками, но не больше.

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

Похоже нас посетил сам великий магистр Йода

В llvm нет никаких утилит для создания парсеров и лексеров, а clang использует самописный парсер, обычный recursive descent.

Рукописный рекурсивный спуск обычно используется. Сравнительно прост и понятен, и легко хаки прикручивать.

Пойти по классике и упороться flex-ом или?..

Взять готовый парсер С или С++. Не надо писать кривое говно на коленке.

«парсер» на регулярках

А вот теорию подучи.

Вопрос в первую очередь тем, кто погружался в исходники компиляторов: gcc, clang, rustc, fpc, go… Используют ли они универсальные инструменты для лексического анализа и разбора — все эти flex, bison и др., которые рекомендуют учебники?

Или же там для разбора исходников написано что-то своё, более низкоуровневое?

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

И второй вопрос — что посоветуете человеку, который хочет что-то вытаскивать из написанного людьми (*) кода на C или C++? Пойти по классике и упороться flex-ом или?..

Разница может быть огромной, в зависимости от того что требуется «вытаскивать».

Советую посмотреть на re2c (пример) и lemon, а если чего-то будет недостаточно то подклеиваться к llvm.

И второй вопрос — что посоветуете человеку, который хочет что-то вытаскивать из написанного людьми (*) кода на C или C++?

Ну, был GCC-XML на смену которого пришел CastXML. С языком C наверно будет норм, а вот с C++ наверняка все не так гладко.

А какая вообще конечная цель? С какой целью что-то вытаскивать из кода на C или C++?

В прошлом в gcc были flex/bison.

Т.е. перешли на своё? А чем мотивировали?

Одна из задумок - сделать генерацию GUI из сишных структур.

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

В gcc парасер написан руками, когда-то давно использовали flex/bison.

В sdcc используют flex/bison.

Бери грамматику для flex/bison, если говнякать прототип, - то для PLY, и извлекай то, что тебе надо.

Cast hobbit

все эти flex, bison и др., которые рекомендуют учебники?

Какие учебники?

Ну, например, http://www.admb-project.org/tools/flex/compiler.pdf

Одна из задумок - сделать генерацию GUI из сишных структур.

Ну это я думаю можно - CastXML может выдать XML файл с описанием структур. Для

#include <inttypes.h>
#include <stddef.h>

struct uint8pair
{
  uint8_t a;
  uint8_t b;
};

struct uint16pair
{
  uint16_t a;
  uint16_t b;
};

будет какое-то такое описание:

  <Typedef id="_12" name="__uint8_t" type="_111" context="_1" location="f1:37" file="f1" line="37"/>
  <Typedef id="_14" name="__uint16_t" type="_112" context="_1" location="f1:39" file="f1" line="39"/>
...
  <Typedef id="_66" name="uint8_t" type="_12" context="_1" location="f3:24" file="f3" line="24"/>
  <Typedef id="_67" name="uint16_t" type="_14" context="_1" location="f3:25" file="f3" line="25"/>
...
  <FundamentalType id="_111" name="unsigned char" size="8" align="8"/>
  <FundamentalType id="_112" name="short unsigned int" size="16" align="16"/>
...
  <Struct id="_104" name="uint8pair" context="_1" location="f8:4" file="f8" line="4" members="_132 _133" size="16" align="8"/>
  <Struct id="_105" name="uint16pair" context="_1" location="f8:10" file="f8" line="10" members="_134 _135" size="32" align="16"/>
...
  <Field id="_132" name="a" type="_66" context="_104" access="public" location="f8:6" file="f8" line="6" offset="0"/>
  <Field id="_133" name="b" type="_66" context="_104" access="public" location="f8:7" file="f8" line="7" offset="8"/>
  <Field id="_134" name="a" type="_67" context="_105" access="public" location="f8:12" file="f8" line="12" offset="0"/>
  <Field id="_135" name="b" type="_67" context="_105" access="public" location="f8:13" file="f8" line="13" offset="16"/>
...

А вот парсить именно код функций оно не умеет.

Вообще-то, универсальность зло, за исключением некоторых отдельных случаев.

Пишите программы, которые делают что-то одно и делают это хорошо.
Пишите программы, которые бы работали вместе.

Пишите программы, которые делают что-то одно и делают это хорошо.
Пишите программы, которые бы работали вместе.

А где здесь «универсальность»?

А чем мотивировали?

http://gcc.gnu.org/wiki/New_C_Parser

Ну это у плюсовиков свои ведосипеды, какие-нибудь джависты всё же скорее выберут ANTLR.

Пробовал писать плагин для Clang, который по AST ищет неявные касты. Оказалось, что это достаточно просто. Определяешь класс с методами, которые будут вызваны в предопределённые моменты во время парсинга. В документации всё достаточно подробно описано: https://clang.llvm.org/docs/ClangPlugins.html. Ещё очень советуют https://clang.llvm.org/docs/LibTooling.html.

Для питона есть https://github.com/eliben/pycparser. Тоже определяешь Visitor, и вперёд.

Ещё есть SrcML. На некоторых конструкциях ломается и выдаёт бред, но для большинства кода работает. Он тоже XML отдаёт. Может для подобных задумок его хватит.

Ну, был GCC-XML на смену которого пришел CastXML.

Ну вот у меня под рукой сейчас был как раз GCC-XML (система старая, да). Как им правильно пользоваться? Если я скармливаю ему произвольный исходник, он ругается на все имена, которые заинклужены из нестандартных библиотек (например, на QDialog из Qt).

Есть какой-нибудь способ указать ему пачку путей к требуемым заголовочным файлам? В man gccxml по слову path как-то ничего не нашлось.

Или для CastXML это неактуально и там всё по-другому делается?

Да выкинь каку. Тоже как-то пытался использовать, помучился и взял clang ast matcher.

Ну вот у меня под рукой сейчас был как раз GCC-XML (система старая, да). Как им правильно пользоваться?

Не знаю, надо курить документацию на него.

Или для CastXML это неактуально и там всё по-другому делается?

Ну у CastXML есть какие-то свои инклуды, типа /usr/share/castxml/clang/include/ но и из /usr/include/ он тоже берет. В общем я думаю что это решаемая задача, надо просто почитать ман и разобраться, как туда всякие хедеры подключать

Одна из задумок - сделать генерацию GUI из сишных структур.

Совсем свеженькое на эту тему: https://www.youtube.com/watch?v=UTsgko7A2wo

Как же все печально без гомоиконности и нормальной рефлексии...

Вопрос в первую очередь тем, кто погружался в исходники компиляторов: gcc, clang, rustc, fpc, go… Используют ли они универсальные инструменты для лексического анализа и разбора — все эти flex, bison и др., которые рекомендуют учебники?

Прежде всего я хотел бы отметить, что C++ принципиально не парсится синтаксически без семантического анализа. По крайней мере современные версии и старые, про самые-самые новые я не готов говорить.

И второй вопрос — что посоветуете человеку, который хочет что-то вытаскивать из написанного людьми (*) кода на C или C++?

Божественных благословений и железных нервов. Я уже ставил свечу в храме за то, чтобы мне никогда не пришлось этим заниматься. Конечно, используя herak-herak-driven development что-то можно сделать, но я такой человек, что если софтина не идеальна, то я не могу успокоиться - в таком ключе делать парсер для C/C++ - это пытка.

C++ принципиально не парсится синтаксически без семантического анализа

Интересно мне одной кажется, что ты херню написал?

https://habr.com/ru/article/448466/#comment_20095844 Далее:

Для того, чтобы этот код распарсить (построить AST, хоть немного отличающееся от разбивки на токены), надо уметь вычислять произвольные констекспр-функции, а они Тюринг-полны. И все.

Там кстати царь в комментах тусуется, его легко распознать

Совсем свеженькое на эту тему: https://www.youtube.com/watch?v=UTsgko7A2wo

Как же все печально без гомоиконности и нормальной рефлексии...

Нужно понимать, что кресты изначально предназначались для системнищы, низкоуровневого, и высокопроизводительного кода. Если вам нужно на C++ генерить GUI, сериализацию, ORM, CRUD, RPC, то вы выбрали совершенно не тот язык для решения задачи. Это примерно как если бы я взял кобол и пошел писать 3D шутаны. Или взял питон и начал писать на нем драйвер SSD накопителя.

Интересно мне одной кажется, что ты херню написал?

Как видишь, пока тебе одной. В крестах одинаковый ситаксис операций сравнения и объявления переменной с типом-шаблоном, а также совпадают инициализатор в классе и объявление функции.

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

Вообще-то можно придумать некий диалект Си с s-expr синтаксисом, рефлексией и нормальными макросами, и дальше на этом городить любые абстракции, независимо от того, под что там оно предназначалось. А глядя на весь тот бардак, который развели в C++ c этими темплейтами и констэкспрами, хочется плакать.

https://github.com/carp-lang/Carp https://github.com/wolfgangj/bone-lisp/ https://github.com/kiselgra/c-mera например

Я вот до сих пор не знаю вычисление чисел фибоначе на шаблонах доказывает их полноту по Тьюрингу или нет? Но gcc вроде такое умеет?

Я вот до сих пор не знаю вычисление чисел фибоначе на шаблонах доказывает их полноту по Тьюрингу или нет?

Нет. А вот написание интерпретатора брейнфака на шаблонах доказывает.

Но gcc вроде такое умеет?

Как умеет?

Вообще-то можно придумать некий диалект Си с s-expr синтаксисом, рефлексией и нормальными макросами, и дальше на этом городить абстракции. А глядя на весь тот бардак, который развели в C++ c этими темплейтами и констэкспрами, хочется плакать.

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

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

Можно список?

Фибоначе это рекурсия? Так? Любой вычислитель с рекурсией Тьюринг полный? Или нет?

Фибоначе это рекурсия? Так?

Что значит «это рекурсия»? Я тебе и без рекурсии Фибоначчи посчитаю

Любой вычислитель с рекурсией Тьюринг полный?

Если у тебя есть рекурсия, и ты ей только числа Фибоначчи посчитать можешь - нет, это не Тьюринг-полнота. У тебя какая-то каша в голове

C++ нельзя распарсить синтаксическим парсером, говорит о том, что язык делался на «отстаньте от меня уже».

А мне рассказывали на семинаре, что С++ был создан для ответа на вызов промышленности. Когда седые юникс-дядьки из at&t и прочих IBM сказали: «Ребята мы крупно обосрались. Мы больше не можем писать сложные проекты на С. Их сложность превосходит наши умственные способности и индустрии нужен другой язык».

что С++ был создан для ответа на вызов промышленности

Он не был «создан для», а был просто создан. Ситуация в промышленности сыграла роль в том, что он стал популярен. В общем, «так получилось».

Не только числа Фибоначе. Шаблоны С++ позволяют определять любые рекурсивные функции времени компиляции.

Когда седые юникс-дядьки из at&t и прочих IBM сказали: «Ребята мы крупно обосрались. Мы больше не можем писать сложные проекты на С. Их сложность превосходит наши умственные способности и индустрии нужен другой язык».

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

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

Используют ли они универсальные инструменты для лексического анализа и разбора — все эти flex, bison и др., которые рекомендуют учебники?

нет, не обязательно. например в том же fpc и go простой нисходящий рекурсивный парсер. в книге Креншоу «Let’s make a compiler!» приводится пример компилятора паскаля (на ассемблере, потом он ещё его на форте переписал). вообще, зависит от грамматики. например, нечто паскалеподобное обычно LR или LALR парсера достаточно. что-то более сложное, уже с проверкой семантики – пишется вручную. как пример технологичного тулза типа «flex,bison и др.» рекомендую ANTLR, особенно в v4 он пытается сам вывести не леворекурсивные грамматики, сводить к типовым. там есть например графический отладчик AntlrWorks, где можно по шагам отладить, посмотреть AST и т.п.; изначально оно под Java, но есть бекенды под 10500 языков программирования и примеры 10600 грамматик готовых в комплекте или на сайте. довольно технологично. также книга от его автора полезна, правда она ЕМНИП платная стала.

из простых технологичных также см. PEG-грамматики. это тоже по сути RDP парсер. есть реализации под 10500 языков программирования, включая любопытные реализации макросами времени компиляции, например в D: Pegged и что-то такое в Nim. то есть, парсер может строиться во время компиляции и распарсенное кодогенерироваться/транспилироваться в D/Nim код. учитывая что сам Nim далее компилируется в С, получаем такой простой бесплатный транспилятор своего недоязычка в Си, на Nim AST макросах.

И второй вопрос — что посоветуете человеку, который хочет что-то вытаскивать из написанного людьми (*) кода на C или C++? Пойти по классике и упороться flex-ом или?..

libclangd, плагины к clang или gcc для написания своего compiler pass.

в clang более человекопонятно, в gcc нужно читать отдельную книжку про потроха компилятора: все эти GIMPLE, RTL, SSA и прочие представления. алсо, есть лисп Meld который по сути поверх GIMPLE, то есть такой лисп времени компиляции в gcc, на котором довольно просто можно написать свой плагин.

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

реализация сего действа как плагин к компилятору, например clang (где есть нормальная обучалка в отличие от анналов gcc) – позволила бы просто собирать сишные библиотеки стандартным компилятором cland со своим нестандартным плагином, и параллельно в фоне строить свои обёртки (которые могут строится не совсем уж однозначно и примитивно).

то есть, на основе AST дерева откомпилированных функций, когда успешно откомпилирована реализация (а не отдельно типы, отдельно хедеры, отдельно заморочка как представить макросы/шаблоны/классы в цпп в другой язык).

алсо, можно посмотреть ту же vala на предмет gobject-introspection, gir и обёрток к glib/gobject, к прочим библиотекам – как они там реализованы.

в целом, есть ощущение что плагином к clang в качестве отдельного AST прохода компилятора – это наиболее правильный путь.

Шаблоны С++ позволяют определять любые рекурсивные функции времени компиляции.

Ну если любые, интерпретатор брейнфака можно будет написать, это да. Тогда вполне Тьюринг-полно. Только компиляторы обычно имеют ограничения на глубину раскрытия шаблонов, почитай про флаг -ftemplate-depth

В качестве чего-то нового впечатляет уровень «нативного парсинга» в виде удачной реализации паттерн-матчинга в erlang и списки в лиспе (сама концепция данных и кода хороша в целом)