RDBMSを作る - 構文解析
今、やりたことが多すぎて複数TrsNiumに分裂したいTrsNiumです。
タイトル通りに現在RDMBSを作成しています。(erlangで。) なぜerlangでRDMBSなのか?ですが、以下の理由があります。
erlang
- 関数型言語をまた触りたくなった
- 以前分散システムについて勉強したが、erlangのOTPを使えばいい感じに実践編に持ち込めそうだと思った。
- 一貫性プログラミングに適している
- 構文解析と字句解析がデフォルトで用意されている
RDBMS
などです。
さて理由はわかりましたが、RDBMSのことを知らなくては作れません。 そこで以下の本を選び、参考にしてみることにしました。
この本は解剖学と歌うだけあり、字句解析のことから、オプティマイザ、プランナ、トランザクションまで幅広く紹介しています。 ※理論を理解したい人は別途で、そのトピックに関する専門書や論文を読むと良さそう
字句解析・構文解析
erlangにはleexとyeccという字句解析と構文解析モジュールが用意されています。 これらを用いて構文解析をおこなっています。
流れは leexにsql文を流しトークンを取得し、yeccにトークンを流し構文解析をする感じです。 まだ作成途中で不完全ですが、このツイートのように徐々に構文を解析できるようになっています。
繋ぎ込みと字句解析を良しなにやれば良いか pic.twitter.com/nNIutQOMPB
— Trs (@TrsNium) June 1, 2019
作業はこのレポジトリの中で地道にやっていこうと思います。
3章: 線形化可能性
TAoMPで紹介されている一貫性は以下の3種類です。 - 静止一貫性 - 逐次一貫性 - 線形化可能性
何となく線形化可能性だけ書きます
線形化可能性
線形化可能性ではオーバーラップしないメソッド呼び出しの順序では、それと対応する逐次履歴と同じである必要があります。呼び出しがオーバーラップする場合、それぞれの呼び出し順序は曖昧でよく、呼び出し順序は入れ替わっても良いです。オーバーラップしないときに、特定の順序または逆の順序で実行した場合と一致することを示します。図にすると下記のように表すことができます。
上の図ではthread1がObjに3を書く呼び出し、次にthread2がObjに-7を書き込んでいます。しかし、呼び出しのオーバーラップが発生する為に、thread2の読み込みは3になっています。これを線形化ポイントを付け図に示すと下記のようになります。
(※ 線形化ポイントとは、メソッドの呼び出し結果が他のメソッド呼び出しから参照できるようになるステップ)