Презентация - Кафедра Системного Программирования

Генератор абстрактных лексических анализаторов
Автор: Полубелова Марина Игоревна
Научный руководитель: магистр информационных технологий
С.В. Григорьев
Санкт-Петербургский государственный университет
Математико-Механический факультет
Кафедра системного программирования
22 мая 2014г.
Полубелова Марина (СПбГУ)
22 мая 2014г.
1 / 14
Область применения
Реинжиниринг программного обеспечения
I
Анализ и трансформация систем, код которых содержит
встроенные языки
Поддержка встроенных языков в IDE
I
I
I
Статический поиск ошибок
Подсветка синтаксиса
Рефакторинги
Полубелова Марина (СПбГУ)
22 мая 2014г.
2 / 14
Пример встроенного языка
Полубелова Марина (СПбГУ)
22 мая 2014г.
3 / 14
Пример встроенного языка
Полубелова Марина (СПбГУ)
22 мая 2014г.
4 / 14
Пример встроенного языка
0
"select x from y "
Полубелова Марина (СПбГУ)
1
"where a ++ b > 2"
2
22 мая 2014г.
4 / 14
Пример встроенного языка
0
0
"select x from y "
1
"select x from name"
Полубелова Марина (СПбГУ)
"where a ++ b > 2"
1
"1"
" 2"
2
2
22 мая 2014г.
4 / 14
Абстрактный лексический анализ
Является необходимым шагом при обработке встроенных языков.
Нужен для токенизации входного графа.
На вход анализатору подается граф, являющийся представлением
динамически формируемого выражения
На выходе получаем также граф, каждое ребро которого содержит
токен
Результирующий граф пригоден для дальнейшего синтаксического
анализа
Полубелова Марина (СПбГУ)
22 мая 2014г.
5 / 14
Пример
“Вход”
“Лексический анализ”
0
0
NUM: 1
1
1
+
1
2
+
NUM: 5 NUM: 3
3
5
2
3+45*6
3
*
+
4
6
NUM: 6 NUM: 4
7
Выражения: “1 + 3 + 4” и “1 + 5 * 6”
Полубелова Марина (СПбГУ)
22 мая 2014г.
6 / 14
Обзор существующих решений и аналогов
Java String Analyzer
I
I
строковое выражение аппроксимируют регулярной грамматикой
нет лексического анализа
PHP String Analyzer
I
I
строковое выражение аппроксимируют контексно-свободной
грамматикой
нет лексического анализа
Alvor
I
I
плагин к Eclipse для проверки встроенного в Java SQL
проводят абстрактный лексический анализ
статья Kyung-Goo Doh, Hyunha Kim, David A. Schmidt
I
I
статическая валидация динамически генерируемого HTML в PHP
проводят абстрактный синтаксический анализ
Курсовая работа Екатерины Вербицкой
Полубелова Марина (СПбГУ)
22 мая 2014г.
7 / 14
Постановка задачи
Доработать генератор абстрактных лексических анализаторов
I
I
I
Поддержка “рваных” токенов
Сохранять привязку частей динамически формируемого
выражения к исходному коду
Реализовать привязку лексических единиц внутри каждой части
Сравнить полученный инструмент с его аналогами
Полубелова Марина (СПбГУ)
22 мая 2014г.
8 / 14
Структура и принцип работы генератора
Полубелова Марина (СПбГУ)
22 мая 2014г.
9 / 14
Сохранение привязки к исходному коду
“Вход”
“Лексический анализ”
0
0
12
NUM: 123; br= [12; 12; 3]
1
1
3
2
+5 *6
3
*; br= [*6]
2
+; br= [+5]
3
NUM: 6; br= [*6] NUM: 5; br= [+5]
4
Выражения: “123 + 5” и “123 * 6”
Полубелова Марина (СПбГУ)
22 мая 2014г.
10 / 14
Пример работы
Полубелова Марина (СПбГУ)
22 мая 2014г.
11 / 14
Генерация тестов
Набор тестов параметризуется кратностью ребра (m = 2) и длиной
цепочкой (n = 3)
0
a
1
Полубелова Марина (СПбГУ)
x1
x2
2
x1
x2
3
x1
x2
4
b
5
22 мая 2014г.
12 / 14
Сравнение производительности
150
m=2_YC_Alvor
●
●
●●
●●
●
●●
●
●● ●●
●
●● ●●
●
●●
●●
●
100
●
● ●●●
●
●
●●●●●
time in ms
50
0
●
●
●●
●●●●●
●●
● ●●
●●●
●●●
●
●
●●
●●
● ●●
●
●
●●
●●
● ●●
●
●
●●
●
●●●
●●
●●
●●●
●
●●
●●
●●
●●
●●
●●
●●
0
●● ●●●
●
●
●●
●●
Alvor
YaccConstructor
20
40
60
80
100
file
Полубелова Марина (СПбГУ)
22 мая 2014г.
13 / 14
Результаты
Реализована структура, хранящая информацию о позиции токена
в исходном коде
Осуществлена корректная передача координат токена к ReSharper
Изучены аналоги лексических анализаторов
Реализован инструмент для тестирования лексеров
YaccConstructor и Alvor
Проведено сравнение лексера инструментов YaccConstructor и
Alvor на одинаковых входных данных
Результаты работы представлены на конференции “Технологии
Microsoft в теории и практике программирования”
Принята статья “Инструментальная поддержка встроенных языков
в интегрированных средах разрботки” на семинар по наукоёмкому
ПО.
Полубелова Марина (СПбГУ)
22 мая 2014г.
14 / 14