Почему бы нам не сохранить синтаксическое дерево вместо исходного кода?

У нас много языков программирования. Каждый язык анализируется и синтаксис проверяется перед переводом в код, поэтому создается абстрактное синтаксическое дерево (AST).

У нас есть это абстрактное синтаксическое дерево, почему бы не сохранить это синтаксическое дерево вместо исходного кода (или рядом с исходным кодом)?

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

Каковы плюсы и минусы этого подхода?

Пробелы и комментарии

Обычно AST не включает пробелы, ограничители строки и комментарии.

Значимое форматирование

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

Код, который не может быть скомпилирован

Хотя многие синтаксические анализаторы очень устойчивы к отсутствующему синтаксису, код с ошибками часто приводит к очень странному синтаксическому дереву, которое прекрасно работает до тех пор, пока пользователь не перезагрузит файл. Когда-нибудь делали ошибку в вашей IDE, и вдруг у всего файла были "волнистые следы"? Представьте, как это будет перезагружено на другом языке.

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

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

Как уже отмечали другие, почти нет двух языков с идеальным соотношением функций. Наиболее близким, на мой взгляд, является VB и C #, или JavaScript и CoffeeScript, но даже тогда VB имеет такие функции, как литералы XML, которые не совсем имеют эквиваленты в C #, и преобразование JavaScript в CoffeeScript может привести к большому количеству литералов JavaScript.

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

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

Действительно, это разумная идея. В 1990-х годах у Microsoft был исследовательский проект, чтобы сделать это почти точно .

На ум приходят несколько сценариев.

Первое довольно тривиально; как вы говорите, AST может отображаться в разных представлениях в зависимости от предпочтений разных программистов для таких вещей, как интервалы и так далее. Но хранение AST является чрезмерным для этого сценария; просто напиши себе симпатичный принтер. Когда вы загружаете файл в ваш редактор, запустите pretty-printer, чтобы перевести его в предпочитаемый вами формат, и верните его в исходный формат при сохранении.

Второй интереснее. Если вы можете сохранить абстрактное синтаксическое дерево, то изменение кода становится не текстовым, а скорее синтаксическим. Рефакторинг, в котором код перемещается, становится намного проще для понимания. Недостатком является, конечно, то, что написание алгоритмов древовидной разности не совсем тривиально и часто должно выполняться для каждого языка. Text diff работает практически для любого языка.

Третий больше похож на то, что Симони задумал для преднамеренного программирования: что фундаментальные понятия, общие для языков программирования, - это то, что сериализуется, и тогда у вас будут разные взгляды на эти понятия, представленные на разных языках. Хотя это прекрасная идея, уродливый факт заключается в том, что языки достаточно различаются по своим деталям, поэтому подход с наименьшим общим знаменателем на самом деле не работает.

Короче говоря, это прекрасная идея, но это огромный объем дополнительной работы для сравнительно небольшой выгоды. Вот почему вряд ли кто-то делает это.

Вы можете утверждать, что это именно то, что байт-код в .NET. Рефлекторная программа Infact Redgate переводит байт-код обратно в ряд языков программирования .NET.

Однако есть проблемы. Синтаксис зависит от языка, поскольку есть вещи, которые вы можете представлять на одном языке, которые не представлены на других языках. Это происходит в .NET, где C ++ является единственным языком .NET, который имеет доступ ко всем 7 уровням доступа.

Вне среды .NET все становится намного сложнее. Каждый язык затем начинает иметь свой собственный набор связанных библиотек. Было бы невозможно отразить общий синтаксис как в C, так и в Java, который отражал бы одинаковое выполнение инструкций, поскольку они решали симулированные задачи самыми разными способами.

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

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

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

Я думаю, что наиболее важные моменты таковы:

• Там нет никакой выгоды. Вы сказали, что это будет означать, что каждый может использовать свой любимый язык. Но это не так - использование представления синтаксического дерева исключает только синтаксические различия, но не семантические. В некоторой степени это работает для очень похожих языков - таких как VB и C # или Java и Scala. Но даже не там полностью.

