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:

Dependency Graph Example

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.

1 answer 1

  • Since the БНФ operates with context-free grammars, the simplest thing is to use the corresponding section of the theory of syntactic analysis.

  • The most annoying thing that can be in an arbitrary КС-грамматике G is the left-handed recursion, which, loosely speaking, makes the grammar G non-deterministic.

  • In this case, the steps of the algorithm to get rid of left recursion include getting rid of cycles. Since you, apparently, are trying to achieve the determinism of the corresponding grammar, I personally would recommend immediately implementing the algorithm for getting rid of left recursion.
  • A simple description of the approach of getting rid of left recursion can be found here, but a review article on different algorithms of getting rid of left recursion is located here.
  • If you really know what you are doing and just want to get rid of the cycles, then use only steps (1) and (2) from the publication Eliminating left-recursion: three steps .
  • Hmmm ... And if without grammar conversions? LEPL itself is able to deal with cycles and LR. Now, if "does not take off" - then yes. Those. having a BNF: <equation> :: = <term> = <term> <term> :: = 1 | <addition> <addition> :: = <term> + <term> I, without touching the rules, for a start, I think just convert the syntax: TERM = Delayed () ADDITION = TERM & Literal ("+") & TERM TERM + = Literal ("1") | ADDITION EQUATION = TERM & Literal ("=") & TERM And, having made, EQUATION &= Eos(); EQUATION.config.auto_memoize() EQUATION &= Eos(); EQUATION.config.auto_memoize() work. Or is this approach too flawed and better not to do so? - drdaeman