I am indulging, I want to make a translator from BNF to a grammar code for LEPL . The parser has written, the code for individual rules is generated, but further podzastryl with the order of the rules.
There is a set of rules that link to each other. Dependencies can be simply represented as a digraph, in which there are cycles:
It is necessary to resolve dependencies with respect to a given vertex by obtaining a list in which the rules should be written so that subsequent rules already “see” all the previous ones they require. If a cycle occurs, you need to place a “preliminary declaration before the first use.” That is, for the example of the graph above, if, simplifying, assume that the vertices contain just lines, get something in the spirit:
>>> 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} ] (The fact that this is not the only option of a satisfying result is understandable.)
The position in the list of preliminary declarations is not very important - in the worst case, you can pull them up, although I personally want to post them no sooner than the most necessary (that is, before the first reference).
If there were no cycles, everything would be, sort of, it is clear - I found and read about topological sorting. But how to cope with cycles - to be honest, for the time being I won’t think.