• Это проблематично. Вы получили свободу языка, но вы потеряли свободу инструментов. Вы больше не можете читать и редактировать код в текстовом редакторе или даже в любой IDE - вы зависите от конкретного инструмента, который говорит в вашем представлении AST как для чтения, так и для редактирования кода. Здесь ничего не получено.

  Чтобы проиллюстрировать этот последний момент, взглянем на RealBasic, который является частной реализацией мощного базового диалекта. Какое-то время казалось, что язык может взлететь, но он полностью зависел от производителя, так что вы могли просматривать код только в их IDE, поскольку он был сохранен в проприетарном нетекстовом формате. Большая ошибка

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

С другой стороны, если вы сохраняете только AST, вы теряете такие вещи, как комментарии, которые невозможно восстановить.

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

Например, в X ++ есть оператор while, который не может быть написан на C # без большого количества дополнительного кода (дополнительные классы, дополнительная логика и т. Д.). http://msdn.microsoft.com/en-us/library/aa558063.aspx

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

Язык X имеет ключевое слово K, которое переводится в AST на 4 выражения: S1, S2, S3 и S4. AST теперь переведен на язык Y, и программист меняет S2. Что теперь происходит с переводом обратно в X? Код переводится как 4 утверждения вместо одного ключевого слова ...

Последний аргумент против подхода AST - это функции платформы: что происходит, когда функция встроена в платформу? Как .NET Environment.GetEnvironmentVariable. Как вы переводите это?

Существует система, построенная вокруг этой идеи: JetBrains MPS . Редактор немного странный или просто другой, но в целом это не такая большая проблема. Самая большая проблема, хорошо, что это не текст больше, поэтому вы не можете использовать любого из обычных текстовых инструментов - другие редакторов, grep, sed, слияние и дифференциалов инструментов и т.д.

На самом деле существует несколько продуктов, обычно называемых «языковыми инструментами», которые хранят AST и представляют в своих редакторах «проекцию» AST на конкретный язык. Как сказал @ sk-logic, MPS JetBrains является одной из таких систем. Другим является Intentional Workbench от Intentional Software.

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

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

Вы читали мои мысли.

Когда я прошел курс по компиляторам несколько лет назад, я обнаружил, что если вы берете AST и сериализуете его с префиксной нотацией вместо обычной инфиксной нотации и используете круглые скобки для разделения целых операторов, вы получаете Lisp. Хотя я узнал о Scheme (диалекте Lisp) в своих исследованиях старшекурсников, я так и не получил за это высокую оценку. В результате этого курса я определенно оценил Лисп и его диалекты.

Проблемы с тем, что вы предлагаете:

1. трудно / медленно составить AST в графической среде. В конце концов, большинство из нас может печатать быстрее, чем мы можем двигать мышью. И все же, возникает вопрос: «Как вы пишете программный код с планшета?» Печатание на планшете медленное / громоздкое по сравнению с клавиатурой / ноутбуком с аппаратной клавиатурой. Если бы вы могли создать AST, перетаскивая компоненты из палитры на холст на большом, программирование устройства с сенсорным экраном на планшете могло бы стать реальной вещью.

2. немногие из наших существующих инструментов поддерживают это. У нас десятилетия разработки, заключающейся в создании все более сложных IDE и все более интеллектуальных редакторов. У нас есть все эти инструменты для переформатирования текста, сравнения текста, поиска текста. Где инструменты, которые могут выполнять поиск по регулярному выражению по дереву? Или разница двух деревьев? Все эти вещи легко сделать с помощью текста. Но они могут сравнивать только слова. Измените имя переменной так, чтобы слова были разными, но семантическое значение одинаково, и эти инструменты сравнения столкнутся с проблемами. Такие инструменты, разработанные для работы с AST вместо текста, позволят вам приблизиться к сравнению семантического значения. Это было бы хорошо.

