ふるつき

v(*'='*)v かに

BNFから文法に沿ったランダムな文字列を生成する試み

randexp.jsというライブラリがあって、これは与えられた正規表現に対して、その正規表現にマッチするような文字列を生成する。へーと思って実装を見てみたら素朴に作られていた。

あとで思い出して、じゃあBNFでやったらどうなのかというのを作ってみた。BNFというのは文法を定める言語のようなもので、Wikipedia曰く"文脈自由文法を定義するのに用いられるメタ言語" ということだった。文脈自由文法がどういう意味だったか全然憶えていないけど、この形式で言語の構文を書いておけば、lex/yaccみたいなのに簡単に落とし込めたり、愚直に再帰下降構文解析を書けば、文法に沿った言語をパースできるようになる。正規表現とは似て非なるもので、今回の目的だと正規表現が括弧のネストみたいなのをうまく表現できないのに比べて、BNFならわりと簡単に書ける、というような違いがある。

いまならPEGというもうちょっとBNFを便利に書いてもパーサは作れるよね、という感じの記法もあるけど、色々できるということは色々実装しないといけなくてややこしいということでもあるので、今回は素直にBNFを対象にした。

できたものがこちら

github.com

やることは簡単で、まずBNFをパースできるようにする。BNFは当然BNFを記述できるし、Wikipediaにそういう例があるから、それを見ながら再帰下降構文解析を書いて抽象構文木を作る。それができたら作った構文木を上から順に読み下しつつ、ルールに応じてランダムな文字を生成すればいい。ルールといっても、連接と選択と他のルールの参照くらいしかないから愚直にやっていい。

ここまで書いて、じゃあ適当な言語のBNFを拝借してなんか生成してみるか、と思ったけど愚直なBNFで定義された文法なんて都合よく転がっていなかった。EBNFならどうかとおもって反復とかもパースできるようにしたけど、結局共通のBNFで文法が定義なんてされていなくて丁寧な前処理が必要そうになって面倒になった。結局BNFで書かれたBNFの文法と、EBNFで書かれたEBNFの文法くらいしかサンプルがなくて悲しい感じになった。かろうじてbcは素直なBNFが提供されていて、かつトークンもそんなに複雑な感じではなかったので遊べる感じになっているが、トークンと構文は区別されているので、構文の間には適当に空白を入れないといけないが、トークンの間には入れることができず、それをBNF側でひとまとめに扱うのは無理なので結局 definex みたいなのが生成されてparsableではなくなってしまったりした。

それではランダムに生成したbcのプログラムでお別れです。これをJSとかTSで書くとか、wasm-friendlyな言語でwasmにコンパイルする前提で書くとかしていれば皆様にもお試しいただけたけど、今回はD言語で、しかも std をバリバリつかって書いてしまったのでブラウザに載せることはできませんでした。

while(h()!=sqrt(s(a(y)^-length(length(9.))))*--a[length((-B.D))])if(obase--g(B3B.D)-(sqrt(obase)^j--)>length(scale(w[ibase+=sqrt(scale--)]--)+sqrt(E1D.C)))for(-++i[7*sqrt(++d[--ibase+length(q())])]-k[length(++scale)]++;(--j[(ibase%=.5)]);sqrt(obase/=l()))break

;""
define w(f,a){
auto q[];
;

;;for(ibase++;c()-.0180>86F58B;-(-length(sqrt(0.3D2C31F+.4^-ibase/=B./A.01)))*B5.C6+sqrt(scale)%(v()-ibase))5.^--scale*h()}

今は再帰が深くなりすぎるとsegmentation faultする問題が知られていて、気が向いたらループに書き換えます