KvanTTT Mar 3 2016 at 16:39

Теория и практика парсинга исходников с помощью ANTLR и Roslyn

23 min

40K

Positive Technologies corporate blog Programming *.NET *Compilers *

+31

Comments 19

ilmirus Mar 3 2016 at 19:56

> процесс парсинга не должен прерывать только лишь из-за одной ошибки, а должен корректно восстанавливаться и парсить код дальше (например, после пропущенной точки с запятой);

Часто попадаются такие исходники? И что вы делаете, когда оффициальный компилятор/интерпретатор спокойно глотают такие сырцы? Просто если сырец невалиден, то, ИМХО, ни о каком анализе ну может быть и речи.

KvanTTT Mar 3 2016 at 23:37

Результатам статический анализа вообще нельзя доверять на все 100%. Для более серьезного анализа есть модули, заточенные под определенные языки и платформы. Ну и мелкие семантические и синтаксические ошибки почти не повлияют на результат анализа.

lightsource Mar 4 2016 at 13:00

Вы планируете делать анализ других языков? Например, для Ruby есть runtime и target для ANTLR 4.4. Однако в репозиторий последний коммит был сделан 9 месяцев назад.
По поводу runtime C++ в Github есть репозиторий. Вы имели в виду про него? Кстати, буквально 2 дня назад был задан вопрос по поддержке XCode.

KvanTTT Mar 4 2016 at 13:05

Так для анализа нужен не рантайм, а грамматика (ее в официальном репозитории вроде нет). У нас же все анализируется все на .NET. Но за ссылку на рантайм спасибо. Не знал, что такой существует. Надо будет поговорить с авторами о переносе в официальный репозиторий. С поддержкой C++, к сожалению, разработчики не торопятся.

KvanTTT Mar 4 2016 at 13:49

Имеется в виду, что на .NET анализируется все по части Pattern Matching, но не других модулей.

lightsource Mar 4 2016 at 14:05

Я имел в виду про общий случай, не привязываясь к .NET, поэтому написал про runtime. Да, в официальном репозитории грамматики языка программирования Ruby нет. Грамматика Ruby для ANTLR 4 есть здесь

UFO just landed and posted this here

lightsource Mar 4 2016 at 14:12

Спасибо за объяснение.

KvanTTT Mar 9 2016 at 01:55

Например, для Ruby есть runtime и target для ANTLR 4.4

Теперь она в официальном репозитории =) https://github.com/antlr/grammars-v4/tree/master/ruby

Bick Mar 4 2016 at 15:24

У вас не было необходимости разработки инкрементального парсера на базе ANTLR? Каким образом это лучше всего было-бы сделать с вашей точки зрения?

KvanTTT Mar 4 2016 at 16:23

Необходимости не было, но тема интересная и полезная. Как говорилось в статье, ANTLR 4 основан на динамическом алгоритме ALL, в котором кэшируются результаты обхода всех узлов. При первом парсинге файла узлы кэшируются. При втором парсер будет учитывать закэшированные узлы. Таким образом, можно будет узнать, какие из них добавились/изменились/удалились. Но это в теории, и я точно не могу сказать насколько это работоспособно. На гитхабе также задавали вопрос про инкрементальный парсинг. Для улучшения производительности скорее всего потребуются оптимизации.

Вообще же парсинг с помощью ANTLR можно начинать не только с корневого узла (обычно compilationUnit), но и вообще с произвольного (например, methodDeclaration). При изменении тела метода можно будет вызывать только метод methodDeclaration для парсинга измененного фрагмента кода (в ANTLR для парсинга файла целиком одним правилом, необходимо добавлять токен EOF в конец. Его отсутствие позволяет парсить код без ошибок не обязательно до конца).

masai Mar 4 2016 at 21:27

В естественном языке существуют неоднозначно трактуемые фразы (типа «казнить нельзя помиловать»).

Эту фразу часто приводят в качестве примера неоднозначности, но тут неоднозначность из-за того, что фраза грамматические некорректна. Мне больше нравится другой классический пример: «Эти типы стали есть у нас в цеху».

KvanTTT Mar 5 2016 at 00:10

Спасибо за замечание. Заменил пример в статье на ваш.

dmitry_pavlov Mar 8 2016 at 12:37

В копилку ссылок к статье — любопытный проект Irony

Irony is a development kit for implementing languages on .NET platform. Unlike most existing yacc/lex-style solutions Irony does not employ any scanner or parser code generation from grammar specifications written in a specialized meta-language. In Irony the target language grammar is coded directly in c# using operator overloading to express grammar constructs. Irony's scanner and parser modules use the grammar encoded as c# class to control the parsing process.

KvanTTT Mar 9 2016 at 01:52

Я все же считаю, что грамматика должна описываться независимо от целевого языка. Проверка синтаксиса и семантики грамматики в реальном времени это, конечно, плюс. Но и для ANTLR существует мощный плагин для IntelliJ IDEA с подсветкой и проверками. Под .NET также существует интересная разработка на Nemerle от разработчиков JetBrains: Nitra. Она, правда, тоже больше не развивается, как и Irony.

dmitry_pavlov Mar 9 2016 at 03:12

Не соглашусь. Все-таки в конечном итоге мы создаем лексер и парсер для использования в своем коде, то есть нужны модули, которые можно подключить и использовать. Тот же ANTLR с граматики генерирует лексер и парсер, скажем, в дотнет, но там такой кромешный ужас в этом коде, что это вполне ощутимо влияет на скорость работы результирующих лексеров и парсеров. В случае подхода примененного в Irony — конструирование граматики в "родном" стэке дает простоту разработки граматики, а также, полагаю, лучшую скорость работы. Хотя, конечно, испытаний как в статье я не проводил и утверждать этого не стану. Но даже без выигрыша по скорости, работа с граматикой не требует выходить из области знаний и инструментария своего стэка. А это при разработке уже очень существенный плюс.

KvanTTT Apr 13 2016 at 15:20

Сгенерированный код, конечно, не самый приятный, но и не кромешный ужас: отлаживать можно (хотя я в него практически не смотрю: для анализа пользуюсь другими средствами). Размер кода также зависит от грамматики (грамматику тоже можно оптимизировать). Ну и да — утверждение про лучшую скорость работы (и на сколько лучшую?) хорошо бы подтвердить фактами. Сгенерированный код статический, а значит может неплохо оптимизироваться компилятором.

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

Все равно нужно иметь представление о грамматиках, токенах, терминалах, AST и т.д.

KvanTTT Apr 13 2016 at 15:21

Под .NET, кстати, есть еще один интересный генератор парсеров LLLPG, но я подробно не изучал его. Авто пишет, что занялся этим проектом после того, как столкнулся с непреодолимым багом в C# рантайме ANTLR 3. В сравнении с ANTLR, автор приводит следующие преимущества:

минимальный размер рантайма. Сгенерированный код парсера похож на написанный вручную код;
скорость кода приоритетней понятности. Автор используется конструкции goto и switch для максимизации производительности.

Однако и ANTLR с 3 версии шагнул далеко вперед. Так что не знаю, насколько актуальны эти пункты.

KvanTTT Mar 9 2016 at 14:10

Здесь должен поправить себя: Nitra не заброшена, а отправлена на "вольные хлеба", код выложен в Open Source. Сейчас над ней ведется активная разработка парнями из RSDN.