Расширение поддержки шаблонных правил в решателе задачи достижимости с контекстно-свободными ограничениями

Задача достижимости с контекстно-свободными ограничениями возникает, например, при статическом анализе кода. Ограничения часто задаются грамматиками, в которых присутствуют однотипные правила. Использование знаний о таких правилах, как показал Илья Муравьёв в своей работе, позволяет существенно повысить производительность алгоритма, решающего задачу достижимости. Однако, Ильёй рассмотрены не все шаблоны правил, встречающиеся в прикладных задачах. В рамках работы предлагается рассмотреть ещё ряд шаблонов и поддержать их в решателе задачи достижимости.

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

2 курс, 3 курс

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

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

Консультант

Grigorev Semyon

Источник

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