Как построить AST для проприетарного языка?
Я пытаюсь понять, как построить AST для проприетарного языка. Мне нужно построить AST, чтобы я мог вводить свои правила и рекомендации, чтобы проверить возможные ошибки в исходном коде.
Как можно построить AST? Есть ли книги, статьи, которые могут помочь мне начать. Поможет ли книга драконов о компиляторах?
Пожалуйста, обратите внимание, что я не из CS-фона.
Спасибо
2 ответа
Это довольно большой вопрос. Я чувствую твою боль, так как я также решил эту проблему из не-CS фона. Это заставило меня ценить CS намного больше.
Одна вещь, которую вы, вероятно, увидите в своих исследованиях, это расширенная форма Бэкуса-Наура (EBNF). Это в основном способ описания вашего языка. Создание EBNF для вашего языка поможет вам обдумать, что потребуется компьютеру для его анализа, это поможет.
Возвращаясь к проблеме: вы, вероятно, будете использовать лексер / парсер для построения своего дерева.
Традиционные инструменты для этого - lex и yacc, или их несколько более современные кузены.
Более новый подход - это подход A ntlr. Это очень рекомендуется, но было над моей головой.
Третий подход, который я нашел, - это библиотека pyparsing Python. Это то, с чем я в конечном итоге согласился из-за моего знакомства с Python и понятного способа описания того, что вам нужно для анализа.
Есть много примеров, доступных для pyparsing, который помог. Самым полезным при создании моего парсера я нашел SimpleCalc. Тем не менее, он основан на довольно старой версии pyparsing и является более сложным, чем это необходимо для некоторых мощных операций, которые позже реализовал pyparsing. SimpleArith - похожая, но более новая версия.
Одна вещь, которую я до сих пор не выполнил с помощью pyparsing - это правильный анализ синтаксических ошибок. Однако, похоже, он предоставляет необходимые инструменты для этого.
В любом случае, это не совсем полный ответ на ваш вопрос, но я надеюсь, что он, по крайней мере, укажет вам несколько моментов, с которых стоит начать. Создать парсер для сложного языка нелегко!
Механизмы анализа кода, как правило, требуют достаточно больших сложностей, помимо создания AST.
Чтобы выполнить любой серьезный анализ кода, вам нужно знать значение идентификаторов в коде и где / как они определены ("таблицы символов"), и вам часто нужно знать, как информация перемещается по программе (контроль и анализ потока данных), Вам нужен механизм для поддержки всего этого, а затем вам нужно привязать этот механизм к вашему собственному языку.
Я думаю о восхождении на Эверест в качестве аналогии. Получение ASTs походит на получение в 10000-футовом базовом лагере. Любой ком может сделать это, просто поднявшись по склону, используя базовую технологию (походные ботинки). Восхождение на последние 17 000 футов требует совершенно другой технологии, преданности делу и плана, и большинство людей, пройдя первые 10000 футов, просто не готовы к остальной части поездки. (У меня есть некоторый опыт здесь, проверьте мою биографию).
Это все довольно подробные темы, и ваше отсутствие опыта работы с CS сделает вашу дорогу довольно трудной. (Однако все мы начинаем где-то, так что это действительно амбиции). Книга Дракона - отличный ресурс, который поможет вам понять, что делает этот механизм и зачем он вам нужен; существует множество других хороших книг по компиляторам, которые, как правило, также будут полезны. Но вы должны быть готовы к серьезному чтению.
Один из способов подняться по кривой - использовать инструмент, в котором большая часть этого механизма уже разработана и внедрена для вас группой компьютерных специалистов, имеющих опыт создания таких инструментов. Тогда ваша проблема значительно уменьшится: вам нужно только научиться использовать то, что они предоставили, а не пытаться выяснить, что вам нужно (большинство людей никогда не пройдут стадию AST) и внедрить все необходимые механизмы поддержки.
ANTLR (уже упоминавшийся, сделанный довольно хорошим профессором CS) является своего рода тем, что он предоставляет возможности синтаксического анализа, позволяет вам определять, как строятся AST, и как процедурно пролезать через получившиеся AST. Но это не дает многого другого, что вам нужно для вашей задачи.
Наш инструментарий реинжиниринга программного обеспечения DMS предоставляет все средства, которые я упомянул в первом абзаце, а затем и некоторые. Одно из первых отличий, которое вы заметите при работе с DMS, заключается в том, что вам нужно предоставить только грамматику; он будет строить AST без дополнительной помощи с вашей стороны.
Вы можете получить представление о том, на что похожа работа с DMS, на этом примере DMS, примененного к алгебре и исчислению средней школы. В частности, он показывает, как легко определить простую грамматику для алгебры / исчисления, а затем можно манипулировать "программами" на этом языке. Это приложение, которое "преобразовывает" код, а не анализирует его, но основы те же.
"Настоящее" приложение DMS, которое проанализировало ваш проприетарный язык, будет значительно сложнее.