Разрешение зависимостей для орграфа с циклами

#графы #зависимости #dependencies #компиляция

Балуюсь, хочу сделать транслятор из BNF в код-грамматику для LEPL. Парсер написал,
код для отдельных правил генерируется, но дальше подзастрял с порядком правил.

Есть набор правил, ссылающихся друг на друга. Зависимости можно просто представить
в виде орграфа, в котором есть циклы:



Нужно разрешить зависимости относительно заданной вершины, получив список, в котором
следует записывать правила так, чтобы последующие правила уже «видели» все требуемые
им предыдущие. Если возникает цикл — нужно перед первым употреблением поместить «предварительную
декларацию.» Т.е., для примера графа выше, если, упрощая, считать, что вершины содержат
просто строки, получить что-то в духе:

>>> deps_dict = {
...    "A": {"B", "C"},
...    "B": {"D", "E"},
...    "C": {"A", "E"},
...    "E": {"E", "D"}
... }
>>> resolve_deps(deps_dict, "A")
[
    "D"              # {}
    Predeclare("E"), # ref'd by {E, B}
    "E"              # {D, E}
    "B"              # {D, E}
    Predeclare("A"), # ref'd by {C}
    "C"              # {A, E}
    "A"              # {B, C}
]


(То, что это не единственный вариант удовлетворяющего условиям результата — понятно.)

Положение в списке предварительных деклараций не очень важно — в худшем случае, можно
их вытащить наверх, хотя лично мне хочется размещать их не раньше самого необходимого
(т.е. перед первой отсылкой).

Если бы циклов не было — все было бы, вроде как, понятно — про топологическую сортировку
я нашел и почитал. Но как справиться с циклами — честно говоря, пока не соображу.
    

Ответы

Ответ 1

Поскольку БНФ оперирует контекстно-свободными грамматиками, то самое простое - это
использовать соответствующий раздел теории синтаксического анализа.
Самое неприятное, что может быть в произвольно взятой КС-грамматике G - это левая
рекурсия, которая, нестрого говоря, делает грамматику G недетерминированной.



  
  При этом шаги алгоритма избавления от левой рекурсии включают в себя избавление
от циклов. Поскольку вы, судя по всему, пытаетесь достичь детерминированности соответствующей
грамматики, то лично я рекомендовал бы сразу же заимплементировать алгоритм избавления
от левой рекурсии.
  



Простое описание подхода избавления от левой рекурсии можно найти здесь, более же
обзорная публикация по разным алгоритмам избавления от левой рекурсии расположена тут.



  
  Если вы действительно знаете, что делаете и хотите только избавиться от циклов,
то воспользуйтесь только шагами (1) и (2) из публикации Eliminating left-recursion:
three steps.
  



Из дополнительных референсов могу порекомендовать пост Эрика Липперта по поводу CFG
и циклов в них вообще, а также набор хороших презентаций по теории формальных языков.