Comments 16
Правильно ли я понимаю, что если идти в анализе дальше, то по сути можно дойти уже до некой виртуальной машины, которая интерпретирует входной код и ищет в процессе ошибки?
Нет ли тут аналогии с антивирусами, которые в процессе анализа вирусов дошли до интерпретации их кода, чтобы оценить его результата?
Если абстрагироваться от строгих значений терминов, то мы уже интерпретируем входной код и в процессе ищем ошибки. В конце концов, статический анализатор это буквально половинка компилятора (та, которой не надо генерировать код, так что половинка не в плане объёма), и пересекается по функционалу, собственно, с интерпретатором. Так что двигаться дальше особо и некуда - непосредственное выполнение кода это уже плоскость динамического анализа, который является отдельной дисциплиной.
В нашем случае был выбран ANTLR v4. Так как инструмент тоже написан на Java, с ним очень удобно работать. И это помимо того, что за долгие годы развития он начал справляться со своей задачей очень хорошо.
На самом деле уже не очень хорошо. Проект в стадии минимальной поддержки, т.е. крупных релизов уже не выходило несколько лет. А за это время в нем накопилось уже большое количество проблем.
По своей классификации оно, кажется, будет ближе к дереву разбора. Но, на самом деле, здесь уже можно остановиться и начать работать с ним.
Это и есть дерево разбора - ANTLR 4 генерирует именно его. Правда это дерево не очень достоверное - типы в нем не очень точные, а ошибки парсинга в нем не сохраняются.
Настроить ANTLR так, чтобы он сразу выдавал нужный AST. Звучит максимально правдоподобно, но всё ещё нужно изучать сам ANTLR, что тоже будет ощутимой тратой времени.
А чем вас не устраивает стандартный Visitor или Listener (Walker) для преобразования дерева в нужный формат? Их тоже можно генерировать с помощью ANTLR 4. С учетом того, что вы уже и так изучили ANTLR, данное дообучение по использованию Visitor выглядит минимальным.
Было бы преувеличением сказать, что ANTLR был изучен очень глубоко, поэтому со всем любопытством спрошу: а такой есть? :)
Видели, что что-то похожее было для третьей версии (в том числе поэтому и отметил вариант как максимально правдоподобный), но в разумные сроки найти что-то для четвёртого не вышло, поэтому решили сделать свою реализацию Listener-a.
Было бы преувеличением сказать, что ANTLR был изучен очень глубоко, поэтому со всем любопытством спрошу: а такой есть? :)
Конечно есть. Я сейчас заметил, что это плохо описано в официальной документации, но можно почитать здесь: https://tomassetti.me/listeners-and-visitors/ Либо просто поискать в гугле по словам antlr 4 visitor.
А, кажется, я не так понял первое сообщение, либо невнимательно прочитал материал по ссылке. Мы и наследуемся от сгенерированного BaseListener-а, тут обошлось без велосипеда. В статье указано его использование (LuaAstParser).
ParseTreeWalker walker = new ParseTreeWalker();
var listener = new LuaAstParser();
walker.walk(listener, new LuaParser(
new CommonTokenStream(lexer)
).start_());
return listener.getFile();
Единственное, сейчас увидел что можно было немного сэкономить время и не строя дерево разбора сразу построить AST.
А так я сначала подумал, что его тоже можно было сгенерировать файлом грамматики/декларативной настройкой, и об этом же пункт в статье.
И да, раз это просто экспериментальный проект, далее по тексту называть наш анализатор будем Mun.
Кажется, кто-то вдохновлялся KSP.
Применительно к Lua, проект с названием Mun уже существует. Но раз это тестовый анализатор, то это ни на что не влияет.
Любопытная статья! Я, наверное, читаю слишком через строчку, а вы весь код где-то выложили или только на кусочки в статью нарезали? Я вот недавно писал игрушечный компилятор за выходные (тоже два дня :), было бы интересно к нему прикрутить подобный анализатор на пару-тройку правил.
Спасибо за добрые слова!
Я вот недавно писал игрушечный компилятор за выходные (тоже два дня :)
Не поверите, но именно ваш цикл во многом вдохновил на эту статью (как и на её название), так что очень рад видеть вас в комментариях :)
вы весь код где-то выложили или только на кусочки в статью нарезали?
Код и правда нигде не выкладывался, и как-то не планировали это делать. Но в статье большая его часть и так приведена. А так, если интересна тема, то можно и что-то совместное попробовать организовать :)
Конечно, интересно. Только я в этом не понимаю ничего, никогда не обучался информатике :)
У меня очень примитивный игрушечный язык, поэтому всякие ошибки типа вылезания за границы и вообще арифметики указателей просто нет. А вот всякие if true и использование неинициализированных переменных можно попробвать и половить, опять же, чисто для развлечения и иллюстрации. Для if true, насколько я понимаю, нужно делать flow analysis.
Пока что я встречал такое словосочетание только в примерах оптимизирующих компиляторов, когда мы переводим AST уже в какой-нибудь трёхадресный код. А как это выглядит в случае анализатора?
Вообще у меня в планах было добавить оптимизации ещё...
Так как анализатор это и есть кусочек компилятора, то, в идеале, вычисление значений как раз лучше и делать через анализ потока данных, предварительно переведя код программы в ssa/трёхадресный.
Но, в целом, не обязательно - никто не запрещает изобрести велосипед, на любом из этапов. Мы так и поступили в статье, где просто запоминали литералы :).
Если делать прямолинейно, то можно пробовать вычислять значения обходя AST. Делая всё вручную код будет громоздким, но для ленивого решения сойдёт. Можно использовать сторонние фреймворки, у нас давным-давно был прототип, в котором визитор просто ходил по AST и скармливал z3 значения переменных, и оно даже как-то работало, как раз на always true условия.
Менее прямолинейным будет по ходу дела помечать методы (например, если в методе условие, использующее аргумент), тогда встречая инвокацию можно сразу что-то понять. Не очень по книжке и имеет много других минусов, но сравнительно просто и у нас кое-где используется.
Более правильным будет построение control flow и def/use графов, используя которые будет проще работать с разными ветвлениями (ибо обходя AST мы сразу не знаем, в какой ветке выполнения находится текущий узел - надо гулять по дереву, чтобы узнать). Трёхадресный код тут желателен (в том числе чтобы меньше концентрироваться на синтаксисе), но можно обойтись и без него.
С неинициализированными переменными и подобными проверками проще, тут можно обойтись простым анализом по дереву, предварительно запомнив области видимости переменных (что мы и сделали в статье).
Ну SSA строить у меня в планах как раз и было, но скажите, пожалуйста, если мы переведём код в SSA, и будем делать анализ IR, то найти всякого в IR можно. Но как сохранить соответствие с исходным кодом? Мы же хотим сигнализировать не просто о проблеме, а о конкретной строчке исходного кода...
Хороший вопрос. В это дело я сам не углублялся, но, кажется, сильно уйти от банальной метаинформаци о позиции не выйдет. Можно придумать разные оптимизации (хранить её в отдельном файле, или создавать только в отладочном режиме), но ультимативно подход останется тем же, а какого-то единого для компиляторов стандарта, кажется, нет.
Как сделать анализатор кода за два дня