Комментарии 12
Но проблема в том, что нужно TDD, причем такое, что бы максимум за 15 секунд можно было получить хотя бы 100% покрытие всех вариантов грамматики (включая комбинации).
Это как понимать? Если 100% покрытие, то о комбинациях речи не идет, т.к. в этом случае количество вариантов растет экспоненциально. 100% — это покрытие всех правил и альтернатив?
А вы не пробовали использовать метрику по покрытию грамматических правил и альтернатив (количество покрытых / количество всех)? По идее ее тоже можно использовать в тестах, она не должна убывать. То же самое и с лексером.
При разработке грамматики для C# смог получить именно проблему, что парсер не справлялся с вариантом isFlag? var1: var2, потому что он пытался парсить, используя знак? не как тернарный оператор. Antlr просто не хватало глубины поиска в правилах и он не мог поймать тернарку.
Может тогда antlr не стоит пользовать, а взять что-нибудь LR-ное, типа того же bison, на основе автомата со стеком, там такой проблемы не будет.
Да это пример. И на ANTLR все языки пробую больше для понимания пределов работы этого фреймворка. Мне нужно знать его ограничения, так как некоторые вещи на нем реализовывать не просто быстрее и легче, но и оптимальнее.
Сделать самописный рекурсивный парсер вообще не представляется никакой проблемой. Более того, можно почти один в один скопировать код из roslyn на джаву и получить нужный мне парсер. Но зачем, если я уже знаю как оно будет работать с точностью до второго знака после запятой? =)
Если потребуется оптимизировать работу того или иного парсера/лексера — это можно будет сделать уже отдельно потом, потому что внутренний поток данных уже будет стандартом и от реализации никак не изменится.
Для таких языков как С++ лексер просто необходимо запускать отдельно от парсера, что бы получать корректный вывод — иначе вы все макросы не раскроете.
А для раскрытия макросов разве достаточно одного лексера? Там же тоже есть всякие вложенные штуки типа #if #elif #endif и текст между ними, для чего неплохо бы использовать парсер.
А зачем вам парсер, если на уровне лексера вы можете встроить анализ всех этих конструкций? Более того, давайте посмотрим на то, как работает препроцессор С++, он вообще не знает в плане вычислений условий, что существует С++, все вычисления производится только согласно стандарту препроцессора. Это вообще отдельная грамматика.
По сути процесс разбора для С++ выглядит примерно так:
1 Токенизировать файл, получить шаблонный файл препроцессора, состоящего из конструкций #if #else #end, #define, #udef, etc… Причем директивы можно вполне обрабатывать прямо вклинившись в токенизатор. Если есть инклюд, который вы не обработали, то ничто не мешает рекурсивно вызывать разбор файла внутри разбора файла. Это нужно, что бы потом можно было модифицировать набор дефайнов согласно шаблону. Т.е. вы проходите по хидеру, игнорируете все, что не относится к препроцессору, берете только дефайны, актуальные для текущего момента. При этом разбор заголовка ничем не будет отличаться от других файлов.
2 Преобразование потока токенов согласно шаблонным файлам, раскрыть макросы и управление препроцессором. В итоге если у вас были setup.h, setup.cpp, то на выходе будут те же самые файлы, только с раскрытыми макросами и удаленными полностью инструкциями препроцессора. Из setup.h в setup.cpp ничего не копируется и не вставляется.
3 Передать поток уже готовых токенов файла в парсер.
При таком подходе вам не надо все сливать в один файл (есть исключение для файлов inc, их токены надо именно что вставлять). Поэтому работать парсер будет на маленьком файле и ему не надо парсить каждый раз один и тот же набор деклараций из заголовков, потому что вы их проанализируете как отдельный файл.
И да, хочу еще раз отметить, что есть небольшая проблема с inc файлами, но обычно у них именно такое расширение, так что разрулить можно, хуже если умник какой-нибудь нарушает стандарты. Такой подход конечно же рискованный, но для SAST он вполне актуален. Экономит просто массу вычислительных ресурсов. Тем более что подать потом на парсер файлы в определенном порядке (а мы знаем все зависимости между файлами) труда вообще не составляет, не так ли?
При разработке грамматики для C# смог получить именно проблему, что парсер не справлялся с вариантом isFlag? var1: var2, потому что он пытался парсить, используя знак? не как тернарный оператор. Antlr просто не хватало глубины поиска в правилах и он не мог поймать тернарку.
Здесь не совсем понятно написано, насколько я помню из лички здесь натыкаемся на неоднозначность: выбор между тернарным выражением и декларацией:
var a = value is MyType? A: B -> sll fail
var a = value is MyType? 1: 2 -> sll ok
Но разве нельзя решить эту проблему используя семантические предикаты? Известно, что в случае декларации после объявления типа может следовать только идентификатор (не выражение как в случае с ternary), а после этого идентификатора — либо токен ; либо =.
A? a;
A? a = null;А может вообще переписать грамматику, чтобы в качестве expression в тернарном условии не принималась декларация, потому что в C# такой синтаксис недопустим:
obj is A? a ? true : false;
Идеальный SAST. Тестируем парсеры