Исследовательская группа

Лаборатория языковых инструментов

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

March 19

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

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

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

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

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

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