さて、Kuin Advent Calender 2018もあと４日で終了となってしまうので、きりのいいところで終わらせてあげなければなりません。そこで、パーサについて少し勉強してみたいと思います。パーサとは何か？それはやってみれば分かります。
今回のお題
KuinのCUIライブラリに数式を入力するとその答えを返すプログラムを作ります。
字句解析
まず、与えられた数式（文字列）をトークン(token)と呼ばれる単位に分解します。トークンは以下のいずれかです。
- 整数：0から9からなる文字列
- 小数：２つの0から9からなる文字列をドット(
.)でつないだもの - 加算記号(
+) - 減算記号(
-) - 乗算記号(
*) - 除算記号(
/) - 左括弧(
() - 右括弧(
)) - 空白(
上記以外の文字列を入力するとエラーになるものとします。これは、正規表現を使うとすっきり表現することができます。
; 字句解析ルーチン(エラーならばnull)
func lex(str: []char): list<[]char>
var rg: regex@Regex
|:: regex@makeRegex("([0-9]+\\.[0-9]+|[0-9]+|[\\+\\-\\*\\/\\(\\) ])(.*)")
var s: []char :: str
var res: list<[]char> :: #list<[]char>
var match: [][]char
while(^s <> 0)
do match :: rg.match(s)
if(match =& null)
ret null
end if
do res.add(match[1])
do s :: match[2]
end while
ret res
end func
func main()
var tokens: list<[]char> :: @lex(cui@input())
if(tokens =& null)
do cui@print("エラー\n")
else
do tokens.head()
while(!tokens.term())
do cui@print(tokens.get() ~ "\n")
do tokens.next()
end while
end if
end func
実行結果はこのような感じです。
正規言語の復習
今回のコードではKuinの正規表現ライブラリが使われています。Kuinの正規表現ライブラリはboostというC++言語のライブラリを使っています。
正規言語は有限オートマトンで認識可能な言語のことで、正規言語の和集合演算、連結演算、スター演算も正規言語になるのでした。正規表現はオートマトン理論の正規言語がもとになっています。Unix由来のもので、その派生であるLinuxのgrepコマンドでも正規表現を使うことができるのでした。
もともとの正規表現でパターンの完全一致を行うにはアンカー(^と$)が必要なのでした。これはオートマトンの正規言語とは異なる点です。Kuinの正規表現ではアンカーを使わなくとも完全一致を行うようになっています。
正規表現は、ほとんどのプログラミング言語で実装されていますが、それぞれ、そのルールが少しずつ違っています。したがって、正規表現で分からないことがある場合には、一般的な正規表現ではどのように記述するのかということと、その言語ではどのように記述するのかということの２つを調べる必要があります。
Kuinの正規表現の場合、ドキュメントには「正規表現の書式は、Perl互換です。」と書いてありますがKuinとPerlではアンカーを打つかどうか(^, $を書くことを「アンカーを打つ」と言います)が違うため、何も知らない人がこのライブラリをさわると100%逃げ出します。
それではどうすればいいのでしょうか。正規表現の解説が分かりやすい記事を何個か読んで、Perl, Ruby, JavaScript, PHPなどの正規表現がメジャーに使われている言語で練習したうえで望むのがベターと言えるでしょう。
なんで正規表現についてこんなにネガティブな言い方をしているかというと、正規表現というものが、とてもコード効率がよいためにバグを作りこみやすいからです。「わたしはくいなちゃん」と「わたしがくいなちゃん」は、とても似ている日本語ですがとても違った意味を持っているでしょう。正規表現もそうなのです。
だからこのシリーズでは正規表現について完全に理解してもらうことをあきらめて、正規表現については最低限の説明にとどめることといたします。なにとぞご容赦のほどを。
字句解析ルーチンの解説
さて、字句解析ルーチンでは文字列からトークンを１つずつ切り出しています。それは、文字列に対して、"(pattern)(.*)"という正規表現で繰り返しマッチングしているからです。.*という正規表現は、どんな文字列にもマッチします。だからpatternのほうを正しく書いてやればトークンを１つずつ切り出していくことができるのです。
正規表現では., +, -, *, /, (, )といった文字はすべて特別な意味を持ちます。なので\を使ってエスケープする必要があるのですが、Kuinの文字列も\でエスケープを行うので\\でエスケープする必要があります。
[0-9]といった記述は文字クラスを表します。例えば[abc]と書いた場合は「aまたはbまたはc」という意味で、[くいなちゃん]と書いた場合は「くまたはいまたはなまたはちまたはゃまたはん」という意味です。文字クラスの中で使われるハイフン(-)にはさらに特別な意味があって、[0-9]と書くと「0から9までの文字」で、[a-z]と書くと「aからzまでの文字」という意味になります。ハイフンを使った表現は半角のアルファベットと数字でよく使います。
|は正規言語の和集合演算に似た演算子で、pattern1|pattern2はpattern1またはpattern2にマッチします。文字クラスに似ていますが、文字クラスが文字の集合を表現するのに対し、|はパターンどうしをかけ合わせます。
*は正規言語のスター演算に似た演算子で、pattern*はpatternの０個以上の繰り返しにマッチします。+は*に似ています。pattern+は１個以上の繰り返しにマッチします。
正規表現における(と)は、正規表現の演算子の優先順位を入れ替えるという意味があります。また、(と)に囲まれたパターンはグループと呼ばれます。パターンがマッチした場合、regex@matchメソッドの返り値の要素として、グループの文字列が与えられます。字句解析ルーチンはパターンマッチのグループの仕組みを使ってトークンを取り出しています。
Kuinのリスト
パーサのプログラムにおいては、可変長リストの構造を多用します。Kuinではlistがそれに該当します。listを使ったことがない人は以下のドキュメントでlistについて学んでおきましょう。
空白を削除する
字句解析ルーチンの中で空白を削除しておきます。通常はループの記述を複雑化することで行いますが、プログラムが複雑化すると分かりづらくなるので、わざとループの外にループを記述してやります。
; 字句解析ルーチン(エラーならばnull)
func lex(str: []char): list<[]char>
var rg: regex@Regex
|:: regex@makeRegex("([0-9]+\\.[0-9]+|[0-9]+|[\\+\\-\\*\\/\\(\\) ])(.*)")
var s: []char :: str
var res: list<[]char> :: #list<[]char>
var match: [][]char
; 文字列の終端に来るまでトークンのマッチを行う
while(^s <> 0)
do match :: rg.match(s)
if(match =& null)
ret null
end if
do res.add(match[1])
do s :: match[2]
end while
; トークンのリストから空白を削除する
do res.head()
while(!res.term())
if(res.get() = " ")
do res.del()
else
do res.next()
end if
end while
ret res
end func
func main()
var tokens: list<[]char> :: @lex(cui@input())
if(tokens =& null)
do cui@print("エラー\n")
else
do tokens.head()
while(!tokens.term())
do cui@print(tokens.get() ~ "\n")
do tokens.next()
end while
end if
end func
実行すると、空白が無くなっていることが分かります。
文脈自由文法
たいていのプログラミング言語の文法は文脈自由文法というものでできています。この電卓プログラムの文法は文脈自由文法の最も簡単な例ですが、このようなものです。
- 式は項、-項、式+項、式-項のいずれかである。
- 項は因子、項*因子、項/因子のいずれかである。
- 因子は(式)か数値のいずれかである。
- 言語全体は式である。
式、項、因子は英語でexpression, term, factorです。なので、上記のルールはバッカス・ナウア記法(BNF)で次のように記述できます。
<exp> ::= [ "-" ] <term>
| <exp> ( "+" | "-" ) <term>
<term> ::= <factor>
| <term> ( "*" | "/" ) <factor>
<factor> ::= "(" <exp> ")"
| <number>
この規則は左再帰といって少し扱いづらいので右再帰の規則に書き換えます。
<exp> ::= [ "-" ] <p-exp>
<p-exp> ::= <term>
| <term> ( "+" | "-" ) <p-exp>
<term> ::= <factor>
| <factor> ( "*" | "/" ) <term>
<factor> ::= "(" <exp> ")"
| <number>
再帰関数
文脈自由文法は有限オートマトンにスタックを追加したプッシュダウン・オートマトン(pushdown automaton)で認識することができます。ソースコードで文脈自由文法を実現する場合、関数呼び出しを再帰的に行う方法がおすすめです。関数はその変数をスタックとして保持するためです。
再帰関数は探索アルゴリズムでよく使われます。トークンから抽象構文木を組みたければ、ありうる組み合わせを全て試してしまえばいいのです。ちなみにトークンから抽象構文木を作ることを構文解析、または単にパース(parse)と言います。
ソースコード
ソースコードが300行近くなったので、リンクで示しておきます。以下にパーサの説明を書いていきます。
実行結果
実行結果は以下のようになります。例えばπを求める級数(ライプニッツの公式)を10項目まで足し合わせてみましょう。
JavaScriptで検算した結果も載せておきます。
数式を入力すると、まず抽象構文木の内容をダンプします。次に計算結果を出力します。入力した数式を正しく計算していることが分かるかと思います。
抽象構文木
「抽象構文木のクラス」とコメントが書いてある所にクラスがたくさん書いてあります。これは、BNFの各行に対応します。
<exp> ::= [ "-" ] <p-exp> ; Expクラス
<p-exp> ; Pexpクラス
::= <term> ; AtomicPexpクラス
| <term> ( "+" | "-" ) <p-exp> ; ComplexPexpクラス
<term> ; Termクラス
::= <factor> ; AtomicTermクラス
| <factor> ( "*" | "/" ) <term> ; ComplexTermクラス
<factor> ; Factorクラス
::= "(" <exp> ")" ; ComplexFactorクラス
| <number> ; AtomicFactorクラス
BNFの左辺に対応するクラス(例えばPexp)と右辺に対応するクラス(例えばAtomicPexp, ComplexPexp)を両方定義しているのは、子クラスが親クラスの変数に代入することができるという性質を使うためです。AtomicPexpとComplexPexpは違うものですが、Pexpに代入することで同じように扱うことができるようになります。
AstNodeクラスは、toStringメソッドのインターフェースを共有させるためのものです。このことによりtoStringメソッドはif文の嵐になることなく簡潔に実装させることができました。
パースする関数(make～関数)
「再帰関数」というコメントに続く、makeExp, makePexp, makeTerm, makeFactor関数がトークンの配列を抽象構文木にパースします。各関数はtokens, istart, iendを引数に取ります。字句解析においては文字列オブジェクトを繰り返し使い捨てるような実装を行っていますが、パーサではトークンの配列を使い捨てるような実装にはなっていません。字句解析の結果として受け取ったトークンの配列の構造自体を変える代わりに、トークンの範囲の開始位置と終端位置(ただし半開区間と呼ばれるもので、実際には終端位置+1の値です)を指定しています。
パースする関数は成功したときに抽象構文木のオブジェクトを返し、失敗するとnullを返します。
makeExp, makePexp関数では、トークン範囲の検査を行う前にクラスオブジェクトを作成していますがこれは横着なやり方で、速度低下の要因になります。BNF上でp-expとtermが同様の構造をしているのでmakePexpとmakeTermは同様の動作をします。ただしmakeTermはトークン範囲の検査を行ってからクラスオブジェクトを生成しています。これが本来のやり方です。ただしソースコードは多少長くなります。C++やDはクラスインスタンスをスタックとヒープの両方に配置することができるので多少書きやすくなると思います。
これらの関数は分かりづらいですが再帰関数です。相互再帰する構造になっています。再帰関数は、複雑なアルゴリズムを簡便に書くことができるというメリットがありますが、スタックを大量に消費するというデメリットもあります。スタックはヒープに比べてサイズが小さく設定されています。そもそもスタックは大量に消費するためのものではないためです。とはいえコンパイラの用途では再帰関数を使って問題ないです。再帰回数が多すぎるソースコードというのは人間が読むことができないためです。
計算をする関数(calc～関数)
calcExp, calcTerm, calcFactor関数は抽象構文木を与えて計算をさせるための関数で、これらも再帰関数です。本当はAstNodeクラスにcalcメソッドを追加したかったのですが、減算と除算が左結合であるためできませんでした。例えば、10-2-4という式を抽象構文木は(10 - (2 - (4))というようにパースしますが、10 - (2 - 4) = 8で、4ではないためです。これを改善するためには、トークンの配列を先頭からではなく末尾から解釈させてやればよかったのですが、そのコードを最初にお見せするのはどうかと思うので今回は先頭から解釈させています。今回のパーサアルゴリズムは素朴なものですが、一般的なパーサアルゴリズムであるLALR法ではより柔軟に対応できるみたいです。
toStringメソッドでは木の葉から根の方向にデータが流れていきますが、これらの関数では一部で木の根から葉の方向にデータを流しています。そのためにダウンキャストという操作を行っています。Kuinは強い静的型付け言語なのでダウンキャストが大量に発生するとソースコードが読みづらくなります。