Реализация абстрактного разрешения имён для модельного языка программирования

Работы по абстрагированию разрешения имён (того, что позволяет делать, например, переход к определению в средах разработки) ведутся активно. Основные результаты, такие как Scope Graphs: The Story so Far или Stack graphs: Name resolution at scale, предлагают использовать процедуры на специальных графах для разрешения имён, строя эти графы автоматически по дереву разбора кода. Часть предложенных процедур может быть переформулирована в виде задачи достижимости с контекстно-свободными ограничениями. Предлагается выявить ограничения на такую разновидность процедуры, реализовать её для модельного языка, учитывающего выявленные ограничения.

Требования к студенту
  • Отличные знания основ анализа языков программирования: синтаксический анализ, дерево разбора, графовые представления программ (граф потока управления, граф потока данных), разрешение имён (переход к определению символ от места его использования), вывод типов.
  • Отличные знания основ анализа графов: обходы графа (BFS, DFS), поиск путей (транзитивное замыкание, кратчайшие пути). Знание алгоритмов решения задачи поиска путей с ограничениями в виде контекстно-свободных языков будет плюсом.
  • Отличные знания основ теории формальных языков и алгоритмов синтаксического анализа: контекстно-свободные языки и грамматики, регулярные языки, конечные автоматы, рекурсивные автоматы.
  • Знание языка программирования Kotlin (или F#).
  • Навыки в реализации модельных языков программирования: дизайн синтаксиса и семантики, парсер, интерпретатор, проверка и вывод типов.
Уровень

3 курс, Бакалаврская ВКР, Магистерская ВКР

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

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

Консультант

Grigorev Semyon

Источник

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