EBNF и разработка ЯП

Тыкаю в нейронку, видно данных мало. Самое хорошее что она предлагает - переходить с EBNF на PEST, если парсер делать под растишку и на его инфраструктуре и ехать.

классика жанра https://www.antlr.org на чём в принципе тред можно и закрыть

если парсер делать под растишку

В ноосфере какие-то флуктуации. Сначала нужно угадать ЯП, на котором будет писаться?

Привет! У меня было всё сделано рукописное, методом рекурсивного спуска. Основной инструмент здесь - это голова, которой не хватало, поэтому сделали очень простой движок базы знаний в одном файле, где предметная область была разбита на мелкие статьи, взаимосвязанные друг с другом. В том числе и конфликты там учитывались в виде тега, и была табличка разных видов character-ов, чтобы видеть проблемы на границах лексем. Наверное, что-то среднее между фреймами, семантической сетью и вики. Остались ли в синтаксисе в результате этого решения какие-то баги - я не могу сказать, ибо не знаю. В общем и целом я стремился, чтобы синтаксис был простым, т.к. у меня в утёнке бейсик, а в практике на тот момент был лисп, т.е. простые синтаксисы, читающиеся в основном слева направо, с весьма малой дозой синтаксического сахара. Весь синтаксис - это сумма синтаксиса лексем, которая более-менее одинакова, выражений с приоритетами и скобок. В таком простом наборе довольно легко исправлять косяки. Если посмотреть на некоторые «настоящие» компиляторы, то рукописные парсеры вполне себе встречаются. Почему отказался от генераторов? Потому что не увидел большой пользы, сложно отлаживать и сложно контролировать сообщения об ошибках. То ли я их не осилил, то ли правильно сделал - пока не знаю.

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

это голова, которой не хватало

Та же самая проблема. Накидал за вечер быстро идею, стал в детали спускаться и там начались тонкие моменты, понял что надо более формально, я хочу своим форматом пользоваться серьёзно. Может к сайту прикручу. Маркдауна мне мало (особенно в плане таблиц и того как они там сделаны), а аскидок слишком не нравится.

У них есть свой почти что язык для создания языков pest

Типа https://lexy.foonathan.net для C++? :)

Сначала нужно придумать грамматику. Грамматики, по иерархии Хомского, делятся на 4 типа по сложности:

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

Насколько я помню, для упрощения дальнейшего синтаксического анализа желательно избежать левой рекурсии при разработке грамматики, то есть правил типа expr → expr + term

См https://ftp.zhirov.kz/books/IT/%D0%90%D1%80%D1%85%D0%B8%D1%82%D0%B5%D0%BA%D1%82%D1%83%D1%80%D0%B0%20%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%B0/%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D1%8B.%20%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF%D1%8B%2C%20%D1%82%D0%B5%D1%85%D0%BD%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D0%B8%20%D0%B8%20%D0%B8%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BC%D0%B5%D0%BD%D1%82%D0%B0%D1%80%D0%B8%D0%B9%20%28%D0%90%D0%BB%D1%8C%D1%84%D1%80%D0%B5%D0%B4%20%D0%92.%20%D0%90%D1%85%D0%BE%2C%20%D0%9C%D0%BE%D0%BD%D0%B8%D0%BA%D0%B0%20%D0%A1.%20%D0%9B%D0%B0%D0%BC%2C%20%D0%A0%D0%B0%D0%B2%D0%B8%20%D0%A1%D0%B5%D1%82%D0%B8%2C%20%D0%94%D0%B6%D0%B5%D1%84%D1%84%D1%80%D0%B8%20%D0%94.%20%D0%A3%D0%BB%D1%8C%D0%BC%D0%B0%D0%BD%29.pdf п. 2.4.5 Левая рекурсия

Поделитесь опытом, какие инструменты у нас есть в линуксах для проверок синтаксисов на разного рода коллизии и вообще

LR(1) генераторы делают такую проверку, можешь взять любой, хоть тот же Bison. Для рекурсивного спуска будет полезно также проверить на LL(1) коллизии — готовых инструментов для этого я не знаю, но можешь написать свой (см. FIRST и FOLLOW множества).

