search

alexandru-dinu / synx

Generate random strings given a BNF grammar.
MIT License
0 stars 0 forks source link

Fix generation for recursive grammars #9

Open alexandru-dinu opened 1 year ago

alexandru-dinu commented 1 year ago

Currently, for recursive grammars like:

<expr> ::= <num> | <expr> <op> <expr>
<num>  ::= r"[1-9][0-9]{0,5}"
<op>   ::= "+" | "-"

weird strings are produced due to how max_depth is handled:

---+7+--3288++861
alexandru-dinu commented 1 year ago

Potential idea: bias random.choice towards selecting terminals the deeper we are in the tree.

For e.g., for a rule like <s> ::= "foo" | <s> <s> and starting from a uniform distribution, we can increase the proba of selecting the first or-group ("foo") w.r.t. the depth.

alexandru-dinu commented 1 year ago

Added an initial fix: return None when reaching max depth and don't propagate None results upwards. However, the caveat is that we have to loop until we find a good match: https://github.com/alexandru-dinu/synx/blob/37ddb570e797068450277300f9fefd0cfb8603ba/synx/synx.py#L228-L230