Синтаксический анализ для «встроенных» языков Андрей Бреслав Соавторы: A. Annamaa, V. Vene (University of Tartu, Estonia) - презентация

1 Синтаксический анализ для «встроенных» языков Андрей Бреслав Соавторы: A. Annamaa, V. Vene (University of Tartu, Estonia)

2 Немного о предмете Наша Программа База данных SQL-Запросы Данные SELECT id, date, title FROM Orders WHERE (user_id=239) AND (completed=FALSE) ORDER BY date ASC id=7, date= ,title=fooid=11, date= ,title=barid=80, date= ,title=baz

3 Как работает «Наша программа» Наша Программа База данных SQL-Запросы Данные public PreparedStatement selectOrders( int userId, boolean completedOnly, boolean ascOrder) { String sql = "SELECT id, date, title," + "FROM Orders" + "WHERE (user_id=" + userId; if (completedOnly) sql += "AND (completed=FALSE)"; sql += "ORDER BY date"; sql += (ascOrder) ? "ASC" : "DESC"; return ConnectionProvider.conn.prepareStatement(sql); }

4 Кто заметил ошибки? public PreparedStatement selectOrders( int userId, boolean completedOnly, boolean ascOrder) { String sql = "SELECT id, date, title," + "FROM Orders" + "WHERE (user_id=" + userId; if (completedOnly) sql += "AND (completed=FALSE)"; sql += "ORDER BY date"; sql += (ascOrder) ? "ASC" : "DESC"; return ConnectionProvider.conn.prepareStatement(sql); } Наша Программа База данных SQL-Запросы Данные

5 Постановка задачи Статически обнаруживать синтаксические ошибки в SQL-запросах внутри Java-строк и сообщать о них пользователю, не запуская его программу

6 Что кроме SQL? URI: git+ssh://foo.bar.com:foo.git String.format(Foo %s, %d bar!, s, x);

7 Общая схема решения prepareStatement(sql) prepareCall(sql) executeQuery(sql) executeUpdate(sql) Какие строковые выражения нужно проверить? Задача алгоритмически неразрешима в общем случае Как представить результат? Множества бывают бесконечными Каковы возможные значения данного выражения? CF CF – неразрешима REG CF – неразрешима REG REG – разрешима но SQL – не регулярный Удовлетворяют ли эти значения требованиям синтаксиса встроенного языка?

8 Общая схема решения prepareStatement(sql) prepareCall(sql) executeQuery(sql) executeUpdate(sql) Какие строковые выражения нужно проверить? Аппроксимация: Построим регулярное множество, содержащее все возможные значения выражения Каковы возможные значения данного выражения? Аппроксимация: Найдем регулярный язык, содержащийся в SQL, и будем проверять включение вида REG REG – разрешимая задача Удовлетворяют ли эти значения требованиям синтаксиса встроенного языка?

a+ + => a b if => a | b Сокращен" title="Abstract Strings String sql = "SELECT id"; if (needNames) sql += ", name"; sql += "FROM People WHERE age = " + minAge; connection.prepareStatement(sql); "SELECT˽id" ",˽name"? "FROM˽People˽WHERE˽age˽=˽" minAge)? for => a+ + => a b if => a | b Сокращен" class="link_thumb"> 9 Abstract Strings String sql = "SELECT id"; if (needNames) sql += ", name"; sql += "FROM People WHERE age = " + minAge; connection.prepareStatement(sql); "SELECT˽id" ",˽name"? "FROM˽People˽WHERE˽age˽=˽" minAge)? for => a+ + => a b if => a | b Сокращение: AS? := (AS | "") a+ + => a b if => a | b Сокращен"> a+ + => a b if => a | b Сокращение: AS? := (AS | "")"> a+ + => a b if => a | b Сокращен" title="Abstract Strings String sql = "SELECT id"; if (needNames) sql += ", name"; sql += "FROM People WHERE age = " + minAge; connection.prepareStatement(sql); "SELECT˽id" ",˽name"? "FROM˽People˽WHERE˽age˽=˽" minAge)? for => a+ + => a b if => a | b Сокращен">

10 Время работы Проект Размер LOC # ВыраженийВремя (сек) Память всегоошибокобщееAStringsкэш Plazma Compiere

11 Abstract Parsing Управляющие таблицы не меняются (для данного языка) Измененяемое состояние: Стек состояний парсера Позиция считывающей головки Основная идея абстрактного разбора Для каждой позиции во входном автомате Вычислить множество всех возможных стеков состояний парсера Множество строк (REG) Abstract Parser Abstract Parser Сообщения об ошибках Bison Управляющие таблицы c snsn s0s0 Упр. таблицы Стек состояний Вход LR-Разбор ACTIONGOTO S A R

12 s1s1 s0s0 Алгоритм s2s2 s0s0 s0s0 a b c e d s4s4 s3s3 s5s5 e s3s3 s5s5 s1s1 s0s0 s4s4 s3s3 s3s3

13 Время работы

14 Поиск контрпримеров Пользователю нужно показать, какую именно неправильную строку может сформировать его программа Контрпример – путь в графе стеков, заканчивающийся ошибочным состоянием Обычно нас интересует самый короткий контрпример Как решать? s1s1 s0s0 s2s2 s0s0 s0s0 a b c e d s4s4 s3s3 s5s5 e s3s3 s5s5 s1s1 s0s0 s4s4 s3s3 s3s3 Контрпримеры: - a(bc)+e - ab(cb)+d

15 Технические требования Нужно сообщать об ошибках в процессе написания кода нужны инкрементальные алгоритмы Подход должен единообразно поддерживать разные встроенные языки Хотелось бы просто описывать синтаксис (контекстно- свободной) грамматикой Не хотелось бы создавать такие грамматики вручную. Лучше взять готовую, например, из стандарта языка. Грамматики, приводимые в стандартах, содержат множество неоднозначностей

16 Что я не рассказал Abstract GLR-Parsing Возможность работать с неоднозначными грамматиками Abstract Lexical Analysis Входной алфавит парсера на самом деле не Unicode, а алфавит лексем: ключевых слов, идентификаторов, констант... Как сконвертировать один автомат в другой? Как проверять отсутствие опечаток в идентификаторах Автоматические тесты [Открытый вопрос] Булевские грамматики Метод можно обобщить так, что для любого автоматного предиката можно Проверить его истинность на регулярном множестве строк Найти кратчайший контрпример

17 Темы дипломных работ 1.[М] Использование булевских грамматик и Abstract Parsing для обнаружения опечаток в идентификаторах 2.[М] Мспользование булевских грамматик для реализации автодополнения идентификаторов в SQL-запросах 3.[Б] Оптимизация регулярной абстракции: ограничивать глубину стека только там и так, где и как это необходимо 4.[Б] Оптимизация потребления памяти GLR Abstract Parsing – разработка и реализация эффективных структур данных для хранения множества множеств стеков