I am trying to generate random sentences from a context-free grammar. During each step, the next non-terminal to be generated is determined according to some probabilistic criteria irrelevant to this question. Where I am stuck is, given a grammar and the partial sentence generated so far, how do I determine the set of non-terminals that can be generated at the next step according to the grammar?

Below is an example grammar in BNF and a partial generation.

<expr> ::= <term> "+" <expr> | <term>
<term> ::= <term> "*" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <const>
<const> ::= "0" | "1" | "2" | "3" | "4"

Supposed generated sequence so far: ( 1 +. In this case, we can easily see that the next token to be generated should come from the set {"(", "0", "1", "2", "3", "4"}.

Is there an algorithm to determine this set given a general grammar and a partial generation, or generate the sentence in a way that makes this set available at each step?

  • $\begingroup$ You can deduce that from the state of any parsing algorithm with the valid prefix property. $\endgroup$ – AProgrammer May 3 '17 at 6:57
  • $\begingroup$ When you say "deduce", do you mean a method such as trying to concatenate each non-terminal to the prefix to see if the resulting prefix leads to any errors or is there a more straightforward way of doing this? $\endgroup$ – user7954416 May 3 '17 at 7:50
  • $\begingroup$ At worst. But you can probably do better for every parsing algorithm, but the details will depend on the algorithm. $\endgroup$ – AProgrammer May 3 '17 at 7:56
  • $\begingroup$ Do you have any recommendations on the choice of algorithm? I have limited knowledge of them to make an informed choice on which one to pick for this specific case. For example, I assume a recursive descent parser is unsuitable for this task since the state is implicit. $\endgroup$ – user7954416 May 3 '17 at 8:03
  • $\begingroup$ Basing this on a table driven LL parsing algorithm should do the work and is probably more intuitive than the other possibilities. As you are generating instead of parsing, there is no need for the grammar to be LL. $\endgroup$ – AProgrammer May 3 '17 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.