Instaparseでパーサジェネレータ

Instaparseの位置づけ

InstaparseはClojure言語による パーサジェネレータ - Wikipedia である

github.com

これのルール記述はBNFの拡張であるEBNFが使われている。

EBNFで構造化言語のルールを記述する

さっそくだが、「＜p＞sample＜/p＞」を読み取るBNFのルールを書いてみた。とは言え、HTMLの複雑なルールを最初から書くのは無理なので、とりあえずタグの開始と終了を読み取れるものを作る。

しかもこのルール記述、de.setf.xml/html-grammar.bnf at master · lisp/de.setf.xml · GitHub からコピーしてきたものである。

コードサンプル

(ns sample
  (:require [instaparse.core :as insta]))

;;
;; https://github.com/lisp/de.setf.xml/blob/master/bnf/html-grammar.bnf
;;
(def as-and-bs
  (insta/parser
   "HtmlDocument ::= Root
    Root         ::= ElementHtml
    ElementHtml  ::= HtmlTag | ( STag ( '/>' | ( '>' #'\\w'++ ETag ) ) )
    HtmlTag      ::= '<'  #'\\w'++ S* '>'
    STag         ::= '<'  #'\\w'++ S*
    ETag         ::= '</' #'\\w'++ S* '>'

    S ::= (' ' | '\t' | '\r\n' | '\n')+
"))

(def fool-tags "<p>sample</p>")

(defn fool-sample []
  (println (as-and-bs fool-tags)))

出力

• sampleのデータがきっちり構造化されて戻ってきた

lein test html-template.test
[:HtmlDocument [:Root [:ElementHtml [:STag < p] > s a m p l e [:ETag </ p >]]]]

後はこれに対して指定されたキーを使ってデータを取得したりすればいいのである。

AOJ - ALDS1_7_A, B, C (木構造) を解いてみた

勝手に解いてろとか言わないで…

ALDS1_7_A, B, Cは、木構造（根付き木、二分木）です

根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge
二分木 | アルゴリズムとデータ構造 | Aizu Online Judge
木の巡回 | アルゴリズムとデータ構造 | Aizu Online Judge
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

木構造を使うときの基本

まあ、木構造単体でプログラミングコンテストの問題が出されることはほとんど無さそうなのですが…*1

• とりあえず、構造体 or クラスで以下のような型を作る
• 木構造の１要素を１つのNodeというクラスで表現します。中には親要素のid、左と右の要素のidを持ちます。
• Rubyの場合はStructを使うと楽にそういうのが作れる、Generics無しにそれを配列型にできるし

Node = Struct.new(:parent, :left, :right)
nodes = Array.new(N) { Node.new }

ALDS1_7_A - 根付き木

１つの節（ノード）に複数の子がくっつく場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_children ( id, nodes )

その接点の直下の子ノードを求める

ALDS1_7_B - 二分木

１つの節（ノード）に２つの子しかつかない場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_height ( id, nodes )

その接点の高さを求める、深さと逆のため再帰的にノードを求める必要がある(Finding height in Binary Search Tree - Stack Overflow)

get_sibling ( id, nodes )

その接点と同じ階層にあるノードを求める、二分木の場合隣接するものはあるかないか２択になる

ALDS1_7_C - 木の巡回

木の巡回には３種類あるという話。

• 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
• 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
• 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。

自分の回答

用意した関数を紹介しておく

pre_parse ( root, nodes )

根節点、左部分木、右部分木の順で節点の番号を出力する

in_parse ( root, nodes )

左部分木、根節点、右部分木の順で節点の番号を出力する

post_parse ( root, nodes )

左部分木、右部分木、根節点の順で節点の番号を出力する

使用例？

単純な木構造って、実務でも競プロでも使うことが稀な気がする。すごい単純なデータが問題で、なおかつ階層がキーになる場合に使えばいいのかな？いい問題があれば追記します。

追記：　木構造の問題です

A Rational Sequence 2 – Kattis, Kattis

*1:木構造よりも、それの発展系のグラフアルゴリズムの出題が多そう

アルゴリズム学びフローを作成してみる

AOJの本

この本を買ってみた。プログラミングコンテスト攻略のためのアルゴリズムとデータ構造…

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

本の内容とレビュー

知識ゼロからはじめてもわかるように、アルゴリズムがだいたい順番に問題とともに紹介されている。昔paizaでA問題が解けないと悩んでいたが、それはこの本に載っているような、計算量を減らすためのアルゴリズムが組めていないことが原因であったと思う。

書籍の中ではAOJの例題が一緒に載っているので、文章を読んで理解した後に問題を実際に解いて腕試しすることができる。

見通しを立ててみる

書籍の中では、「このアルゴリズムを学んだら、次はこれに進めます」という情報が書いてある。ちょっとその情報をdraw.ioというサービスで絵にしてみた。（こういう風に、構造化していけば雑然とした概念がまとまるかなあという願望…）

図を書いていて思ったこと。

• 業務プログラミングでは、緑の線を出るか出ないかぐらいの知識しか使わない
• 自分は木構造とグラフと動的計画法の知識が足りない感じなので、そこをマスターしていく必要がある

高解像度版

プロコンで解いた問題を格納

今日は何か新しいことをやる気力が無くなったので、今まで解いた問題のコードを格納するリポジトリを作ってみた

github.com