LINUX.ORG.RU

Разработка Neparsy - языка представления результатов парсинга

 , , , ,


0

2

Здравствуйте!

Хочу представить на обозрение результаты месяца разработок, а именно язык представления результатов парсинга Neparsy.

Парсинг — это первый этап компиляции любого языка программирования, преобразование текста программы в синтаксическое дерево. После разбора в такое дерево у компилятора ещё много дел: провести семантический анализ, оптимизации, преобразование в ассемблер/машинный код. Идея разбить создание компилятора на несколько частей не нова: компиляторы LLVM состоят из фронтенда, компилирующего язык в универсальный ассемблер некого обобщённого процессора, и бекэнда, производящего оптимизации и преобразование в код целевой архитектуры. Neparsy пытается подойти к задаче с обратной стороны и облегчить разработку именно фронтенда. Он создаёт новый слой абстракции где парсинг уже произведен. Внутри такого слоя облегчается задача трансляции между языками. Разновидности языка Neparsy для представления результатов парсинга различных языков программирования называются диалектами. Например, разрабатываемый в настоящее время диалект для языка D обозначается Neparsy:D.

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

Язык Neparsy имеет очень простой для парсинга Lisp-подобный синтаксис (менее 200 строчек для парсера, для сравнения парсер языка C на bison занимает около 3000 строк).

Вкратце суть Neparsy на примере вызова функции и ещё одной постфиксной функции выглядит так:

(function arg1 arg2 arg3).(postfix-function arg1 arg2)

Помимо этого он имеет одну хитрость:

(func (. arg1 arg2).multi-postfix)

Что аналогично навешиванию постфиксной функции сразу на несколько аргументов, т.е.:

(func arg1.multi-postfix arg2.multi-postfix)

Помимо названия функции или оператора в начале скобки указывается тип через # и метка через @:

