Редукция графа в задаче достижимости с контекстно-свободными ограничениями

В недавней статье Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification показано, что предварительная редукция графа может существенно ускорить решение задач достижимости с контекстно-свободными ограничениями, возникающих в статическом анализе кода. Предлагается попробовать выразить предложенные в работе трансформации в виде операций линейной алгебры, внедрить в разрабатываемый нами инструмент и оценить влияние на производительность.

Требования к студенту
  • Отличное знание языка программирования Python: алгоритмическое программирование, средства контроля качества кода, тестирования, разработки, отладки, управления зависимостями.
  • Отличное знание основ теории графов: базовые определения, обходы графов, алгоритмы поиска путей, построения транзитивного замыкания, матрица смежности графа.
  • Хорошее понимание основ теории формальных языков: конечные автоматы, регулярные выражения, пересечение конечных автоматов, контекстно-свободные языки и грамматики.
  • Понимание основ статического анализа кода: межпроцедурный/внутрипроцедурный анализы, граф потока данных, граф потока управления, анализ указателей.
Уровень

2 курс

Руководитель

Григорьев Семен Вячеславович

Консультант

Grigorev Semyon

Источник

Кафедра системного программирования СПбГУ