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

111

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

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

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

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

Calmarius
источник
37
Лисп обычно пишется как абстрактное синтаксическое дерево. Он не завоевал популярность среди алголоподобных языков.
Дэвид Торнли
2
Я не могу поверить, что Дэвид единственный, кто упомянул, что программы на LISP представляют собой абстрактное синтаксическое дерево.
WuHoUnited
3
В дополнение к другим пунктам: AST - это даже не последнее. Это также не займет много времени, чтобы создать AST из кода. Когда я запускаю StyleCop в своем небольшом проекте VS2010, он очень быстро запускает десятки различных правил на основе AST для тысяч строк кода (иногда в секунду или две). Также довольно легко расширить StyleCop и написать собственное правило. Я подозреваю, что синтаксический анализ исходного кода в AST является хорошо понятной и относительно простой проблемой. В первую очередь это хороший язык, оптимизация и все библиотеки, которые сложны, не разбираются.
Работа
1
После проанализирован кода, это не так легко генерировать код для другого языка. (Как бы вы перевели неявное объединение Пролога в C?). В основном у вас есть AST для оригинальной программы.
Ира Бакстер
3
Проблема синтаксического разбора хорошо понятна технически, но разбирать C или C ++ непросто, потому что это грязные противные языки. Многие компиляторы анализируют C или C ++ для AST: Clang, GCC, ... Они не предназначены для хранения программ, и GCC очень хочет быть компилятором, а не инструментом анализа программ. Наш DMS Software Reengineering Toolkit анализирует многие диалекты C и C ++, производит AST, таблицы символов и различные виды артефактов анализа потока. Большой плюс этого подхода - способность создавать автоматизированные инструменты изменений. semanticdesigns.com/Products/DMS/DMSToolkit.html
Ира Бакстер

Ответы:

72

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

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

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

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

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

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

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

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

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

Личный опыт:

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

Кевин Маккормик
источник
9
Есть парсеры, которые фиксируют комментарии и макет в AST. Наш DMS Software Rengineering Toolkit прекрасно справляется с этой задачей. Это нелегко с нелегальным кодом; у него есть точный синтаксический анализатор языка.
Ира Бакстер
2
На самом деле есть инструмент, который преобразует Javascript в CoffeeScript , поэтому я думаю, что JavaScript и CoffeScript взаимно переводимы без литералов Javascript.
Питер Олсон
Интересный инструмент, Питер, я не знал об этом.
Кевин Маккормик
+1 за содержательное форматирование и интересный личный опыт. - Пробелы не важны для вопроса, и комментарии могут быть сохранены. Коды с ошибкой было бы легче исправить в любом случае, и, конечно, часть вопроса «один язык, чтобы управлять ими всеми» была недоступна.
Cregox
43

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

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

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

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

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

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

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

Эрик Липперт
источник
3
На самом деле, вы можете сделать разность деревьев независимым от языка способом. Вам нужны языковые парсеры для построения деревьев. Посмотрите нашу линейку инструментов Smart Differencer, которая сравнивает AST для многих языков. Все они используют один и тот же базовый механизм сравнения. semanticdesigns.com/Products/SmartDifferencer
Ира Бакстер
1
Я надеюсь, что когда-нибудь в Visual Studio мой стиль-довольно-печатать-при-нагрузке-команд-стиль-довольно-печатать-при-сохранить ... надеялся на годы ... пока не повезло ...
Роман Старков
19

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

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

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

Майкл Шоу
источник
5
Вы когда-нибудь пытались декомпилировать MSIL, созданный F #?
SK-logic
12

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

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

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

PSR
источник
5
Вы следили за развитием проекта Microsoft " Roslyn " по открытию компиляторов VBc и C # в качестве API-интерфейсов? Доступна предварительная версия.
Carson63000
11

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

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

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

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

Конрад Рудольф
источник
4
Потенциальным преимуществом было бы то, что он мог бы закончить бесконечные дебаты, такие как «табуляция против пробелов», «Unix против оконной привязки / отступа», «Префиксы m_ перед членами или нет», потому что их можно превратить в простые опции IDE.
nikie
1
@nikie Правда, но вы уже можете сделать это, используя инструменты переформатирования, например astyleUnniversalIndent. Нет необходимости в тайных двоичных форматах.
Конрад Рудольф
2
Реальная выгода - это возможность иметь инструменты diff / patch, которые помогут вам лучше понять, что действительно изменилось. Но это, похоже, подразумевает необходимость в совершенно новом наборе инструментов для контроля версий, что является серьезным ограничением.
Питер Тейлор
1
Если вы думаете, что «нет пользы», значит, вы не видели инструментальные средства домена Intentional Software.
Крейг Stuntz
1
Короче говоря, одну и ту же логику можно спроецировать в разные представления, не все текстовые, что делает правила доступными для непрограммистов. Например, эксперты в области, такие как актуарии, могут написать актуарные части страхового заявления. Как DSL за исключением того, что не ограничивается этим представлением. Хотя это очень сильно связано с вопросом. Там хорошая демонстрация .
Крейг Штунц
6

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

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

