Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

「構文解析ハンズオン 関西出張版」に行ってきました

lang-impl.connpass.com

に行ってきました。

水島さん (@kmizu) による、構文解析ハンズオンです。ここ最近はずっとこれに参加できることを心の支えにしてました。

ハンズオンの流れと思考の変遷

いくつかのトピックについて、水島さんの講義 -> ハンズオンの流れをテーマごとに繰り返して進んでいきました。 トピックは順を追って少しずつ複雑な概念を含むようになっていて、BNF が講義の中で示されるのでそれをもとにハンズオンの時間で皆が実装するという形式です。

数値の構文解析

一桁整数の構文解析

一文字を数値であるかどうか判定するというもの。これ自身はまあさすがに大丈夫でした。これ自身は。

余談

ch - '0' って昔は入門書にも載っていたようなテクニックじゃなかったかと思うんですけど、意外と反響があるようだったのでびっくり。(老害並感) まあ、さすがに今時はもう使うようなことはないでしょうし私もまず使いませんけど。

非負数値の構文解析

与えられた文字列が数値であるかどうかを判定するというもの。 これは、0 は許されるけど 012 などは許されないために最初に 0 (zero) であるかどうかを判定する、ということを気をつけていれば問題ありません。数値であるかどうか判定は前回のを流用できますし。

と、この時点では軽く考えていました。

余談

前(左)から順番に読み込む実装をしているにもかかわらず、一の位から順に計算しているかのように

result += ch *  Math.pow(10, i);

のような実装をしていて恥ずかしながらしばらくはまっていました。

それ以前に、Java には累乗の演算子がないことをすっかり忘れていました。私はもうだめだ・・・。

単純算術式の構文解析

かっこなし、演算子は一度だけ出てくる (1+1 のような) 算術式の解析です。

BNF はこちら

expression = addition | subtraction
           | multiplication | division | integer;
addition = integer '+' integer;
subtraction = integer '-' integer;
multiplication = integer '*' integer;
division = integer '/' integer;

ここでちょっとつまづきました。

演算子を判別する時点で failure だったときと右側の数値を取る時点で failure だったときどうするかという点がまずひとつ。 左側の数値は解析済みで返せる値なので、そこまで戻ってやらないといけない。

もう一つは、前段の非負数値の構文解析がすぐに流用できなかったこと。ひとつ目の問題と関連しますが、そこまではリストアすることを意識していなかったのでここに至って今までのソースがすんなり流用できなくなってしまいました。

そこでようやく、@kmizu さんの模範実装が try-catchthrow Exception を多用していたことの意味をあらためて意識しだしました。ただし動くものは作れましたが、この時点で理解はまだ正しくできていません。

算術式の構文解析

かっこや複数の演算子が登場する算術式の解析。

BNF はこちら

expression = additive;
additive = multitive 
           {'+' multitive | '-' multitive};
multitive = primary
           {'*' primary | '/' primary};
primary = '(' expression ')' | integer;

ここであらためて、@kmizu さんの講義の内容や模範実装の意味を咀嚼し直しました。 また、周りの人たちが「なんかわからんけど BNF 通り実装したら動いた」(意訳)と口々に言っていたので、私も邪念(?)を捨ててとにかく BNF を書き下すことに専念することにしました。あと、前述の、数値の解析が足を引っ張っているのをなんとか潰す。

そうしたら、なんかわからんけど BNF 通り実装したら動きました。その瞬間、私も「やったー」より「お?おおおお?」という感覚になりました。 また、何も考えずに実装した結果としてなぜそのような実装をするのかをようやく理解したというよくわからないことに。

JSON構文解析

書いている途中でタイムアップ。あとで続きやろう・・・。

特に印象に残ったこと

「なんかわからんけど BNF 通り実装したら動いた」

いろんな方が言っていた、これ。

よくよく考えたらなんかわからんなんてことなんかなくて、BNF という絶対的な仕様があるのだからそれを自然に書き下したらそりゃ動くんじゃないかなぁ、って後で思いました。普段そういうコーディングをすることがそうそうないからなんかよくわからんように思えるだけで。

日々の業務も BNF 的なもので書き下せれば簡単にプログラムで書き下せるようになるのかしらん?って、その BNF 的なものをどうやって作るんだよって話ですけど。

締め

とにかく楽しかったし勉強になりました。 プログラミング欲も満たされた、というかむしろ増大して飢えがひどくなったかもしれません。 懇親会も二次会もいろいろな話題で楽しめました。

関西出張して今回の機会を作っていただいた @kmizu さん、スポンサードしていただいたエフ・コード様、会場提供していただいたはてな様、本当にありがとうございました。 次の機会にも期待せざるを得ない!