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

Часто попадаются такие исходники? И что вы делаете, когда оффициальный компилятор/интерпретатор спокойно глотают такие сырцы? Просто если сырец невалиден, то, ИМХО, ни о каком анализе ну может быть и речи.
Результатам статический анализа вообще нельзя доверять на все 100%. Для более серьезного анализа есть модули, заточенные под определенные языки и платформы. Ну и мелкие семантические и синтаксические ошибки почти не повлияют на результат анализа.
Вы планируете делать анализ других языков? Например, для Ruby есть runtime и target для ANTLR 4.4. Однако в репозиторий последний коммит был сделан 9 месяцев назад.
По поводу runtime C++ в Github есть репозиторий. Вы имели в виду про него? Кстати, буквально 2 дня назад был задан вопрос по поддержке XCode.
Так для анализа нужен не рантайм, а грамматика (ее в официальном репозитории вроде нет). У нас же все анализируется все на .NET. Но за ссылку на рантайм спасибо. Не знал, что такой существует. Надо будет поговорить с авторами о переносе в официальный репозиторий. С поддержкой C++, к сожалению, разработчики не торопятся.
Имеется в виду, что на .NET анализируется все по части Pattern Matching, но не других модулей.
Я имел в виду про общий случай, не привязываясь к .NET, поэтому написал про runtime. Да, в официальном репозитории грамматики языка программирования Ruby нет. Грамматика Ruby для ANTLR 4 есть здесь
UFO landed and left these words here
У вас не было необходимости разработки инкрементального парсера на базе ANTLR? Каким образом это лучше всего было-бы сделать с вашей точки зрения?
Необходимости не было, но тема интересная и полезная. Как говорилось в статье, ANTLR 4 основан на динамическом алгоритме ALL, в котором кэшируются результаты обхода всех узлов. При первом парсинге файла узлы кэшируются. При втором парсер будет учитывать закэшированные узлы. Таким образом, можно будет узнать, какие из них добавились/изменились/удалились. Но это в теории, и я точно не могу сказать насколько это работоспособно. На гитхабе также задавали вопрос про инкрементальный парсинг. Для улучшения производительности скорее всего потребуются оптимизации.

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

Эту фразу часто приводят в качестве примера неоднозначности, но тут неоднозначность из-за того, что фраза грамматические некорректна. Мне больше нравится другой классический пример: «Эти типы стали есть у нас в цеху».
В копилку ссылок к статье — любопытный проект 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.
Я все же считаю, что грамматика должна описываться независимо от целевого языка. Проверка синтаксиса и семантики грамматики в реальном времени это, конечно, плюс. Но и для ANTLR существует мощный плагин для IntelliJ IDEA с подсветкой и проверками. Под .NET также существует интересная разработка на Nemerle от разработчиков JetBrains: Nitra. Она, правда, тоже больше не развивается, как и Irony.
Не соглашусь. Все-таки в конечном итоге мы создаем лексер и парсер для использования в своем коде, то есть нужны модули, которые можно подключить и использовать. Тот же ANTLR с граматики генерирует лексер и парсер, скажем, в дотнет, но там такой кромешный ужас в этом коде, что это вполне ощутимо влияет на скорость работы результирующих лексеров и парсеров. В случае подхода примененного в Irony — конструирование граматики в "родном" стэке дает простоту разработки граматики, а также, полагаю, лучшую скорость работы. Хотя, конечно, испытаний как в статье я не проводил и утверждать этого не стану. Но даже без выигрыша по скорости, работа с граматикой не требует выходить из области знаний и инструментария своего стэка. А это при разработке уже очень существенный плюс.

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


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

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

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


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

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

Здесь должен поправить себя: Nitra не заброшена, а отправлена на "вольные хлеба", код выложен в Open Source. Сейчас над ней ведется активная разработка парнями из RSDN.
Only those users with full accounts are able to leave comments. Log in, please.

Information

Founded
2002
Location
Россия
Website
www.ptsecurity.com
Employees
501–1,000 employees
Registered

Habr blog