Tesserex
источник
6
и если вы сделаете комментарии частью синтаксического дерева (с узлами комментариев, которые могут быть потомками чего угодно)?
храповик урод
Наши инструменты делают именно это. Смотрите мои другие комментарии в этой теме.
Ира Бакстер
4

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

Например, в 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. Как вы переводите это?

Виктор Хурдугачи
источник
4

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

SK-логика
источник
2
... но вы получаете много функций редактора из коробки. Попробуйте немного расширить этот ответ, это очень интересная технология, которая заслуживает более подробного описания преимуществ, заключающихся в том, что исходный код не хранится в виде текста. Например, как я ответил на этот вопрос на вкладках против пробелов .
Стивен Джеурис
AST может быть сохранен в удобочитаемом формате, а не в двоичном формате. можете ли вы теперь с помощью инструментов Linux, например, заменить каждый метод в коде, который принимает в качестве параметра сериализуемый объект? было бы очень трудно написать, но AST сделать это очень легко.
IAdapter
1
Люди постоянно делают эту ошибку. AST делает это проще, чем если бы у вас был только сырой текст. Но для чего-то интересного вам нужна куча дополнительной информации: управление и поток данных, таблицы символов, анализ диапазона, ... AST помогают, но являются лишь небольшой частью того, что действительно необходимо.
Ира Бакстер
@ Ира Бакстер, конечно, легче с AST. Но гораздо сложнее интегрироваться в существующую инфраструктуру.
SK-logic
4

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

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

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

Ларри Обриен
источник
«языковая рабочая среда» не обязательно должна основываться на хранении необработанных AST. Они также могут быть ориентированы на синтаксис простого текста, см., Например, meta-alternative.net/pfront.pdf (и этот фактически расширяет редактор Visual Studio и Emacs с любым eDSL, реализованным поверх него).
SK-logic
Это интересная статья; это напоминает мне (в амбициях, совсем не в реализации) инструмент под названием SugarJ, который был представлен на SPLASH / OOPSLA несколько недель назад: uni-marburg.de/fb12/ps/research/sugarj
Larry OBrien
интересно, я тоже попробую.
SK-logic
3

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

Когда я прошел курс по компиляторам несколько лет назад, я обнаружил, что если вы берете 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. Это будет сложным в вычислительном отношении, то есть нам, вероятно, понадобится какая-то схема клиент-сервер,

Meower68
источник
1

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

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

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

Густав Бертрам
источник
1
Тогда вам все еще понадобится семантическая разность и слияние (т. Е. Снова уровень AST).
SK-logic
Нет, редактор переформатируется обратно в командный стиль для хранения источника - так что вы сравниваете один тип источника с тем же типом.
Густав Бертрам
Хороший момент, единственное нормализованное представление решает все проблемы
SK-logic
1
Нет, это только решает проблемы разделения двух файлов для идентификации. Если вы хотите увидеть различия между файлами, в идеале вам нужно что-то, что понимает структуру. Я люблю свои emacs, но он не понимает структуру.
Ира Бакстер
Emacs великолепен, но я никогда не использую его для сравнения. Чтобы проверить исходное дерево перед регистрацией, я всегда использую meld . Это на самом деле понимает SVN и мерзавец. В Windows я бы использовал WinMerge, вероятно, в сочетании с черепахой.
Густав Бертрам
1

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

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

umlcat
источник
1
Надежнее модифицировать AST с помощью механических инструментов, чем с помощью текста. Вы можете сделать это с помощью шаблонно-направленных изменений. См. Semanticdesigns.com/Products/DMS/ProgramTransformation.html
Ира Бакстер,
2
Скажи это LISPers сейчас ...
hugomg
@ Ира Бакстер. Я знаю, что на самом деле я работаю над пользовательским визуальным инструментом, который работает непосредственно с AST, однако иногда разработчикам приходится работать с текстом вместо визуального. Некоторые AST также представлены в виде более короткого языка программирования в тексте.
umlcat
@umlcat, расскажите подробнее о своей работе над визуальным инструментом для AST.
Даниэль Альбушат
@Daniel Albuschat. Я работаю над проектом на языке программирования для домашних животных. Сложно реализовать его синтаксический анализатор, поэтому на данный момент я пропустил его и создал инструмент для отображения AST (формы с управлением в виде дерева) и непосредственного добавления выражений. И можете сделать наоборот, сгенерировать код из AST.
umlcat
0

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

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

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

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

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

Хавьер
источник
1
Как человек, хорошо знакомый как с компиляторами C #, так и с VB, я могу вам сказать, что они, безусловно, похожи, но есть достаточно важных деталей, которые настолько различаются, что нецелесообразно рассматривать их как «один и тот же язык с разным синтаксисом». Мы рассматривали возможность сделать это для проекта Roslyn; создание единого компилятора, который мог бы компилировать оба языка с одинаковыми возможностями - и после долгих дебатов решил пойти с двумя компиляторами для двух языков.
Эрик Липперт
@EricLippert: это позор. не то чтобы я когда-либо планировал изучать любой язык, но это звучало как хорошее исключение. Я думаю, что htat оставляет пример «lisp-like-Dylan» и «algol-like-Dylan» как единственный «один и тот же язык с разными синтаксисами».
Хавьер