3. в то время как преобразование исходного кода программы в AST является относительно понятным (у нас есть компиляторы и интерпретаторы, не так ли?), превращение AST в программный код не так хорошо понято. Умножение двух простых чисел для получения большого составного числа является относительно простым, но разложить большое составное число обратно на простые числа гораздо сложнее; вот где мы с разбором против декомпиляции AST. Вот где различия между языками становятся проблемой. Даже в пределах определенного языка есть несколько способов декомпилировать AST. Например, перебирая коллекцию объектов и получая какой-то результат. Использовать цикл for, проходящий через массив? Это было бы компактно и быстро, но есть ограничения. Используйте итератор какой-то, работает над коллекцией? Эта коллекция может иметь переменный размер, что добавляет гибкости за счет (возможно) скорости. Уменьшение карты? Более сложный, но неявно распараллеливаемый. И это только для Java, в зависимости от ваших предпочтений.

Со временем усилия по разработке будут израсходованы, и мы будем разрабатывать с использованием сенсорных экранов и AST. Печатание станет меньше необходимости. Я вижу, что в качестве логического продвижения от того, где мы находимся, глядя на то, как мы сегодня используем компьютеры, это решит # 1.

Мы уже работаем с деревьями. Лисп - это просто сериализованный AST. XML (и HTML, по расширению) - это просто сериализованное дерево. Для поиска у нас уже есть пара прототипов: XPath и CSS (для XML и HTML соответственно). Когда будут созданы графические инструменты, которые позволят нам создавать селекторы и модификаторы в стиле CSS, мы решим часть # 2. Когда эти селекторы могут быть расширены для поддержки регулярных выражений, мы будем ближе. Все еще ищу хороший графический инструмент сравнения для сравнения двух документов XML или HTML. По мере того, как люди будут разрабатывать эти инструменты, № 2 будет решена. Люди уже работают над такими вещами; их просто нет, пока.

Единственный способ, с помощью которого я смогу декомпилировать эти AST в текст на языке программирования, - это поиск цели. Если я изменяю существующий код, цель может быть достигнута с помощью алгоритма, который делает мой измененный код максимально похожим на исходный код (минимальная разность текстов). Если я пишу код с нуля, целью может быть наименьший, самый трудный код (вероятно, цикл for). Или это может быть код, который распараллеливается настолько эффективно, насколько это возможно (скорее всего, карта / сокращение или что-то, связанное с CSP). Таким образом, один и тот же AST может привести к значительному различию кода, даже на одном языке, в зависимости от того, как поставлены цели. Разработка такой системы решит проблему № 3. Это будет сложным в вычислительном отношении, то есть нам, вероятно, понадобится какая-то схема клиент-сервер,

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

Это довольно легко, если вы используете редактор, такой как Emacs . Изменение стиля форматирования всего файла - это задание из трех команд.

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

Трудно читать и изменять AST вместо исходного кода.

Однако некоторые инструменты, связанные с компилятором, позволяют использовать AST. Байт-код Java и промежуточный код .NET работают аналогично AST.

это хорошая идея; но AST каждого языка отличается от любого другого.

единственное исключение, которое я знаю, касается VB.NET и C #, где Microsoft утверждает, что они «абсолютно одинаковые языки с разным синтаксисом». Даже другие языки .NET (IronPython, F # и т. Д.) Отличаются на уровне AST.

То же самое с языками JVM, все они нацелены на один и тот же байт-код, но языковые конструкции различны, что делает его разными языками и разными AST.

Даже «тонкослойные» языки, такие как CoffeScript и Xtend, в значительной степени разделяют теорию базовых языков (JavaScript и Java соответственно); но ввести концепции более высокого уровня, которые (или должны быть) сохранены на уровне AST.

если бы Xtend мог быть восстановлен из Java AST, я думаю, он был бы определен как «uncompiler» Java-to-Xtend, который волшебным образом создает абстракции более высокого уровня из существующего кода Java, не так ли?