Комментарии 32
добавить peco в наш репозиторий как подмодуль git, выполнив из корня нашего репозитория команду
Довольно странный способ установки. В Python обычно публикуют пакет на pypi.org, и тогда его можно установить любым пакетным менеджером.
Возможно, это пока не окончательная версия библиотеки, и API ещё поменяется — поэтому автор не спешит с публикацией пакета в реестре PyPi.
Есть и другие примеры компиляторов без зависимостей, которые предоставляются только в виде исходного кода — например, компилятор XamlX, используемый в кроссплатформенном GUI-фреймворке AvaloniaUI для трансляции разметки интерфейса в низкоуровневое представление и не опубликованный в реестре NuGet.
Видимо, обновлять связанные репозитории иногда проще через git pull, чем через реестр пакетов. А переключиться на нужную версию библиотеки легко через git checkout :)
Есть и другие примеры компиляторов без зависимостей, которые предоставляются только в виде исходного кода
В мире C# это возможно и норма, с учётом того, что пользователи в конечном итоге скачивают программу в виде скомпилированного бинарника, и способ распространения исходного кода им не так важен. Но в питоне упаковка в бинарный файл это скорее исключение из правил - зачастую все распространяется в виде пакетов, и указывать в метаданных пакета зависимость на git репозиторий довольно неудобное решение.
В мире C# это тоже не норма, там сразу были динамические скомпилированные библиотеки, а сейчас пакеты, которые публикуют на nuget.org
А вот в мире C++ возможно всякое...
Роскошная статья, побольше бы таких на Хабре! И подборка ссылок соответствующая.
+/+
Я конечно нуб в теме парсеров, но идею со стеком считаю великолепной!
В первый раз вижу такое сочетание парсер-комбинаторов и стэка.
Соглашусь! Есть ещё интересный момент — состояние peco можно переопределить, добавив новые поля, не сломав при этом уже реализованные peco-грамматики. Это позволит выполнять семантические действия при разборе и реализовать таким образом, например, lexer hack.
Хмм… а я issue открыл на эту тему…
Несколько неточностей в предисловии лучше поправить:
1. Переводом кода с одного ЯП на другой занимается транслятор (иногда применяют термин "транспилятор"). Компилятор - частный случай транслятора: компилятор переводит код с высокоуровневого языка (обычно ЯП) в машинный \ объектный код.
2. "передним/задним планом" фронтэнд и бэкэнд азывать не принято.
3. Сегодня (начиная с llvm) компилятор делят на frontend / middleend / backend
4. Лексер + парсер - малая часть фронтэнда. Основная часть фронтэнда - построение AST и специфические (обычно глобальные) оптимизации над AST.
Также добавлю вопрос от себя:
Лексер (в лексере-парсере) нужен для того, чтобы ваш парсинг был устойчив к разделителям и форматированию пользователя.
5. С peco (и вообще парсерами в python) не работал - а что у вас обеспечивает эту фунциональность?
Не автор, но могу ответить на пятый вопрос — разделители (пробельные символы любого вида) обрабатываются вот этими правилами грамматики:
space = eat(r'\s*')
token = lambda f: seq(space, f)
Правило space просто пропускает все пробельные символы. Функция token строит правило, пропускающее пробельные символы перед основным правилом f. Все остальные правила так или иначе определяются через функцию token. Например, функция
tok = lambda c: token(push(eat(c)))
формирует токен, кладя строку составляющих его символов c (через eat(c)) на стек (через push(...)) и пропуская пробельные символы перед ней (через token(...)). А правило
skip = lambda c: token(eat(c))
просто пропускает символы c (через eat(c)) + необязательные пробельные символы перед ними (через token(...)).
Поскольку все остальные правила строятся через эти примитивы, то парсер успешно обрабатывает наличие пробельных символов в любом месте разбираемого выражения.
Ок, спасибо (грепнул skip).
Ручной скип delimiters без лексера.
expr = alt(
seq(skip(r'\('), expr, bop, expr, skip(r'\)'), mkbop),
seq(var, skip(r'\('), args, skip(r'\)'), mkfun),
var,
num,)
Углы срезаны, as-is, смысл имеет (сложность-то обычно не в лексере, а в заворачивании лексера под капот парсера бесшовно лениво и с нормальными сообщениями об ошибках). В минимально поддежриваемом проекте лучше бы в этих местах не срезать.
В целом "пара месяцев поддержки и зумеры переизобретут лексер" - если тут есть сарказм (а он есть), то абсолютно беззлобный.
@worldbeater
Вообще-то именно так и принято писать PEG-парсеры, не знаю, что вас здесь удивило. Нет, можно, конечно, добавить отдельный шаг лексера, формировать токены, а парсер натравить на них, но зачем это усложнение, когда PEG и так успешно справляется с задачей?
И кстати, «ручной скип delimiters» происходит ровно в двух вышеуказанных мной правилах, если конечно, под «разделителями» вы не имели в виду служебные скобки, являющиеся частью синтаксиса. Не предлагаете же вы засовывать их пропуск в лексер?
Чтобы сэкономить 20-30 строк на PEG-парсере превратим входное выражение в нечитаемую мешанину из скобок.
Это выглядит как плохое архитектурное решение, анлесс ваша целевая метрика - минимальное число строк кода (ценой удобства пользователя).
П.С.
> Вообще-то именно так и принято писать PEG-парсеры, не знаю, что вас здесь удивило.
А где и зачем так принято, - что ради довольно небольшого кол-ва строк и исходная грамматика менее удобна и код regex начитает содержать?
Преимущество PEG-грамматик в том, что они принципиально не сваливаются в бесконечный бэктрекинг, как может происходить с LL-парсерами, поскольку выбор альтернативы alt в PEG-парсерах упорядоченный, то есть, если мы хотя бы частично успешно прошли по первой ветке, то уже никогда не пройдём по второй. Это значительно упрощает код парсера и повышает скорость его работы (а также понижает требования к памяти). Но для этого надо аккуратно прописать порядок этих альтернатив, что, конечно, сделать сложнее, чем в LL-парсерах.
нечитаемую мешанину из скобок
Делаете так:
L_PAREN = skip(r'\(')
R_PAREN = skip(r'\)')
binary_op = seq(L_PAREN, expr, bop, expr, R_PAREN, mkbop)
call_function = seq(var, L_PAREN, args, R_PAREN, mkfun)
expr = alt(binary_op, call_function, var, num)
и никакой мешанины из скобок.
Ни грамматика ни код не видятся мне хорошими
Какой же код тогда на ваш взгляд хороший? Вот приведённый в статье, например, один в один повторяет структуру грамматики из EBNF, чем же это плохо?
В LL-парсерах бэктрэкинг не бесконечный, а экспоненциальной.
Но на практике вы в эту экспоненту вообще вряд ли когда-нибудь упираетесь при парсинге чего-то похожего на ЯП (corner case - разумеется возможны) - т.е. бэктрегинг в каких-то разумных случаях в профиле вообще не виден.
С заменой как у вас
L_PAREN = skip(r'\(')- куда лучше;
На мой взгляд там нарушение PEP 8: Function and Variable Names (но я не спец по Python - возможно для 0-арных ф-ий там хитрое исключение) .Наличие regexp внутри бизнес-логики - делают код куда менее поддерживаемым. Странно, что это следует объяснять.
С лексером:
куда более "compiler way" - когда сложная системаа строится из набора максимально простых фаз, каждая из которых делает свою законченную часть работы;
лексер имеет законченную функциональность;
Не сложно - здесь достаточно линейного прохода лексера, потом прохода парсера;
скорее всего быстрее;
Что можно перефразирвовать, как "с лексером лучше".
В LL-парсерах бэктрэкинг не бесконечный, а экспоненциальной
Совершенно верно. Однако в практических случаях, когда он вас всё-таки настигает, он именно что «бесконечный». Поэтому я позволил себе такую художественную вольность описания явления.
Наличие regexp внутри бизнес-логики - делают код куда менее поддерживаемым.
Эм. То есть, вас испугал «ужасно сложный» регексп \( (открывающая круглая скобка) или \s* (возможно, пустой список пробельных символов), я правильно понял? Что вы предлагаете ни под каким видом не пускать регекспы в бизнел-логику. Мне кажется, здесь каким-то культом «безрегексповедения» попахивает.
На мой взгляд там нарушение PEP 8: Function and Variable Names
Имена выбраны чисто на мой вкус и привычку называть всякие «константы» КАПСОМ_С_ПОДЧЁРКИВАНИЯМИ. Вы вольны выбрать другие имена.
когда сложная системаа строится из набора максимально простых фаз, каждая из которых делает свою законченную часть работы;
Поздравляю, это суть всех парсер-комбинаторов, коим peco, несомненно и является. Его кирпичики (и наши кирпичики тоже!) — именно что максимально простые фазы, имеющие законченную функциональность. «Пропустить символы». «Положить на стек». «Разобрать вызов функции».
скорее всего быстрее
Непонятно, почему оно должно быть быстрее, если с лексером получается всё то же самое, только ещё и с лексером.
Update:
какие проблемы решает текущая грамматика - я понимаю:
Это например упрощение обработки, включая избегание ошибок: a - b + x / y * z (а не аргументы про скорость (*))
Ценой заставление пользователя делать мешанину из скобок.
Моё утверждение, что плюсы от такого парсера вовсе не перевешивают минусов.
*) Ваши аргументы про скорость - вероятно неактуальны. За исключением corner-case (шаблоны \ хиндли-милнер \ ...) фронтэнд, а тем более парсинг, не является сколь бы то ни было прожорливой частью.
======= спор по маловажной perf-части ========
Совершенно верно. Однако в практических случаях, когда он вас всё-таки настигает, он именно что «бесконечный». Поэтому я позволил себе такую художественную вольность описания явления.
А где посмотреть примеры с экспоненциальным парсингом, скажем C (кратно более сложная вещь, чем парсинг подинтегрального выражения) зависал? Чтобы оценить насколько актуальна проблема для кардинально более сложного случая?
Непонятно, почему оно должно быть быстрее, если с лексером получается всё то же самое, только ещё и с лексером.
Тут был не прав, причём неправ в том месте, где "можно вынести лексер из-под капота парсера". Токенизировать всё-таки надо по ходу парсинга выплёвывая в парсинг только правильные токены.
> максимально простых фаз, каждая из которых делает свою законченную часть работы;
Поздравляю, это суть всех парсер-комбинаторов ... Его кирпичики (и наши кирпичики тоже!) — именно что максимально простые фазы
Как у вас сочетается "совместить парсер с лексером" и "делать максимально простые фазы".
Ну это не говоря уже о том, что компилятор делит на фазы компиляции, а парсер-комбинатор - делает работу внутри фазы компиляции.
Спасибо за развёрнутый комментарий!
Переводом кода с одного ЯП на другой занимается транслятор (иногда применяют термин "транспилятор"). Компилятор - частный случай транслятора: компилятор переводит код с высокоуровневого языка (обычно ЯП) в машинный \ объектный код.
Рискну предположить, что Вы, вероятно, используете определение компилятора из S.S. Muchnick, Advanced Compiler Design and Implementation, 1997, где компилятором называют «средство перевода программ, написанных на высокоуровневом языке, в эквивалентные программы в объектном коде или машинном коде, предназначенном для выполнения компьютером»? Однако, в начале статьи я намеренно акцентирую внимание читателя на том, что в статье мы используем более широкое определение компилятора из книги K.D. Cooper & L. Torczon, Engineering a Compiler, 2011:
Кроме того, в Advanced Compiler Design and Implementation S.S. Muchnick пишет следующее:
"Передним/задним планом" фронтэнд и бэкэнд называть не принято.
Так называют фронтенд и бэкенд компиляторов в отечественной научной литературе, например, в научных работах [1—3]. Убрал из статьи упоминание этих терминов, чтобы академическая терминология не вызывала вопросов у читателя!
Аветисян А.И., Курмангалеев К.Ю., Курмангалеев Ш.Ф. Динамическое профилирование программы для системы LLVM // Труды Института системного программирования РАН. – 2011. – Т. 21. – С. 71-82.
Советов П.Н. Разработка компиляторов предметно-ориентированных языков для спецпроцессоров // Труды Института системного программирования РАН. – 2020. – Т. 32. – № 5. – С. 35-56.
Стасенко А.П. Модели и реализация транслирующих компонентов системы функционального программирования: дис. // Институт систем информатики им. АП Ершова СО РАН, 2009.
Сегодня (начиная с llvm) компилятор делят на frontend / middleend / backend. Лексер + парсер - малая часть фронтэнда. Основная часть фронтэнда - построение AST и специфические (обычно глобальные) оптимизации над AST.
Постарался прояснить п.3 и п.4 в предисловии — надеюсь, в нынешней редакции статья улучшилась. Отдельное спасибо @Mingun за разъяснения по п.5 в соседнем комментарии!
Учился я как раз по Ахо-Ульман, где компилятором называется программа переводящая с одного языка на другой.
Но в реальной жизни семантика translator && compiler разделилась - оставив компилятору узкое значение, конкретного вида трансляторов.
> Rosetta is a dynamic binary translator developed by Apple Inc. for macOS, an application compatibility
> Online Rust to Csharp Converter
Проверил для DSL - их это тоже касается (см число найденных ответов)
На 2-й картинке выше опечатка, без неё разница в количестве результатов несущественна:
Но это говорит только о распространенности обсуждаемых определений, правильно?
Конечно, студентам я рассказываю об исторически сложившихся определениях и разнице между ними (транслятор, транспайлер/транспилятор, компилятор, интерпретатор, ...), но в короткой обучающей статье, на мой взгляд, лучше сослаться на определение из классического учебника. Да и потом, после sed s/компилятор/транслятор статья выглядит уже не так интригующе. А цель — заинтересовать читателя, показать, что сделать свой DSL проще, чем кажется на первый взгляд!
Но это говорит только о распространенности обсуждаемых определений, правильно?
Ничего себе "только" - значения слов это узус, то как они употребляются.
Тем более вы преподаватель (а не студент, как изначально думал).
Сделать хорошую работу, и снабдить её разъяснительным текстом лет на 20 устаревшим? А потом студенты тут на хабре пишут - нас учили всякой устаревшей фигне.
Что вообще может человека мотивировать поступать так? Нежелание признавать свои ошибки "якобы под давлением"? Ну ок мне не сложно:
- вы сделали хорошую полезную для студентов работу;
- сопровождение хорошо написано и отлично выглядит;
- если поменяете терминологию на более современную - это сделает и без того хорошую работу ещё лучше;
Сделать хорошую работу, и снабдить её разъяснительным текстом лет на 20 устаревшим?
А что именно устарело, не расскажете? Выше в вопросах терминологии компилятор/транслятор пока видно только «так принято». Кем принято, где и когда принято? Выше цитаты из учебников были попыткой намекнуть, что нужен более весомый источник, чем число результатов в поисковой выдаче Google или скопированный текст из README.md случайного проекта, причем источник желательно академического толка, если уж мы полемизируем с S.S. Muchnik и др.
А потом студенты тут на хабре пишут - нас учили всякой устаревшей фигне.
А можно поконкретнее? Определитесь, пожалуйста, «устарело» или «зумеры изобрели», а то, если честно, уже не улавливаю. Спасибо.
А что именно устарело, не расскажете?
употребление терминов так, как у вас в предисловии.
Вы действительно сомниваетесь в том, что сегодня compiler (по поводу DSL-компилятор к стати у меня изначально вопросов не было - такое употребление встречал, хотя с DSL особо не работаю - чем объяснить разную выдачу гугла пока не понимаю) в большинстве случаев употребляется как частный стучай транслятора, когда целевой язык - биранрый \ объектный \ ассемблер (или другой язык платформы)?
Вы действительно сомневаетесь в том, что сегодня compiler в большинстве случаев употребляется как частный случай транслятора, когда целевой язык - бинарный \ объектный \ ассемблер (или другой язык платформы)?
К сожалению, у меня нет под рукой статистики, чтобы однозначно утверждать, что сегодня компилятор в большинстве случаев считают частным случаем транслятора — впрочем, однозначно утверждать, что это не так, я также без подтверждений в виде конкретных цифр не стану, и нигде выше по тексту, кажется, не утверждаю.
Мне встречался и тот, и другой подход к определению «компилятора» и «транслятора». Наверное, надо аккуратно измерить частоту встречаемости этих терминов на ресурсах сообществ по компиляторам, чтобы можно было сделать однозначный вывод, какой вариант более массовый? Персонализированная выдача Google для сбора такой статистики вряд ли подходит. Именно поэтому во избежание путаницы в самом начале статьи явно указано, каким конкретно определением компилятора, и из какой книги, мы будем пользоваться в пределах статьи, чтобы не вводить читателя в заблуждение. Мы можем заменить термин «компилятор» в предисловии и далее в статье, если на это есть веские основания, но надо понять, на какой именно термин и на какой именно приличный SSOT можно было бы сослаться.
Кстати, вот доводы в пользу того, что не всё так однозначно:
На главной странице проекта Babel указано, что «Babel is a JavaScript compiler», хотя данный инструмент транслирует JavaScript-код, в котором используются новые и экспериментальные синтаксические конструкции, в JavaScript-код, совместимый с не самыми новыми браузерами, такими как Internet Explorer 11. Такие инструменты иногда называют транспиляторами/транскомпиляторами, но авторы называют свой инструмент именно компилятором. Впрочем, этот довод на уровне доказательства ссылкой на «README.md случайного проекта на GitHub» можно пропустить, хоть проект и широко используемый.
В репозитории проекта Cython указано, что Cython — это «The most widely used Python to C compiler», при этом указано также, что «Cython translates Python code to C/C++ code». Впрочем, C иногда называют высокоуровневым ассемблером, поэтому данный пункт также можно пропустить. Хотя есть и managed-реализации C, например, Cesium.
В англо-русском словаре терминов по вопросам компиляции русскоязычного сообщества разработчиков компиляторов указано: «Compiler — компилятор, транслятор». То есть, здесь эти 2 термина считают взаимозаменяемыми, насколько я могу судить. Кстати, у сообщества есть чат в Telegram, можно обсудить терминологию ещё и там, помимо этой ветки комментариев, чтобы выяснить, почему написали именно так.
Обратите внимание, правки в соответствии с Вашими замечаниями в части п.2, п.3 и п.4 были ведь сразу внесены, а Вы на ad hominem переходите несколькими комментариями выше в связи с вопросами к п.1. Надеюсь, что цель обсуждения, всё же, в том, чтобы выяснить истину / сделать правильнее, а не в том, чтобы отстоять точку зрения :)
@WASD1 отвечу на свой же комментарий, если позволите.
Почему-то нам с Вами в этой ветке не напомнили, что как только разгорается спор о терминах, применение которых разнится от источника к источнику, полезно обратиться к стандартам — воспользоваться терминами из стандарта, если он есть, или опубликовать новый стандарт, если о терминах ещё не договорились.
Итак, внимание!
ГОСТ 19781-90 Обеспечение систем обработки информации программное <...> Трансляция — преобразование программы, представленной на одном языке программирования, в программу на другом языке и в определенном смысле равносильную первой. Транслятор — программа или техническое средство, выполняющие трансляцию программы. Компиляция — трансляция программы с языка высокого уровня в форму, близкую к программе на машинном языке. Компилятор — программа или техническое средство, выполняющие компиляцию. <...> Переиздание. Январь 2010 г.
Спасибо @WASD1 за плодотворную дискуссию, обновил терминологию в соответствии с ГОСТ 19781-90, добавил Вас в благодарности! Пожалуйста, пишите, если ещё найдёте неточности. Улучшим.
👍
Судя по задаче у вас графовых оптимизаций не будет - тольк над деревьями.
Исходя из этого - в чистой теории: имеет ли смысл в этой схеме вообще упоминать IR?
(я в целом писал это ниже - но я тогда предполагал, что вы студент).
А по бэкэнду - выглядит так, что минимально необходимый функционал:
- нелокальный peephole: a + b + c + c -a ( у вас "+a" и "-а" будут отстоять довольно далеко друг от друга).
- замена переменных.
Ну это если бэк входит в область рассмотрения статьи.
конфигурирования спецпроцессоров на основе FPGA (PyLog),
Судя по статистике обновлений на https://github.com/hst10/pylog этот проект мертвый. Последнее обновление случилось почти 2 года тому назад. Число разработчиков в точности равно числу авторов статьи в IEEE. Чисто академический проект с целью исследования темы и публикации статьи. Дальше все заглохло. Подобное часто случается с академическими проектами.
На тему инструментов высокого уровня в контексте FPGA (а также ASIC) есть интересная дискуссия: https://www.reddit.com/r/FPGA/comments/10riaj3/fpga_highlevel_programming/ Там много сказано почему подобные инструменты не получили широкого распространения.
К стати вам тут IR в общепринятом понимании не нужен (это довольно сложная структура).
Если пишите диплом (или что вы пишите?) - то можете черкнуть, что поскольку AST структурно совпадает разработанным вами IR, то IR = map(transform_node, AST), но (*).
*) А в случае эквивалентных преобразований структурно одинаковых выражений воспользуемся α-эквивалентностью поддеревьев (комиссии понравится).
https://ru.wikipedia.org/wiki/Лямбда-исчисление#α-эквивалентность
Практика использования парсер-комбинаторов peco и оператора match для создания простых DSL на языке Python