Ave Maria

今日もバイト行ってpkuといういつものroutine.

1人でプログラム書くときはいつも何かBGMを流してるんですが、、

今日は何故かAve Mariaが聞きたくなったので、

youtubeで見つけたAve Mariaをランダム再生してましたw



で、今日もプログラミングネタなんですがー、、

最近10分で書けるお手軽パーサーにはまってますw


えーと、パーサーと言うのはですね、、

「構文解析器」っていう物なのですが、例えば

I wish I were a bird, which can fly! とか言う文を見たときに、

I wish (I were a bird (, which can fly)))! とか言う感じに、

区切ってくれるような、そんな働き方をします。


別の例で言うと、1+2*3+3*5/2-3っていう数式を、

(((1+(2*3))+((3*5)/2))-3)っていう感じで

適切に括弧をつけてくれる、みたいなのも構文解析です。



んで、上の例を見て分かる通り、構文解析ってのはなかなかややこしいんです。

小学生とかだと1+2*3を9 ( = (1+2)*3 ) って言ってしまったり、

にゅうしとかでえいごをなんねんべんきょうしてもがくしゃたちがこのみそうな

ふくざつでこうぶんがいりみだれたようなえいぶんがかいしゃくできなかったり、

なかなか難しいわけですよ。この平仮名の文章も構文解析しにくいでしょ？w


人間が大変なものってのはプログラムするのも大変なわけで、

普通はパーサ(構文解析器)を作るってのはなかなか手のかかる作業なわけです。

でも上のリンクの、10分で書けるお手軽パーサーっていうサイトを参考にすると、

なんか驚くほど簡単にパーサが作れるようになってしまったのですw


詳細を述べるにはLL文法で左再帰があると不味い理由とか、

なんかそういうおもしろくないことを書かないといけないので省略しますが、、

まぁICPCとか挑戦してる人にはこのサイトはものすごく勉強になると思います。


で、"10分で書ける"お手軽パーサーって名前のサイトなので、

本当に10分で書けるのか試してみました。

使った問題はこちら。問題文の解説とかは省略でw


で、さすがに問題を読む時間を含めると間に合わないことが確定してしまうので、

まず問題を読んでから、時刻をチェックしてプログラムを書き始めてみました。

このとき22:10でした。で、まず文法を列挙して、パーサ部分をカリカリ書いて、

最後に入出力部分をカリカリカリカリ書いて、submitしてみたら一発Accept。

そしてこのときの時間が22:19。所要時間がきっかり10分(笑)


いやー、、正直10分で書けると思ってなかったから感動しました。

これでまた一つ知識がついたので世界大会に近づいたかなー、

なんて思ってみたりみなかったり。いや、思ってるんですがw


俺がここ数日pkuで解いた問題を探すと、

パーサの練習になるような問題がいくつかあるので、

興味のある人はやってみてくださいな。

そろそろお風呂入ったかな、、いてきますw