(*#unary@label pointer)

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

(#. str f1 (#[ 2) f2)

Означает str.f1[2].f2

(#" Литерал строки с пробелами)

А вот пример if-else-if-else конструкции:

(#if
 (условие1).(#body ветка1)
 (условие2).(#body ветка2)
 (#else).(#body else-ветка))

Neparsy также имеет оригинальное графическое представление в виде круговых диаграмм, что и представлено на скриншоте.

За месяц удалось написать:

  • Редактор круговых диаграмм, с клавиатурным управлением. Поддержка мыши — начальная.
  • Парсер кода D, того подмножества D на котором написан сам Neparsy. Причём лексический анализатор и парсер написаны (нарисованы?) непосредственно в редакторе Neparsy.

Репозиторий проекта на github: https://github.com/unDEFER/neparsy

Ветка на языке neparsy: https://github.com/unDEFER/neparsy/tree/neparsy

На скриншоте можно видеть: 4 структуры, функцию typeColor, класс Iface в котором развёрнута функция updateView, а в ней инициализацию двух переменных (большое выражение: double nr = (expr.a1 + expr.a2)/2 - 180), блок «#if», ещё одну переменную ri без инициализации, блок «#while».

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

Управление:

  • Стрелки — навигация
  • Запятая — добавить дочерний узел
  • Пробел — добавить братский узел
  • Точка — преобразовать узел в дочерний
  • Ctrl+Запятая — добавить постфиксный узел/расширить его влияние на узел влево
  • Ctrl+Точка — добавить постфиксный узел/сузить его влияние на узел вправо
  • Shift+Влево, Shift+Вправо — Переместить текущий узел влево или вправо.
  • Ctrl+Стрелки — навигация по полям (когда диаграмма полей видна внизу левой панели)
  • Del — удалить узел и всех потомков
  • Ctrl+Backspace — «отстричь» потомков
  • Ctrl+S — сохранить в формат neparsy
  • Ctrl+D — сохранить в .d-формат (@D модули)
  • Ctrl+L — сгенерировать лексический анализатор из файла описания синтаксиса (@Lexer модули)
  • Enter/Escape — выход из режима редактирования узла

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

>>> Просмотр (1366x768, 258 Kb)

★★★★★

Проверено: hobbit ()

У меня просьба: А можно после фразы «Хочу представить на обозрение результаты месяца разработок, а именно язык представления результатов парсинга Neparsy.» сразу сказать, какие практические задачи оно решает? Для тех, кто не в теме языков представления результатов парсинга, так сказать... Вот совсем по-простому «чтобы что?»

crypt ★★★★★ ()
Последнее исправление: crypt (всего исправлений: 2)
Ответ на: комментарий от crypt

Так оно так вроде и есть. Следующий абзац после этой фразы раскрывает практическую задачу, которую решает Neparsy.

unDEFER ★★★★★ ()
Ответ на: комментарий от unDEFER

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

че? что такое результаты создания парсера? «конечного продукта»?? а результат парсинга - это продукт?? «а не заниматься созданием компилятора»? че?! а при чем тут компилятор???

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

crypt ★★★★★ ()
Последнее исправление: crypt (всего исправлений: 2)
Ответ на: комментарий от crypt

А так не лучше? Я просто стараюсь максимально кратко, т.к. не видел здесь ни разу подробного введения в какую-либо тему.

unDEFER ★★★★★ ()
Последнее исправление: unDEFER (всего исправлений: 1)
Ответ на: комментарий от unDEFER

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

crypt ★★★★★ ()
Последнее исправление: crypt (всего исправлений: 1)
Ответ на: комментарий от unDEFER

все ок, я просто хотел сказать спасибо за то, что потратил время:)

crypt ★★★★★ ()
Последнее исправление: crypt (всего исправлений: 2)

Neparsy пытается подойти к задаче с обратной стороны и облегчить разработку именно фронтенда.

Ничего не понятно, но очень интересно.

Oldboy ()

Если транслировать диалект Neparsy нового языка в существующий диалект Neparsy (пока в разработке находится диалект Neparsy:D) легко, то разработка компилятора может быть значительно облегчена.

Т.е. он предназначен для представления результатов парсинга произвольного языка, а не только D, и предлагается как некоторого рода стандартный формат для использования разными тулами/частями компилятора? Как у него с расширяемостью? Допустим, что нужно сделать, если у нового ЯП есть синтаксические конструкции, которые нельзя представить средствами Neparsy? Или надо писать диалект Neparsy:$PROGRAMMING_LANGUAGE с нуля?

Насколько он гибкий, может ли он представлять какие-нибудь «экзотические» литералы типа -USD$1'234.56789 и ~r[^https?://]iu, идентификаторы вроде my-func-name?

theNamelessOne ★★★★★ ()
Последнее исправление: theNamelessOne (всего исправлений: 1)
Ответ на: комментарий от theNamelessOne

Совершенно верно, произвольного. И да, хотелось бы стандартизировать для использования компиляторами.

С нуля диалект разрабатывать не нужно - по максимуму использовать уже разработанные конструкции и расширить вновь разработанными для нового языка.

Конкретно с этими идентификаторами вообще проблем нет. Проблемы с символами ()#@ и пробелом. Символ экранирования ещё не выбран. Но скоро я перепишу парсер и учту огрехи, за одно добавив возможность комментариев.

unDEFER ★★★★★ ()

Очень интересно, планирую подтвердить завтра. Правда, некоторые формулировки лучше бы написать понятнее. Например вот это:

Если транслировать диалект Neparsy нового языка в существующий диалект Neparsy (пока в разработке находится диалект Neparsy:D) легко, то разработка компилятора может быть значительно облегчена

без стакана Мозголомной Браги понять довольно тяжело.

hobbit ★★★★★ ()
Ответ на: комментарий от unDEFER

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

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

crypt ★★★★★ ()
Последнее исправление: crypt (всего исправлений: 1)

Он создаёт новый слой абстракции где парсинг уже произведен. Внутри такого слоя облегчается задача трансляции между языками.

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

Mirage1_ ()
Ответ на: комментарий от Mirage1_

В планах попытаться транслировать код Vim с C на D.

Транслятор безусловно получится проекто-зависимым, но демонстрация будет хорошая.

unDEFER ★★★★★ ()

На первый взгляд штука строго завязана на внутреннее отображение данных в мозге автора. Есть примеры использования другими особями Х. сапиенс?

token_polyak ★★ ()
Последнее исправление: token_polyak (всего исправлений: 3)
Ответ на: комментарий от token_polyak

Проекту всего месяц и это первое его упоминание в сети. Так что пока нет.

unDEFER ★★★★★ ()

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

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

Также интересно бы пример этих кругов с какой-нибудь программы на джаве с ее длинными названиями вроде VeryUnderstandableVariableForSavingTax

mydibyje ★★ ()

язык представления результатов парсинга

У меня мозг сломался и я в целом вообще ничего не понял.

LINUX-ORG-RU ★★★★ ()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)
Ответ на: комментарий от mydibyje

Мне неудобно читать текст расположенный по окружности

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

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

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

Также интересно бы пример этих кругов с какой-нибудь программы на джаве с ее длинными названиями вроде VeryUnderstandableVariableForSavingTax

Тут да, косяк. Слишком длинные идентификаторы могут стать слишком мелкими, но пока я не сталкивался и чинить не на чем.

unDEFER ★★★★★ ()

Отлично. Нравятся мне скрины лоровских кулибинов).

«И славен буду я, доколь в подлунном мире, Жив будет хоть один рУсский-кОдер-кулибИн» (с)

KernelPanic ()

Идея, лежащая под этим всем, завораживающая. Надеюсь в будущем увидеть и компилятор =)

elve ()
Ответ на: комментарий от elve

Спасибо, буду стараться довести дело и до готового компилятора.

unDEFER ★★★★★ ()

С большим трудом вроде что-то понял. Это должно быть языко-независимым форматом синтаксического дерева? Каким образом это облегчает написание фронта, дерево же потом надо будет обходить в любом случае и точно также узнавать узлы и т.д.? И какой оверхед на формирование и разбор этого промежуточного представления (примерно)? А где информация о позиции токенов, без которой ни отладочной информации, ни нормальных сообщений об ошибках не будет?

У меня ещё есть большие сомнения по поводу трансляции между языками. Если по AST ещё можно рискнуть вывести программу на другом языке, то по синтаксическому дереву эта затея провалится из-за отсутствие какой-либо семантической информации, кроме самых тривиальных случаев.

xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

Это должно быть языко-независимым форматом синтаксического дерева?

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

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

Дерево обойти гораздо проще, чем парсить с нуля. Пример использования - формирование списка символов в панели слева.

какой оверхед на формирование и разбор этого промежуточного представления (примерно)?

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

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

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

Номер символа в строке после парсинга потеряется, но на этом по-моему смысла его хранить нет.

Если по AST ещё можно рискнуть вывести программу на другом языке,

А чем по-вашему синтаксическое дерево Neparsy не абстрактное? Программу D я по нему уже восстанавливаю.

unDEFER ★★★★★ ()
Ответ на: комментарий от unDEFER

Номер символа в строке после парсинга потеряется, но на этом по-моему смысла его хранить нет.

Не так давно поддержку колонок добавили в DWARF, gdb и потом в компиляторы. Так что в целом людям нужно.

А чем по-вашему синтаксическое дерево Neparsy не абстрактное? Программу D я по нему уже восстанавливаю.

Да, ошибся, чего-то я в примерах конкретное синтаксическое дерево увидел. Но проблема в различиях между языками, дерево из условного Lua в условный Python просто так не преобразовать из-за различий в областях видимости переменных, разных подходах к ООП и т.д. Не вижу чтобы Neparsy тут что-то облегчал, так как вся сложность операции лежит вне самого представления. Разве что может упростить процесс отладки и взаимодействия частей.

xaizek ★★★★★ ()
Ответ на: комментарий от doctorx

Насколько мне известно, лексический анализ это то что обычно происходит на первом этапе парсинга – т.е. разбитие на лексемы.

unDEFER ★★★★★ ()
Ответ на: комментарий от xaizek

Не так давно поддержку колонок добавили в DWARF, gdb и потом в компиляторы.

Не очень понял про gdb, во всяком случае по умолчанию в backtrace никаких номеров колонок нет.

Но проблема в различиях между языками

Проблема глубже. «Универсальный» транслятор инструкция-в-инструкцию написать проще всего только не нужно ибо никакого смысла. Например нет никакого смысла писать транслятор с C на D, который отключит сборщик мусора и будет все malloc/free транслировать в их аналоги на D. В достаточно крупном проекте на C наверняка есть реализация ассоциативных массивов, которую опять же нет смысла транслировать в D. Если трансляцию произвести таким образом, то проект написанным на D не станет, это будет всё ещё C под гримом D.

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

unDEFER ★★★★★ ()

Окей, допустим я придумал сосисочный язык программирования, у меня есть его грамматика в БНФ, как твой непарься мне поможет написать его транслятор в другой схожий язык? Чем это будет лучше lex+yacc+самописный генератор?

cocucka ★★★★★ ()
Ответ на: комментарий от cocucka

Тем и поможет, что «схожий». Вы пишете парсер в структуры neparsy, а генератор уже готов. Т.е. один из трёх членов вашей суммы отваливается.

unDEFER ★★★★★ ()
Ответ на: комментарий от unDEFER

Не очень понял про gdb, во всяком случае по умолчанию в backtrace никаких номеров колонок нет.

А в отладочной информации есть и может использоваться чтобы ходить по нескольким утверждениям в одной строке.

$ echo 'int main(){ return 66; }' | gcc -S -x c -c - -o - -g | grep .loc
.loc 1 1 11
.loc 1 1 20
.loc 1 1 24
xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

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

unDEFER ★★★★★ ()

Одни говорят харе, другие непарься. Лисп в виде круговых диаграмм - метапрог тихонько фалломорфирует. Вроде лисп, но ни слова про макросы.

qaqa ()
Ответ на: комментарий от qaqa

Насчёт макросов есть идеи ввести некое их подобие. Но проработку этого вопроса я отложил до разработки диалекта Neparsy:C. С препроцессором надо однозначно что-то делать и его поддержка должна быть особой.

unDEFER ★★★★★ ()
Ответ на: комментарий от qaqa

метапрог

А я-то уж думал, я один его вспомнил. :))) Теперь я не одинок. Правда, @metaprog пока в заморозке и прокомментировать свои впечатления не сможет.

hobbit ★★★★★ ()
Ответ на: комментарий от unDEFER

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

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

Adamos ()
Ответ на: комментарий от Adamos

Это в теории. Давайте я расскажу о практике применения такого интерфейса.

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

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

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

unDEFER ★★★★★ ()
Ответ на: комментарий от unDEFER

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

abcq ★★ ()
Ответ на: комментарий от qaqa

да сразу напомнило светилу графического программирования почему-то

abcq ★★ ()
Ответ на: комментарий от abcq

Реализация AST у каждого языка своя, а я предлагаю универсализировать.

Насчёт кружков, интерфейс скорее всего будет двигаться в сторону различных представлений для разных объектов (для класса/структуры – своё представление, для переменной своё)

unDEFER ★★★★★ ()
Последнее исправление: unDEFER (всего исправлений: 1)
Ответ на: комментарий от unDEFER

ну написав еще одну вариацию универсальности не получить, да и стандартизация есть как бы это странно не звучало, но дерево остается деревом вне зависимости от языка, в этом и универсализация и стандартизация и подходы одни и те же для работы с ним, что еще надо то?

abcq ★★ ()
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)