а там тоже бывают сложные и тонкие моменты, которые в голове могут быть и не учтены, приводя у UB у парсеров, когда синтаксис можно толковать двояко (классика жанра в C++) i = ++i + i++

Эта проблема вообще не имеет отношения к синтаксису.

Грамматики, по иерархии Хомского, делятся на 4 типа по сложности

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

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

Precedence climbing делает это не обязательным.

Есть разные расширения маркдауна, особо глубоко, правда, не копал, но был прецедент встраивания в него формул на ТеХе. И, чтобы два раза не вставать, вот как выглядела моя база знаний в отрендеренном виде:

https://программирование-по-русски.рф/static/sbclt-docs.html

Исходник этого я уже вряд ли найду, хотя вот фрагмент похожего

; -*- system :ПРОЕКТ-ЧИТАТЕЛЯ; coding: utf-8; -*- 

(in-package :ПРОЕКТ-ЧИТАТЕЛЯ)
(named-readtables::in-readtable :buddens-readtable-a)


(СЕКЦИЯ ВСЁ ("" () "")

 (! о-данном-документе "" ()
    """Этот файл генерируется системой :ПРОЕКТ-ЧИТАТЕЛЯ, инструкции см. в asd файле """)

 (! обзор-требований "" ()
 """
- с одной стороны, имитируем лисп, к-рый всё читает и создаёт набор вложенных групп
- с другой, имитируем обычные языки (два этапа - лексический и синтаксический анализ)
- хотим раскрашивать во много слоёв: идентификаторы и их части, ошибочные лексемы, строки и т.п.
- хотим раскрашивать встроенные иные синтаксисы
- восстановление после ошибок на основе отступа (если ошибка, то закрываем всё, когда уменьшается отступ)
- def-symbol-readmacro
- хотим, чтобы простым сторонним просмотровщиком можно было просматривать файл, невзирая на наличие в нём symbol-readmacro-в.
"""
 :СМ-ТАКЖЕ (состав-работы-по-разбору-при-отсутствии-ошибок))


 (! состав-работы-по-разбору-при-отсутствии-ошибок "" ()
    """
- читатель - читает лексемы
- пост-лексер - собирает составные лексемы - белые поля и символы. 
- группировщик - собирает группы, такие как (элемент,...,элемент) и опр ... кно      
- парсер - разбирает определения, составной оператор, выражения с приоритетом операций

Читатель и пост-лексер находятся в процессе слития. А именно, прогресс читателя в одном месте (при разборе символа) ограничен: читатель не может продолжать читать за символ, пока пост-лексер не понял, что данный символ не является читающим словом.
""")

 (! def-symbol-readmacro "" (ПРОТИВОРЕЧИЕ)
    """
Решение описано в оя :: предметно-ориентированные-языки (см. описание языка Яр).
Последствия для процесса чтения: мы должны знать прочитанный символ до того, как прочитали следующую лексему, а КАК-ЕСТЬ мы узнаем его только
на этапе пост-лексера. Выход - мы связали читатель и пост-лексер и теперь читатель не может идти дальше одной буквы от конца символа. 
""")

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

Делай по простому - на бумажке опиши синтаксис, а потом нисходящий парсинг. Тулзами-генераторами пользоваться не рекомендую - если захочется потом гибкости, то сложно будет. Можно на первым порах bison использовать, да и то не для генерации, а для валидации EBNF.

Парсеры бывают разные, разного назначения, одни для подсветки кода, другие для языков, одни строят abstract syntax tree, другие concrete syntax tree со всеми каментами и каким образом они в коде отформатированы. В tree sitter вообще на жаваскрипте грамматики делают, хотя на выходе по сути та же EBNF, хоть и в виде жсона. Говорят сырую EBNF писать сложнее, нет ни функций, ни переиспользования.

Я пару раз делал руками кодом парсер формул, без всяких EBNF. Вполне посильно, главное тестами обмазать пожирнее. Сам парсер в ast порядка 200 строк кода. Лексер порядка 50 строк, в основном регексы. Самое сложное кстати сделать хороший годный репорт ошибок, нужно сохранять контекст в каком конкретном месте что было не так.

Вряд ли здесь i = ++i + i++ у парсера UB кстати. Скорее у компилятора, какой как потом сделает перестановку порядка операций.

когда синтаксис можно толковать двояко (классика жанра в C++) i = ++i + i++

Синтаксис тут вполне однозначен. А вот семантика страдает, да, но это не значит что её нельзя тут однозначно определить. Просто авторы Си – наркоманы.

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

Случайно добавить полноту по Тьюрингу – проще простого. Избавиться от неё для более-менее сложного языка – куда сложнее задача. Тут в статье классная картинка в самом начале.

По моему опыту, PEG куда приятнее в использовании чем использовать EBNF и тем более руками писать парсеры. Всячески рекомендую.

Не у парсера, а у стандарта. Стандарт не рассказывает в каком порядке и как.

Что уважаемое купечество скажет про https://github.com/siy/java-peglib ? Это PEG для JDK25+, современная разработка, интересно ваше мнение.

Я отсмотрел за утро PEGи явашные:

• parboiled - 1й давно в уютной коме звёздочек и почёта, 2й вроде только скала, 3й неясно какой. Старьё короче.
• MousePEG - прикольно и здраво но чисто академическая вещь, ни артифактов ни толком пайплайна. Нагенерил код с ошибками. Но в целом здраво
• PetitParser - не помню, но что-то не цепануло
• Rekex - круто что от типов явы всё выводится и JDK17+, но PEG-файла нет, он а-ля parboiled вроде

Задолбали своим калькулятором в куче либ. Мелкий DSL написать текстовый - надо выискивать примеры.

Upd: petit-parser в духе parboiled но ещё более замудоханный и нечитаемый (сходу)

попутный вопрос, есть ли какой-то тул/сайт для работы с PEG-файлами, а-ля https://regex101.com, чтобы где-то править PEG и видеть как матчится искомый текст?

В ideaj community плагина сходу не нашёл.

проблема с EBNF, и вообще, грамматиками Хомского, в том что они описывают как язык может генерироваться, а не как его парсить

PEG и потом recursive-descent по ней, или там, packrat-парсер, это куда удобнее

В сложных случаях один хрен парсеры пишутся руками

.. в случае java-peglib я протупил, есть playground для webui по http. И как продвинутый регексп оно классно работает (в библиотеке). Но в java-peglib в текущей версии 0.6.3 проблемой пользователя является построение AST: в 0.5.0 оно было искаропки (судя по истории гита) а ныне выдаётся CST в виде int[] и жричодали, сам визитором обходи, думой.

Это мне не совсем нравится, хотелось бы PEG+AST сразу, пусть и медленное тупое зато кросивое.

ну вот например есть CoCo/R, Coco/Cookbook и книжка к нему : Pat Terry’s compilerbook Compilers, Compiler Generators and C++ CandCG1997/compbook , Programming Language Translation compilerbook/pltbook.htm compilerbook/Modula2Standardisation/modula2.htm github.com/norayr/cocor_pascal github.com/norayr/cocor_voc под армянский оберон-2 github.com/vishapoberon/compiler

лучше взять более ранний вариант книжки по конструированию конпеляторов, тот где на модуле-2 и паскале – там понятнее. опять же, более простой и понятный CoCo/R есть под Oberon-2: Blackbox component Pascal или классический Project Oberon *.cod (есть в A2) или паскаль (книжка Pat Terry кажется про примеры на Turbo Pascal и Modula-2).

второй по наглядности пример: на Icon (и/или, Unicon: ОО Icon: www.wyrdtech.com/cocor/ ). Про написание конпеляторов на Unicon тоже была книжка, как бы не сразу у них на сайте.

на Icon например написан noweb (впрочем, есть вариант и на awk), и когенераторы ковыражений – это оттуда. сам язык в целом понагляднее питона.

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

из модулы-2 можно взять например gcc-16 gm2 – gcc-snapshot в Debian Sid testing/unstable.

ну, ещё есть ANTLR : v4 и ранее. там тоже как и в CoCo/R есть реализации под все основные языки, но формализм LL(*), есть свои особенности. книжка по нему есть от самого автора ANTLR на Progmatic Programmers, ЕМНИП.

в целом, там примеров чтобы разобраться вполне достаточно. есть StringTemplate и тестовые *.g грамматики, какое-то ANTLR IDE отдельно или плагином к эклипсу (хз, как давно оно обновлялось там).

в целом, и там и там в чём-то похожи: CoCo/R который похож на классический RDP парсер и формализм .ATG наиболее близок к EBNF; и ANTLR в котором LL() есть свои особенности – нужно рефакторить леворекурсивные, приводить к аналогичным; ещё похожи они и там и там тем что есть как синтаксические, так и семантические предикаты. которые можно реализовать сразу написав их обработку на языке реализации парсера.

StringTemplate позволяет сделать шаблонизатор и pretty printer (с правильной красивой идентацией). но в целом, в ANTLR есть все эти фабрики, визиторы и т.п. – и AST получить можно довольно просто например так как AST.toStringTree() – получается дамп в S-выражениях (без красивого форматирования S-выражений, так что потом засовываем в Emacs и скриптом на elisp делаем нормальное выравнивание S-exprs).

например, как-то написал простой и наивный конпелятор транспилятор 1Cv7: грамматика на ANTLR v3, тесты в *.g отдельной грамматике, синтаксические и семантические предикаты, свой pretty printer; но в первой итерации, наивный конпелятор в лисп был просто из AST.toStringTree() + скриптом на елисп. то есть, далее AST макросами лиспа раскрывался в другую реализацию.

на CoCo/R сейчас параллельно почитывая книжку с примерами на модуле и турбо паскале – пишу парсер WEB метаязыка контрольных кодов из классического tangle.web/weave.web. там оригинальная реализация на PASCAL-H типа ISO Pascal, но есть tex-gpc и tex-fpc где нормальный GNU Pascal / Free Pascal (кстати, наиболее простой вариант поставить паскаль под венду это похоже PascalXE – скачиваем и запускаем простой инсталлятор, и вот: конпеляция tangle.pas из tex-fpc одной кнопкой, запуск второй одной кнопкой, pretty printing, форматирование и идентация третьей одной кнопкой. там внутри «из коробки» есть gpc-20070904-with-gcc.i386-pc-mingw32 и FPC 3.4.2, Virtual Pascal .

в целом, классический tangle.web => tangle.p из tex-fpc/tex-gpc написан на структурном программировании с goto; и ручной RDP парсер.

то есть: есть метаязык контрольных кодов WEB: все эти @'oct,@"hex,@\,@@ для квотирования;@,@* для блоков документации; @p для блоков кода; @<codeblock name...@> = / += для имен блоков кода;@{,@} для прагм; @!id для идентификаторов; @.string@> для строк из пула строк; @d для макросов WEB; @& склейка токенов в макросах (как ## в cpp); @f форматы для pretty printing в weave

часть контрольных кодов используется только для tangle, часть только для weave (и своей костыльной реализации pretty printing). где-то строки нормализуются: склеивая пробелы и удаляя комментарии. где-то организуется свой пул строк для токенов и макросов зональным аллокатором в массиве.

в целом, вручную написанные парсеры самим Дональдом Кнутом – весьма наглядны и довольно быстры – не анализируется ненужное (например, контрольные коды нужные только для weave игнорируются в tangle; в weave более полный набор; @? для какого-то ещё не реализованного ? тоже может обрабатываться как конец типа @ ).

но вот например, хочется взять в руки тот же CoCo/R например, и написать нормальную грамматику на алголе-68 gcc16/ga68, модуле-2 gcc16/gm2, аде gcc16/gnat или том же обероне (есть готовые под BBCP , Vishap voc/Ofront и классический Project Oberon; нет под активный оберон в A2).

и запилить например, tangle.web/weave.web не на паскакале, а на ( ~~PL/I PL/KT или Аде или алгол-68 ga68 ~~ – кстати, получается простой дубовый, лоб-в-лоб с паскалевской версии, прямо в отдельных change файлах можно писать : потому что там есть goto) – модуле, оберонах пассивных/компонентном паскале BBCP или обероне активном, акторном A2/BlueBottle.

пописываю вот например сейчас, WEB.ATG грамматику пока что на BBCP, затем под аду или активный оберон перепишу (и заодно, портирую CoCo/R под активный оберон).

ну то есть: там в модуле и оберонах гото нетути , так что классический код Кнута портировать в лоб не получится, придётся писать нормальный парсер метаязыка контрольных кодов WEB. так почему бы не писать сразу на нормальной грамматике, например WEB.ATG на CoCo/R.

заодно, будет легко портировать потом под что-то ещё.

а tex-fpc вообще, занятная вещь. например tangle.web + change файлы как диффы порта под FPC к изначальной реализации Кнута => tangle.pas который легко собирается одной кнопкой в PascalXE, например; затем этим tangle легко собирается сам TeX изначальный, и ещё с отдельными патчами – метафонт. там есть примеры, в целом на plain tex webmac.tex стиля вполне достаточно.

затем можно попробовать собрать через gpc более нормальный ISO Pascal: например, Pascal-P5 pascalp5 , Pascal-P6 sf:Pascal-P6 samiam95124.github.io/Pascal-P6 или ещё какой Pascal-P или Pascaline.

опять же, почитывая книжку Pat Terry про напейсание конпеляторов и в идеале – невозбранно, портировав сам TeX изначальный из texbook.web на обероны пассивные, активные или вообще какие-нибудь ады, алголы-68 или PL/I PL/KT (зело компактный конпелятор там всего 1.5 мб, ну чем не паскаль, хотя и PL/1 :))

Маркдауна мне мало (особенно в плане таблиц и того как они там сделаны), а аскидок слишком не нравится.

та же фигня. в итоге, делаю что-то среднее между WEB и TeX классическом, и asciidoc подобным облегченным на BlackBox Component Pascal + CoCo/R CoCo

чтобы из WEB разметки доработанной собирать в .tex и в .pdf и/или в Rich Text родные блекбоксовые *.odc и/или в *.docx, *.odt или ещё в какой IStorage compount document рулением из блекбокса в ком-автоматизацию (запускаемым через литературно-грамотный деплоинг и девопсинг в rich text *.odc с вьюшками и коммандерами с формами и контролами на родном Component Pascal из WEB доработанного).

там вообще-то какая-то конвертация *.odc в .xml или *.odt уже была в компонентах, но почему бы не написать свою, литературно-грамотную? заодно и парсер расчехлю на CoCo/R и книжку Pat Terry почитаю.

или PL/I PL/KT (зело компактный конпелятор там всего 1.5 мб, ну чем не паскаль, хотя и PL/1 :))

