JetBrains Research — наука, меняющая мир

Семинар по оптимальному алгоритму синтаксического анализа графов для языков Дика

Синтаксический анализ графов для языков Дика является фундаментальной задачей в статическом анализе. На вход дан граф с различными видами открывающихся и закрывающихся скобок на ребрах. Необходимо искать пути, метки на ребрах которых образуют правильную скобочную последовательность. На cеминаре будет рассмотрен следующий ряд результатов:

1) предложен алгоритм с наилучшей известной асимптотикой;

2) доказана оптимальность достигнутой асимптотики;

3) данная задача синтаксического анализа сведена к задаче умножения Булевых матриц.

Материалы к докладу: K.Chatterjee, B.Choudhary, A.Pavlogiannis. Optimal Dyck Reachability for Data-Dependence and Alias Analysis

Докладчик: Рустам Азимов

19.03.2018, 17:15.

Место: ауд. 3248, мат-мех. факультет СПбГУ, Старый Петергоф, Университетский пр-т, д. 28