Rethink Grammar::generate logic about bnf HOT 5 CLOSED

What would you think of

1. reducing a grammar to a directed graph structure
2. where nodes are rule names and edges go from a rule to its dependents. For example: <A> ::= <B> | <C> <D> would result in a graph

(A) --> (B)
   \
    `-> (C) --> (D)

3. then check for cycles that can't be reached from terminals

?

I think that'd be doable using petgraph.

from bnf.

Ah petgraph looks cool! I like your proposed solution too, I'd have to poke at it a bit if I were implementing, but fwiw I'd totally support a solution like this in a PR.

from bnf.

Has this question been resolved already? If not I think I have proposal for it (I was skeptical that the proposed solution would work).

This problem can be reduced to solving the emptiness problem for CFLs. I have added a solution strategy below:

1. We mark every non-terminal that produces a sequences of terminals
2. We then recursively mark every non-terminal that can produce a sequence of marked elements
3. We check whether the initial non-terminal is marked

I don't think this needs any special libraries but just a poly-space recursion on the existing grammar would work well.

What do you guys think?

from bnf.

@notDhruv this hasn't been solved yet 😄 I think your approach sounds great, seems like it'd definitely give us a mechanism for avoiding the infinite loop issues, and I can imagine that if we have some known-to-be-finite paths to terminals to traverse, we could work in the min - max generated sentence length too.

from bnf.

addressed by #127 thanks for everyone's suggestions!

from bnf.