вот кстати, жаль что ga68 это Marst Algol-68 в gcc 16 портировали, а pl1gcc похоже застрял – пилит один человек, и проблемы с устаревшей версией примерно такие же как и с gpc (ещё пойди найди версию gcc под который оно последнее собирается).

поэтому, наиболее адекватной после PL/KT от Д. Караваева (кстати, жаль что сайт и сам компилятор PL/KT поддерживать некому) – и наиболее портируемой, по-видимому, является XPL – книжка и компилятор: sf.net/projects/xpl-compiler или здесь: www.cs.toronto.edu/XPL/ teamPLI.net/XPL

ещё на этом есть любопытный StonyBrook Modula-2 Pascal : suny-pascal и sf.net/projects/modcomp-xpl-compiler

что любопытно: это не Top-down, а Bottom-up парсер. через таблицы написан компилятор компиляторов из EBNF грамматики транспиляцией из PL/1 упрощённого/расширенного (X в PL) в си или ещё какой ассемблер.

если в классических конпеляторах виртовского паскаля P2..P4 и P5, или новомодный P6 и Pascaline – есть pcom, pint – компилятор в пи-код, интерпретатор пи-кода

то тут есть XCOM.xpl, XPL.BNF, XMON – монитор и отладчик.

транспиляцией в сишку или ещё какой ассемблер .

в этом смысле, можно смотреть сразу suny-pascal на тему того как PL/1 XPL в паскаль.BNF расширили.

то есть: suny0006_.zip это пример того как XCOM/XMON и симулятор в ISO-Pascal.BNF подобное расширили, из изначальных примеров в книжке XPL про сам XPL на XPL.

Про написание конпеляторов на Unicon тоже была книжка, как бы не сразу у них на сайте.

из книжек unicon.sourceforge.io/ubooks.html идём в

byopl : Build Your Own Programming Language и бложик unicon.org/byopl/blog

Вы такой умный. Расскажите что-нибудь еще.