Балуюсь, хочу сделать транслятор из 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}
]
(То, что это не единственный вариант удовлетворяющего условиям результата — понятно.)
Положение в списке предварительных деклараций не очень важно — в худшем случае, можно их вытащить наверх, хотя лично мне хочется размещать их не раньше самого необходимого (т.е. перед первой отсылкой).
Если бы циклов не было — все было бы, вроде как, понятно — про топологическую сортировку я нашел и почитал. Но как справиться с циклами — честно говоря, пока не соображу.
Ответ
Поскольку БНФ оперирует контекстно-свободными грамматиками, то самое простое - это использовать соответствующий раздел теории синтаксического анализа.
Самое неприятное, что может быть в произвольно взятой КС-грамматике G - это левая рекурсия, которая, нестрого говоря, делает грамматику G недетерминированной.
При этом шаги алгоритма избавления от левой рекурсии включают в себя избавление от циклов. Поскольку вы, судя по всему, пытаетесь достичь детерминированности соответствующей грамматики, то лично я рекомендовал бы сразу же заимплементировать алгоритм избавления от левой рекурсии.
Простое описание подхода избавления от левой рекурсии можно найти здесь, более же обзорная публикация по разным алгоритмам избавления от левой рекурсии расположена тут.
Если вы действительно знаете, что делаете и хотите только избавиться от циклов, то воспользуйтесь только шагами (1) и (2) из публикации Eliminating left-recursion: three steps
Из дополнительных референсов могу порекомендовать пост Эрика Липперта по поводу CFG и циклов в них вообще, а также набор хороших презентаций по теории формальных языков.
Комментариев нет:
Отправить комментарий