おはこんにちはこんばんは！れおなちゃんです。
traP Advent Calendar 2016も12日目になりましたね！いよいよ中盤に差し掛かってきたというところです。
今回は構文解析についての入門記事を書いていこうと思います。
どうしてこうなった
実は、「計算機代数」っていう分野にハマってしまったのがきっかけなのです。
「計算機代数」っていうのはどういうものかというと、計算機内で数学的な代数構造を再現しようという分野です。
普通の数値計算が、数学的構造を模したパイプラインに沿ってデータを流していくアプローチだと言うなら、計算機代数は、パイプラインそのものをデータとして見るというアプローチだといえます。
数値計算は非常に研究が進んでいる分野で、計算機上でも簡単に再現できる一方、パイプラインを流れ続けるデータは数値誤差を蓄積し続けるので、計算を進める上で常に「誤差」について意識を向けなければいけません。多くの数値シミュレーションでもこの誤差を如何に減らすかが問題になることが多いようです。誤差が発散してしまえば、シミュレーションとして意味を成しませんからね。
一方、計算機代数というのは比較的新しい分野で、数値計算に比べて出来ることは限られています。しかし、パイプラインそのものを計算機内に再現するというアプローチをとるおかげで、基本的に計算誤差は蓄積しません。そんな計算機代数という分野ですが、発展途上と言わざるを得ず、出来ることはまだまだ限られています。
そんな中でも、重要なツールとなるのが「多項式」です。そこでまず、「多項式」をどのように計算機上で表現するかということが問題になるのです。
でも、多項式のデータをどうやって計算機上で保持するかというのはとても悩ましい問題です。この方法をいちいちユーザー側に任せるのは面倒くさい。ユーザー側が内部実装を知る必要がないというのが理想です。
ですから、ユーザーお馴染みの多項式の文字列そのものをデータとして利用できたとしたら、とてもうれしいですよね？
そこで、ユーザー側としては多項式を文字列を入力するだけでいいようにして、あとの処理は内部実装にすべて任せてしまおう！っていうのが今回の構文解析の動機なのです。
さて、、とても長い前置きになってしまいました・・・。
というわけで構文解析、あなたも入門してみませんか？
構文解析とは？？
まずは構文解析が何なのかということについてきちんと説明しておきましょう。
計算機のなかに何か作りたいものがあって、それを「オレ語」で実行したい！そんなとき便利なのが構文解析です。
構文解析とは、ある文字列を読み込んで、何かしら意味付けが可能な構造体(構文)を得るプロセスのことを言うのです。
だから動機は何でもいいんです。構文解析の話と、上で話した「計算機代数」の話は直接関係ありません。なのでさっきの「計算機代数」の話はきれいさっぱり忘れてください！！
ということで、具体的には構文解析は次のように大きく3つのプロセスに分けることができます。
- 字句解析(Lexical analysis)
- 構文解析(Syntactic analysis)
- 意味解析(Semantic analysis)
1つ目の字句解析とは読み込んだ文字列を単語に分割してデータ構造に格納していくという操作のことです。これを行うことで後の構文解析が非常に楽になります。
2つめの構文解析とは、今回の大きな意味での構文解析と言葉が重複してしまっていますが、字句解析で得たトークン同士の関連付けを行い、構文を得ることです。これらは木構造を成すので、構文木ともいいます。
3つめの意味解析とは、構文解析によって得た構文木に従って、実際の意味を対応させることです。
これらの手順を踏めば、いわゆる「オレ語」が作れるようになります。私たちが使うプログラミング言語のコンパイラがやっていることも、本質的にはこの構文解析に他なりません。
以下では、先ほど上げた「多項式」を題材にして、実際に構文解析器を作ってみることにしましょう！
ちなみに言語はJavaを選びました。(本当はHaxe使いたかったんだけどすこしマイナーなのでやめました
字句解析
構文解析をするときの、まず1つ目の段階はこの字句解析です。文字列を読み込んで、それらをラベル付けされた単語として保持するのです。これらの単語のことをトークンと呼びます。そこでまずこのトークンを保持するTokenクラスを定義しましょう。
Tokenクラスの保持すべき情報は、そのトークンを示す文字列と種類、そしてトークンの順番を保つ情報です。
enum Type {
Number,
Symbol,
Identifier,
EOF,
Error;
}
public class Token {
private Type type;
public Type getType() {return this.type;}
private String data;
public String getData() {return this.data;}
public Token next;
public Token(Type type, String data) {
this.type = type; this.data = data;
}
public String toString() {
switch (this.type) {
case Number : return "[ number : "+data+" ]";
case Symbol : return "[ symbol : "+data+" ]";
case Identifier : return "[ identifier : "+data+" ]";
case EOF : return "[ EOF ]";
case Error : return "[ Error : "+data+" ]";
default : new NullPointerException().printStackTrace(); return null;
}
}
}
トークンの種類は直和型(enum)で表すのが便利です。上の例で言えば、すべてのトークンをNumber,Symbol,Identifier,EOF,Errorの何れかに分類することになります。各型の意味を説明していきましょう。
Numberはもちろん多項式の中で使われる数字を表すときに使う型です。
Symbolは多項式の中で扱われる演算子を表すときに使います。
Identifierは識別子、今回の場合は多項式の変数名を表すときに使うことにします。
そしてEOFというものを用意しました。これはEnd Of Fileの略で、読み込んだ文字列の終端を表すため、一番最後に追加する特殊な型です。これを用いることで、トークンをきちんと最後まで読み込んだのかどうかを判別できます。
Errorはこれらの何れにも該当しないトークンに与えられる型です。想定していないトークンが含まれるような文字列に対しては後々例外を吐かせるようにしましょう。
言語みたいなものを作りたいのなら、この他にも予約語を表す型としてKeywordみたいなものを用意するといいかもしれません。
変数nextには、次に来るトークンが入ります。これを数珠のように繋げていけば、各トークンそのものがインデックスの役割を果たしてくれるというわけです。代数的データ型(ADT)を使えたら、もう少し冗長にならずに書けるんですけど(小声)
お次はこのトークンを生成するTokenizerクラスを作りましょう。
と言いたいところですが、その前に、後々の便宜のために文字列を読み込むためのStringReaderクラスを用意します。このクラスはIteratorと似ていて、文字列の各文字を指し示してくれます。
public class StringReader {
private String data;
private int index;
public StringReader(String data) {
this.data = data;
this.index = 0;
}
public boolean hasNext() {
return index < data.length();
}
public String peek() {
if (!hasNext()) return null;
return data.charAt(index)+"";
}
public String next() {
if (!hasNext()) return null;
return data.charAt(index++)+"";
}
}
hasNext()はイテレータが指す要素に次があるかどうかをbool値で返します。
next()は現在指している文字を返したあとに、イテレータを前に進めます。
一方、peek()はイテレータを前には進めずに、現在指している文字を返します。
では、これを利用してTokenizerクラスを作ります。
public class Tokenizer {
private StringReader sr;
private Token tokens;
private Token lastToken;
public Tokenizer() {}
public Token tokenize(String src) {
this.sr = new StringReader(src);
this.tokens = null;
while (sr.hasNext()) readToken();
appendToken(new Token(Type.EOF, "EOF"));
return tokens;
}
private void readToken() {
/* ... */
}
private void appendToken(Token token) {
if(tokens!=null) {
lastToken = lastToken.next = token;
}
else lastToken = tokens = token;
}
}
appendToken()というメソッドでは常に、いま注目しているトークンlastTokenのケツに引数のtokenをくっつけていくという操作を行います。tokensという変数は、数珠の先頭を表すトークンです。
そして重要なのがtokenize()ですね。イテレータの代わりとなるStringReaderを用いて、while文を回しながら引数にとった文字列を先頭から解析していきます。そして文字列を読み込み終わったら、最後のトークンのお尻に終端子を挿し込んで終了です。while文の中のreadToken()の中身が気になるところですよね。
readToken()の中では地道に文字を読み込んでいきます。そしてある一定のところまで読み込んだら、それを区切ってトークンを生成し、lastTokenのケツにくっ付ける。これをwhile文で繰り返しています。
private void readToken() {
String s = sr.peek();
if (Pattern.compile("[\t\r\n ]").matcher(s).find()) sr.next();
else if (Pattern.compile("[0-9]").matcher(s).find()) {
String n = "";
do {
n += sr.next();
s = sr.peek();
} while (sr.hasNext() && Pattern.compile("[0-9]").matcher(s).find());
appendToken(new Token(Type.Number, n));
}
else if (Pattern.compile("[a-zA-Z_$]").matcher(s).find()) {
String n = "";
do {
n += sr.next();
s = sr.peek();
} while (sr.hasNext() && Pattern.compile("[a-zA-Z0-9_$]").matcher(s).find());
appendToken(new Token(Type.Identifier, n));
}
else {
if (Arrays.asList(Constants.SYMBOLS).contains(s)) appendToken(new Token(Type.Symbol, sr.next()));
else appendToken(new Token(Type.Error, sr.next()));
}
}
ここでは、文字のパターンマッチングに正規表現を使ってます。また、途中でConstants.SYMBOLSを使いましたが、これは記号を表す文字配列を、定数としてConstantsクラスにまとめたものです。具体的には
public static final String[] SYMBOLS = {
"+", "-", "*", "^", "(", ")"
};
としました。割り算/は色々めんどくさいので今回は省いています。
なお、記号長がすべて1なおかげでコードが簡単になっていることに注意しましょう。==とかを使いたいときはもうちょっと工夫しないといけません。
ポイントは、if文の順番です。空白がある場合は読み飛ばし、そうでなければ数字、識別子、記号の優先順位でトークン化していきます。まあこの部分は、コードをまじまじと読むより自分の頭で考えたほうが早いかもしれません。
字句解析はこれでおしまいです。ね、簡単でしょ？
実際に生成したトークン列を、toString()を使って出力してみましょう。
(5x10 ?? / x 0798 + 2* z_$ *-)^ 33 4)%
という式を入力して、生成されたトークン列を文字列で出力したら次のようになりました。
[ symbol : ( ] [ number : 5 ] [ identifier : x10 ] [ Error : ? ] [ Error : ? ] [ Error : / ] [ identifier : x ] [ number : 0798 ] [ symbol : + ] [ number : 2 ] [ symbol : * ] [ identifier : z_$ ] [ symbol : * ] [ symbol : - ] [ symbol : ) ] [ symbol : ^ ] [ number : 33 ] [ number : 4 ] [ symbol : ) ] [ Error : % ] [ EOF ]
うまくトークン化されてるみたいですね！きちんとエラー文字列も分けられていますし、最後にEOFも挿入されています。
こうして生成したトークンを並べたものとしてtokensをつくることができました！
今度はこのtokensをもとにして、構文木(syntax tree)を作っていきましょう。
構文解析
さてさて、次のステップは構文解析です。
構文解析をする(構文木を作る)プログラムのことをパーサと呼びます。つまり、パーサを作るのがここでの目標です。
では、パーサを作るにはどうしたらいいでしょうか？
実はこのパーサには色々な種類があります。ここでは、「再帰下降構文解析」という手法を用いることにします。
読んで字の如く再帰的な手法を用いるもので、実装は他のアルゴリズムに比べると非常に簡単なようです(実は再帰下降構文解析以外の手法を全く知らないので、あまり確実なことはいえません)。
この「再帰下降構文解析」を実装する前に、一つ便利な概念を導入しておきたいと思います。それは「EBNF(拡張バッカス-ナウア記法)」と呼ばれる、文法を表現するための記法です(あくまで道具として使いたいだけなので、あまり厳密な定義とかはしません、ご了承ください)。
概念といっても、大して難しい話をするわけではありません。例えば10進数の整数を表すEBNFは次のようになります。
<integer> := ( [ `+` | `-` ] <nat> | '0' );
<nat> := ( `1` | `2` | `3` | `4` | `5` | `6` | `7` | `8` | `9` ) {<digit>};
<digit> := ( `0` | `1` | `2` | `3` | `4` | `5` | `6` | `7` | `8` | `9` );
:=は左辺を右辺のように定義するという意味です。
|は「または」を意味し、<digit>でいえば0~9のいずれかの文字を表します。
{ }は0回以上の任意回数の繰り返しを意味する記号です。数の上1桁目は0を付けないのでこのように書くことになります。
[ ]は省略可能を表す記号です。整数を表すときは頭に符号を付けるか付けないかのいずれかで、付けるとすれば+か-のどちらかなので上のように書けますね。それと<nat>の定義だと0単体を表すことが出来ないので、| 0 )としました。
EBNFで出てくる規則はだいたいこれくらいです。この記法を用いると、簡単に「構文」を定義することが出来るようになります。
では実際に今回扱う多項式の構文をEBNFを用いて記述してみましょう！ずばり、多項式の構文は次のように書けます。
<expression> := <unary> { ( `+` | `-` | `*` ) <term> };
<unary> := [ ( `+` | `-` ) ] <term>;
<term> := ( <identifier> | <number> | `(` <expression> `)` ) [ `^` <number> ];
<identifier>と<number>は、これまでやってきた字句解析で得たIdentifierとNumberを型にもつトークンだとみなして、定義を省略しました。
すこし複雑になりましたが、一つずつ説明していきます。
<expression>は多項式のことです。多項式は文字や数字を演算子で繋いでいくことで構成できます。文字や数字をまとめたものが<term>になります。
<term>は<identifier>または<number>または括弧で囲まれた<expression>そのものを表します。さらにそれぞれの項は累乗も可能なので^ <number>を付けられるものとしました。
ここが注意しなければいけないのは、+と-は二項演算子としてだけでなく、符号を表す単項演算子としても使うことができるという点です。そこで構文の上でこれらを混同しないようにする必要があります。
多項式の頭にある<term>は、その前に二項演算子が来ないので、括弧を付けなくてもこの単項演算子と二項演算子を混同することはありません。なので、<expression>の先頭を特別に、<term>に符号を付けた<unary>と定義することで、<expression>の再帰構造を併せて、混同することなく、二項演算子と単項演算子を区別できるようにしました。
さて、こうして多項式の構文を書き下すことが出来ました！この構文は私たちが普段使っている多項式の書き方と同じです。
もちろん多項式を表すための構文はこれだけではありません。+、-と*とを分けて定義するのぜんぜんアリです。ここらへんは自分の好みで使いやすいものを定義してください。
この構文を用いて、実際に構文解析器、すなわちパーサーを作っていくのですが、実はそのプログラムはこの構文を「丸写し」すれば書けてしまうんです。これがEBNFを使って構文を表した最大のメリットです。
ではでは、準備が整ったので、実際に構文解析器を実装していきましょう。
まずは、構文木を表すためのデータ構造のクラスを作ります。
データ構造全体を表わすINodeというインターフェースを用意して、その下に構文木のクラスを書いていきます。
役割別に細かくノードを分けたので、それらを一つ一つ説明していくのも骨が折れます。なので詳細は省いてまとめて説明します。
作ったノードの継承関係がこちら
INode
┣━Tree
┗━ExpressionNode
┣━BinaryExpressionNode
┣━UnaryExpressionNode
┣━TermExpressionNode
┣━IdentifierExpressionNode
┗━NumberExpressionNode
Treeは構文木全体を収納するクラスです。
Expressionは式を表す抽象クラスで、式を逆ポーランド記法(RPN)に変換する抽象メソッドdumpRPN()が実装されています。
その下のノードはすべて上で書き下したEBNFに沿って分けたノードで、BinaryExpressionNodeやUnaryExpressionNode、TermExpressionNodeには演算子や被演算子が格納されており、IdentifierExpressionNodeやNumberExpressionNodeには、変数や数字をあらわす文字列が収納されます。
とまあ、数が多い割に中身はスカスカです。
public abstract class ExpressionNode implements INode {
public abstract String dumpRPN();
}
public class BinaryExpressionNode extends ExpressionNode {
public ExpressionNode lhs;
public String op;
public ExpressionNode rhs;
@Override
public String dumpRPN() {
return lhs.dumpRPN() + " " + rhs.dumpRPN() + " " + op;
}
}
public class IdentifierExpressionNode extends ExpressionNode {
public String identifier;
@Override
public String dumpRPN() {
return identifier;
}
}
字句解析のときに文字列の読み込みのためのStringReaderを作ったのと同様に、今回もトークンの読み込みのためのTokenReaderクラスを作りましょう。メソッドはStringReaderと同様、イテレータと似ていますが、型や文字列の検査をする機能が入っています。検査から漏れた場合は、容赦なくエラーを吐かせるようにしました。
public class TokenReader {
public Token tokens;
public TokenReader(Token tokens) {
this.tokens = tokens;
}
public boolean hasNext() {
return tokens.getType() != Type.EOF;
}
public String peek() {
return tokens.getData();
}
public String next() {
String data = tokens.getData();
if(tokens.getType() == Type.Error) new Exception("unexpected token : " + data).printStackTrace();
tokens = tokens.next;
return data;
}
public String next(String expected) {
String data = tokens.getData();
if(!data.equals(expected) || tokens.getType() == Type.Error) new Exception("unexpected token : " + data).printStackTrace();
tokens = tokens.next;
return data;
}
public String next(Type expected) {
String data = tokens.getData();
if(tokens.getType() != expected || tokens.getType() == Type.Error) new Exception("unexpected token : " + data).printStackTrace();
tokens = tokens.next;
return data;
}
public boolean is(String data) {
return tokens.getData().equals(data);
}
public boolean is(Type type) {
return tokens.getType() == type;
}
}
StringReaderのときとあまり変わらないので、説明は省きます。
構文木のクラスと、トークンを読み込むためのクラスを作ったので、いよいよこれらを基にして構文解析器のクラスParserを作っていきましょう！実装の概要は次のような感じです。
public class Parser {
private TokenReader tr;
private Tree tree;
public Tree parse(Token tokens) {
this.tr = new TokenReader(tokens);
tree = new Tree();
ExpressionNode expr = parseExpression();
tree.addExpression(expr);
tr.next(Type.EOF);
return tree;
}
private ExpressionNode parseExpression() {
/*
* <expression> := <unary> { ( `+` | `-` | `*` ) <term> };
*/
}
private ExpressionNode parseUnaryExpression() {
/*
* <unary> := [ ( `+` | `-` ) ] <term>;
*/
}
private ExpressionNode parseTermExpression() {
/*
* <term> := ( <identifier> | <number> | `(` <expression> `)` ) [ `^` <number> ]
*/
}
private ExpressionNode parseIdentifierExpression() {
/*
* <identifier>;
*/
}
private ExpressionNode parseNumberExpression() {
/*
* <number>;
*/
}
private ExpressionNode parseParenExpression() {
/*
* `(` <expr> `)`;
*/
}
}
先ほども言ったように、基本的には書き下したEBNFの構文を「丸写し」するだけです。
parse()メソッドが呼び出されると、まずは構文木全体を収納するtreeを初期化します。
つぎにparseExpression()メソッドに始まる、構文木を再帰的に生成する一連のルーチンを実行してtreeの下に格納し、最後にきちんと最後まで構文解析が終わったことを確かめるためEOF型のトークンを読み込んでおしまいです。
簡単なところから見ていきましょう。
/*
* <identifier>;
*/
private ExpressionNode parseIdentifierExpression() {
IdentifierExpressionNode ien = new IdentifierExpressionNode();
ien.identifier = tr.next(Type.Identifier);
return ien;
}
/*
* <number>;
*/
private ExpressionNode parseNumberExpression() {
NumberExpressionNode nen = new NumberExpressionNode();
nen.number = tr.next(Type.Number);
return nen;
}
/*
* `(` <expr> `)`;
*/
private ExpressionNode parseParenExpression() {
tr.next("(");
ExpressionNode en = parseExpression();
tr.next(")");
return en;
}
この3つはとても簡単です。先ほど作ったノードクラスをEBNFで書き下した構文の定義に従って使い分けています。ここまで処理が簡単になったのは、事前に字句解析によって<identifier>と<number>を型で分類しておいたからです。字句解析に圧倒的感謝???
さて、構文解析は、ある種の構文を解析していくことですが、これは裏を返せば、構文解析をする側がある種の構文を要求するということを意味しています。つまり構文解析は常にある種の構文で書かれていることを期待して実行されます。parseParenExpression()で言えば、次に来るのが(` <expr> `)だと仮定して、まず左括弧の(を確認します。ここで読み込んだものが(と違ければもちろんエラーが吐かれます。つぎに<expr>をparseExpression()を用いて再帰的に処理して、それが終わったら右括弧)を確認します。
再帰とEBNFのおかげで、これらの一見複雑な操作が、非常に明快になっているという事実に気づいたでしょうか？
他の処理も基本的には同じようなやり方で、スマートに実装していくことができます。
/*
* <unary> := [ ( `+` | `-` ) ] <term>;
*/
private ExpressionNode parseUnaryExpression() {
if(tr.is("+")) tr.next("+");
else if(tr.is("-")) {
UnaryExpressionNode uen = new UnaryExpressionNode();
tr.next("-");
uen.op = "~";
uen.rhs = parseTermExpression();
return uen;
}
return parseTermExpression();
}
/*
* <term> := ( <identifier> | <number> | `(` <expression> `)` ) [ `^` <number> ];
*/
private ExpressionNode parseTermExpression() {
ExpressionNode en = null;
if(tr.is(Type.Identifier)) en = parseIdentifierExpression();
else if(tr.is(Type.Number)) en = parseNumberExpression();
else if(tr.is("(")) en = parseParenExpression();
else new Exception("unexpected token : " + tr.peek()).printStackTrace();
if(tr.is("^")) {
TermExpressionNode ten = new TermExpressionNode();
ten.lhs = en;
ten.op = tr.next("^");
ten.rhs = parseNumberExpression();
return ten;
}
return en;
}
このようにif文を駆使すれば、簡単に実装できます。parseUnaryExpression()の中身について補足をしておくと、読み込んだものが+のときは、あってもなくても論理的には同等なので、後の処理の単純化を図って読み飛ばしてしまいます。
一方-のときは、勝手に取り外すわけにも行きません。ですが、二項演算子としての-と混同するのもよくないので、代わりに~という演算子に差し替えました。
肝心(そして問題)なのは、最後に残したparseExpression()の実装です。先ほど書き下したEBNFの構文では+、-と*とをまとめて扱ってしまいました。これを疑問に感じた人もいるかもしれません。実際、加減と乗算は異なる演算なので、それぞれを同じように扱うわけには行きません。すなわち、これらの間には演算子の優先順位が生じます。一般に、2つの異なる演算が結合的でないならば、それぞれの演算の優先度には違いを設けるべきです。ふつうは慣例として*の優先度が高く設定されます。もちろんここでもこの慣例に従いましょう。したがって必然的に生じるのが、演算子の優先順位を考慮する必要性です。
/*
* <expression> := <unary> { ... };
*/
private ExpressionNode parseExpression() {
ExpressionNode lhs = parseUnaryExpression();
return parseBinaryExpression(lhs, 0);
}
/*
* ... { ( `+` | `-` | `*` ) <term> };
*/
private ExpressionNode parseBinaryExpression(ExpressionNode lhs, int minPrec) {
int prec;
while((prec = getPrec(tr.peek())) >= minPrec) {
String op = tr.next(Type.Symbol);
ExpressionNode rhs = parseTermExpression();
if(getPrec(tr.peek())>prec) rhs = parseBinaryExpression(rhs, prec+1);
BinaryExpressionNode ben = new BinaryExpressionNode();
ben.lhs = lhs;
ben.op = op;
ben.rhs = rhs;
lhs = ben;
}
return lhs;
}
/*
* return the precedence of given `String` operator as `int`. return -1 if given one is not an operator.
*/
private int getPrec(String operator) {
String[][] a = Constants.OPERATOR_PRECEDENCES;
for (int i = 0; i < a.length; i++) for (int j = 0; j < a[i].length; j++) {
if (a[i][j].equals(operator)) return i;
}
return -1;
}
うわぁちょっとややこしいですね・・・。
一番下のgetPrec()は演算子の優先度をint値で返すものです。中で使われているConstants.OPERATOR_PRECEDENCESは
public static final String[][] OPERATOR_PRECEDENCES = {
{"+", "-"},
{"*"},
};
です。配列の順序を用いて巧妙にこの演算子の優先度をあらわすint値を計算します。
parseExpression()とparseBinaryExpression()の説明です。後者は文字通り二項演算を処理するメソッドです。
構文に沿って、まずは<unary>を読み込みます。つぎにparseBinaryExpression()の中で演算子と、続いて<term>を読み込みます。ふつうならこれらをまとめてBinaryExpressionNodeに入れて返します。benに代入する部分がそれです。
しかし5+2*xとかを考えてみてください。わたしたちが<unary>として5を読み込んだとしましょう。つぎに演算子+を読み込んで2を読み込みました。ところが次の演算子は*です。*のほうが+よりも優先順位が大きいのですからBinaryExpressionNodeとして先にまとめるべきなのは5+2ではなく2*xです。それが
if(getPrec(tr.peek())>prec) rhs = parseBinaryExpression(rhs, prec+1);
の意味です。2*xを先にまとめて、その後5と+と2*xをまとめるということです。
ここは再帰処理と優先度による条件分岐が入り混じっていてすごく混乱しますが、やっていることはざっくりと把握できたでしょうか。
これでParserはおしまい。今回の山場もおしまいです。こうしてトークン列tokensを入れると構文木treeが得られるパーサが完成しました。
でも、構文木の何がうれしいんでしょうか？
今回の場合は、式の逆ポーランド記法が構文木のおかげで簡単に得られることです。
たとえば
-(x+2*y-(-2+(+7)*x^2)^3)*(-21)
という式を文字列で入力して、パーサにかけてdumpRPN()を実行したところ、
x 2 y * + 2 ~ 7 x 2 ^ * + 3 ^ - ~ 21 ~ *
という文字列が得られました。
このように、どんなに複雑な式でも簡単に逆ポーランド記法が得られるのです。
さて、最後のステップである意味解析では、この「逆ポーランド記法」が重要な役割を担います。
というのも、逆ポーランド記法は式を計算機で処理する上で非常に適した記法なのです。
次節では、それらを実装していきましょう！
意味解析
意味解析は文字通り、式を意味付けしていく処理のことです。パーサを通して、入力した式を逆ポーランド記法で表わしたものが得られたので、あとはこれに実際の処理を対応させるだけです。
ところで、逆ポーランド記法について説明をし損ねていました。
数式の表記の仕方には主にポーランド記法と中置記法、そして逆ポーランド記法と呼ばれるものがあります。
私たちが普段使っている、文字と文字の間に演算子を置くやり方は中置記法というもので、それに対しポーランド記法は演算子を左に、逆ポーランド記法は演算子を右に置くやり方です。
計算機で左から右へ処理をしていくときは、逆ポーランド記法で書かれた式を用いるのが適しています。なぜなら数式の順番と処理の順番が一致しているからです。
まずは式を格納するデータ構造Property<S>を定義します。これ以降ちょくちょく型パラメータ(Javaではジェネリクス)を使っていますが、単なる抽象化なのであまり気にしないでください。
public class Property<S> {
public String name;
public S data;
public Property(String name, S data) {
this.name = name;
this.data = data;
}
}
式と、その意味を表わすデータ構造Sをもつクラスです。これ自体は何てことありませんね。
そして、式と実際の処理を対応させる上で、実際の処理にあたるインターフェースImpl<S>を定義します。
public interface Impl<S> {
public S add(S a, S b);
public S sub(S a, S b);
public S mul(S a, S b);
public S div(S a, S b);
public S pow(S a, int n);
public S scale(S a, int n);
public S compile(String s);
}
add()やmul()は単なる二項演算ですね。pow()やscale()もわかると思います。
そしてcompile()は、文字列をデータ構造Sに対応させる規則を表わすメソッドです。
これらを基にして、意味解析を行うクラスAnalyzerを定義しましょう。
public class Analyzer<S> {
private ArrayList<Property<S>> stack;
private int i;
private Impl<S> impl;
public Property<S> analyze(Tree tree, Impl<S> impl) {
this.stack = new ArrayList<Property<S>>();
this.impl = impl;
this.i = 0;
runRPN(tree.expr.dumpRPN());
return stack.get(0);
}
private void runRPN(String rpn) {
String[] data = rpn.split(" ");
for(String s : data) {
switch(s) {
case "+" :
binOp(s); break;
case "-" :
binOp(s); break;
case "*" :
binOp(s); break;
case "^" :
pow(); break;
case "~" :
unOp(s); break;
default :
push(s, impl.compile(s)); break;
}
}
}
private void push(String name, S data) {
Property<S> property = new Property<S>(name, data);
if(i<stack.size()) stack.set(i, property); else stack.add(i, property);
stack.get(i).name = name;
stack.get(i).data = data;
i++;
}
private Property<S> pop() {
return stack.get(--i);
}
}
ここからは構文解析というより、逆ポーランド記法の式を処理するアルゴリズムの説明だといってもいいかもしれません。
さて、逆ポーランド記法の式の処理は「スタック」と組み合わせることで行うことができます。これはデータを「積みあげておく」物置場のようなものです。
Analyzerクラスもこのスタックを変数stackとしてもっています。
int型変数iの意味ですが、これまでのStringReaderやTokenReaderと同じように、今度はstackの要素を指し示すイテレータのような役割を果たします。専用のクラスを用意してもいいのですが、まあ特に問題は無いでしょう。
そしてimplは意味解析をする上での「実装」を格納する変数です。これを使えば、実装はほかのところに任せることができます。
analyzer()を呼び出してこれらの変数を初期化すると、いよいよ与えらえたtreeから得た逆ポーランド記法の式に処理を対応させるrunRPN()が実行されます。
与えられる式はトークンごとにスペースで区切ってあるので、まずはこれらを分割して配列に入れます。これらをfor文で順番に処理していきます。
逆ポーランド記法の式を処理する方法は簡単です。
まず、取り出したトークンが演算子でなければこれをスタックに積み上げます。これを行うのがpush()メソッドで、文字列とそれの実装を引数として入れると、勝手にProperty<S>インスタンスを生成してスタックに積み上げてくれます。
そして、取り出したトークンが演算子の場合は、演算子の種類によって処理を分け、その処理の過程で適宜スタックからデータを取り出してきます。それがpop()メソッドです。処理結果はふたたび、push()でstackに戻します。
これらを左から順番に行っていくことで、最終的に全体の処理結果を得ることができるのです。
runRPN()の中でやっていることはこのことにほかなりません。
では、各演算子の下でどのような処理を行っていくか、詳しく見ていきたいと思います。
private void binOp(String op) {
Property<S> lhs, rhs;
rhs = pop();
lhs = pop();
S a = lhs.data==null?lhs.data = impl.compile(lhs.name):lhs.data;
S b = rhs.data==null?rhs.data = impl.compile(rhs.name):rhs.data;
S tmp = null;
switch(op) {
case "+" :
tmp = impl.add(a, b); break;
case "-" :
tmp = impl.sub(a, b); break;
case "*" :
tmp = impl.mul(a, b); break;
case "/" :
tmp = impl.div(a, b); break;
}
push(tmp.toString(), tmp);
}
private void unOp(String op) {
Property<S> rhs = pop();
S a = rhs.data==null?rhs.data = impl.compile(rhs.name):rhs.data;
S tmp = null;
switch(op) {
case "~" :
tmp = impl.scale(a, -1); break;
}
push(tmp.toString(), tmp);
}
private void pow() {
Property<S> lhs, rhs;
rhs = pop();
lhs = pop();
S a = lhs.data==null?lhs.data = impl.compile(lhs.name):lhs.data;
int n = Integer.parseInt(rhs.name);
S tmp = impl.pow(a, n);
push(tmp.toString(), tmp);
}
処理に大きな違いが出てくるのは、+,-,*と^と~です。1つ目は二項演算で2つ目は第2引数をint値としてとるので二項演算とは違います。3つ目は単項演算子です。そこでそれぞれbinOp()やpow()、unOp()を用意しました。
どれも最初は、スタックから被演算子を表すProperty<S>インスタンスを取り出してきます。二項演算子の場合は2つ、単項演算子の場合は1つです。そしてそれらから実際のデータ構造<S>のインスタンスを取り出します。
これをもとに、実装implに従って新たな<S>のインスタンスを得てスタックに戻します。これが一連の処理の流れです。あとは最終的な結果として残ったデータ構造を返すだけです。
これで意味解析はおしまいです。構文解析に比べたら意外とあっさり終わってしまいました。
えーっと、そういえば今回は多項式を文字列として入力して、あとは内部実装に任せられるようにするというのが目標でしたね。実際、意味解析まで終わって、文字列に実際の意味を対応させるところまでができるようになったので、僕がやりたいことはほとんど達成されてしまいました。
あとは実際にデータ構造Sと実装Impl<S>を具体的に決めて、実装するだけですね。
・・・ということで、ユーザの扱うことのできる多項式クラスPolynomialと、その実装クラスとしてのPolynomialImplを実装しました！
ですが、ここの実装は単に「やるだけ」の愚直な作業で、コードも読みにくいので、解説もしなければここにコードを載せることもしません。個人的にpow()の実装が辛かったです。
Sとして僕はMap<int[], Long>を選びました。これは各単項式の各変数の次数をint[]型のキーとして、これに係数を表す値Longを対応させるものです。
実際にこの情報からもとの多項式を復元することができます。もちろん同じ多項式の表現が可能なデータ構造はほかにも色々あるので、実装の方法は自由です。
最後に得られたアウトプットをまとめてみましょうか。たとえば
((-37*x)^2 + (-y)^2 + a^2 - 3*((-x)*y+(-3)*a)^2*a + 3*a*(-x))^5
という式を入力してみます。するとまずトークン列は次のような感じになりました。
[ symbol : ( ] [ symbol : ( ] [ symbol : - ] [ number : 37 ] [ symbol : * ] [ identifier : x ] [ symbol : ) ] [ symbol : ^ ] [ number : 2 ] [ symbol : + ] [ symbol : ( ] [ symbol : - ] [ identifier : y ] [ symbol : ) ] [ symbol : ^ ] [ number : 2 ] [ symbol : + ] [ identifier : a ] [ symbol : ^ ] [ number : 2 ] [ symbol : - ] [ number : 3 ] [ symbol : * ] [ symbol : ( ] [ symbol : ( ] [ symbol : - ] [ identifier : x ] [ symbol : ) ] [ symbol : * ] [ identifier : y ] [ symbol : + ] [ symbol : ( ] [ symbol : - ] [ number : 3 ] [ symbol : ) ] [ symbol : * ] [ identifier : a ] [ symbol : ) ] [ symbol : ^ ] [ number : 2 ] [ symbol : * ] [ identifier : a ] [ symbol : + ] [ number : 3 ] [ symbol : * ] [ identifier : a ] [ symbol : * ] [ symbol : ( ] [ symbol : - ] [ identifier : x ] [ symbol : ) ] [ symbol : ) ] [ symbol : ^ ] [ number : 5 ] [ EOF ]
長いですね・・・。そしてこれらのトークン列をもとに得られるのは、次のような逆ポーランド記法で書かれた式です。
37 ~ x * 2 ^ y ~ 2 ^ + a 2 ^ + 3 x ~ y * 3 ~ a * + 2 ^ * a * - 3 a * x ~ * + 5 ^
はい。ここまではいいでしょう。
そして最後に得られた計算結果をtoString()で出力したものがこちらです。
- 14348907*a^15 - 47829690*a^14*x*y + 2657205*a^14 - 71744535*a^13*x^2*y^2 + 7085880*a^13*x*y - 7971615*a^13*x - 196830*a^13 - 63772920*a^12*x^3*y^3 + 8266860*a^12*x^2*y^2 - 21257640*a^12*x^2*y + 3637713645*a^12*x^2 - 393660*a^12*x*y + 1180980*a^12*x + 2657205*a^12*y^2 + 7290*a^12 - 37200870*a^11*x^4*y^4 + 5511240*a^11*x^3*y^3 - 24800580*a^11*x^3*y^2 + 9700569720*a^11*x^3*y - 328050*a^11*x^2*y^2 + 2361960*a^11*x^2*y - 540692010*a^11*x^2 + 7085880*a^11*x*y^3 + 9720*a^11*x*y - 65610*a^11*x - 393660*a^11*y^2 - 135*a^11 - 14880348*a^10*x^5*y^5 + 2296350*a^10*x^4*y^4 - 16533720*a^10*x^4*y^3 + 11317331340*a^10*x^4*y^2 - 145800*a^10*x^3*y^3 + 1968300*a^10*x^3*y^2 - 1081384020*a^10*x^3*y + 1616761620*a^10*x^3 + 8266860*a^10*x^2*y^4 + 4860*a^10*x^2*y^2 - 87480*a^10*x^2*y + 30136860*a^10*x^2 - 787320*a^10*x*y^3 + 1180980*a^10*x*y^2 - 90*a^10*x*y + 1620*a^10*x + 21870*a^10*y^2 + a^10 - 4133430*a^9*x^6*y^6 + 612360*a^9*x^5*y^5 - 6889050*a^9*x^5*y^4 + 7544887560*a^9*x^5*y^3 - 36450*a^9*x^4*y^4 + 874800*a^9*x^4*y^3 - 901153350*a^9*x^4*y^2 + 3233523240*a^9*x^4*y - 368891109630*a^9*x^4 + 5511240*a^9*x^3*y^5 + 1080*a^9*x^3*y^3 - 43740*a^9*x^3*y^2 + 40182480*a^9*x^3*y - 179837010*a^9*x^3 - 656100*a^9*x^2*y^4 + 2361960*a^9*x^2*y^3 - 538920555*a^9*x^2*y^2 + 1080*a^9*x^2*y - 746550*a^9*x^2 + 29160*a^9*x*y^3 - 131220*a^9*x*y^2 - 15*a^9*x - 196830*a^9*y^4 - 540*a^9*y^2 - 787320*a^8*x^7*y^7 + 102060*a^8*x^6*y^6 - 1837080*a^8*x^6*y^5 + 3143703150*a^8*x^6*y^4 - 4860*a^8*x^5*y^5 + 218700*a^8*x^5*y^4 - 400512600*a^8*x^5*y^3 + 2694602700*a^8*x^5*y^2 - 737782219260*a^8*x^5*y + 2296350*a^8*x^4*y^6 + 90*a^8*x^4*y^4 - 9720*a^8*x^4*y^3 + 20091240*a^8*x^4*y^2 - 239782680*a^8*x^4*y + 41257361340*a^8*x^4 - 291600*a^8*x^3*y^5 + 1968300*a^8*x^3*y^4 - 1077841080*a^8*x^3*y^3 + 180*a^8*x^3*y^2 - 497700*a^8*x^3*y + 6667920*a^8*x^3 + 14580*a^8*x^2*y^4 - 174960*a^8*x^2*y^3 + 60076890*a^8*x^2*y^2 + 6935*a^8*x^2 - 393660*a^8*x*y^5 - 360*a^8*x*y^3 + 4860*a^8*x*y^2 + 21870*a^8*y^4 + 5*a^8*y^2 - 98415*a^7*x^8*y^8 + 9720*a^7*x^7*y^7 - 306180*a^7*x^7*y^6 + 838320840*a^7*x^7*y^5 - 270*a^7*x^6*y^6 + 29160*a^7*x^6*y^5 - 100128150*a^7*x^6*y^4 + 1197601200*a^7*x^6*y^3 - 614818516050*a^7*x^6*y^2 + 612360*a^7*x^5*y^7 - 810*a^7*x^5*y^4 + 4464720*a^7*x^5*y^3 - 119891340*a^7*x^5*y^2 + 55009815120*a^7*x^5*y - 122963703210*a^7*x^5 - 72900*a^7*x^4*y^6 + 874800*a^7*x^4*y^5 - 898200900*a^7*x^4*y^4 - 82950*a^7*x^4*y^2 + 4445280*a^7*x^4*y - 1538041365*a^7*x^4 + 3240*a^7*x^3*y^5 - 87480*a^7*x^3*y^4 + 80102520*a^7*x^3*y^3 - 179640180*a^7*x^3*y^2 - 82410*a^7*x^3 - 328050*a^7*x^2*y^6 - 60*a^7*x^2*y^4 + 3240*a^7*x^2*y^3 - 2232360*a^7*x^2*y^2 + 29160*a^7*x*y^5 - 65610*a^7*x*y^4 - 60*a^7*x*y^2 - 810*a^7*y^4 - 7290*a^6*x^9*y^9 + 405*a^6*x^8*y^8 - 29160*a^6*x^8*y^7 + 139720140*a^6*x^8*y^6 + 1620*a^6*x^7*y^6 - 13350420*a^6*x^7*y^5 + 299400300*a^6*x^7*y^4 - 273252673800*a^6*x^7*y^3 + 102060*a^6*x^6*y^8 + 372060*a^6*x^6*y^4 - 26642520*a^6*x^6*y^3 + 27504907560*a^6*x^6*y^2 - 163951604280*a^6*x^6*y + 18704145521610*a^6*x^6 - 9720*a^6*x^5*y^7 + 218700*a^6*x^5*y^6 - 399200400*a^6*x^5*y^5 + 740880*a^6*x^5*y^2 - 1025360910*a^6*x^5*y + 9128382480*a^6*x^5 + 270*a^6*x^4*y^6 - 19440*a^6*x^4*y^5 + 40051260*a^6*x^4*y^4 - 239520240*a^6*x^4*y^3 + 40987901070*a^6*x^4*y^2 + 19111645*a^6*x^4 - 145800*a^6*x^3*y^7 + 540*a^6*x^3*y^4 - 1488240*a^6*x^3*y^3 + 13321260*a^6*x^3*y^2 + 14580*a^6*x^2*y^6 - 87480*a^6*x^2*y^5 + 29940030*a^6*x^2*y^4 + 27650*a^6*x^2*y^2 - 540*a^6*x*y^5 + 4860*a^6*x*y^4 + 7290*a^6*y^6 + 10*a^6*y^4 - 243*a^5*x^10*y^10 - 1215*a^5*x^9*y^8 + 13306680*a^5*x^9*y^7 - 741690*a^5*x^8*y^6 + 39920040*a^5*x^8*y^5 - 68313168450*a^5*x^8*y^4 + 9720*a^5*x^7*y^9 - 2220210*a^5*x^7*y^4 + 6112201680*a^5*x^7*y^3 - 81975802140*a^5*x^7*y^2 + 24938860695480*a^5*x^7*y - 540*a^5*x^6*y^8 + 29160*a^5*x^6*y^7 - 99800100*a^5*x^6*y^6 - 170893485*a^5*x^6*y^2 + 6085588320*a^5*x^6*y - 1399154894550*a^5*x^6 - 1620*a^5*x^5*y^6 + 8900280*a^5*x^5*y^5 - 119760120*a^5*x^5*y^4 + 54650534760*a^5*x^5*y^3 - 169413993*a^5*x^5 - 36450*a^5*x^4*y^8 - 248040*a^5*x^4*y^4 + 8880840*a^5*x^4*y^3 - 3056100840*a^5*x^4*y^2 + 3240*a^5*x^3*y^7 - 43740*a^5*x^3*y^6 + 39920040*a^5*x^3*y^5 - 246960*a^5*x^3*y^2 - 90*a^5*x^2*y^6 + 3240*a^5*x^2*y^5 - 2225070*a^5*x^2*y^4 + 9720*a^5*x*y^7 - 90*a^5*x*y^4 - 540*a^5*y^6 + 554445*a^4*x^10*y^8 + 2217780*a^4*x^9*y^6 - 9108422460*a^4*x^9*y^5 + 405*a^4*x^8*y^10 + 509350140*a^4*x^8*y^4 - 18216844920*a^4*x^8*y^3 + 12469430347740*a^4*x^8*y^2 + 1620*a^4*x^7*y^8 - 13306680*a^4*x^7*y^7 + 1014264720*a^4*x^7*y^2 - 932769929700*a^4*x^7*y + 4156476782580*a^4*x^7 + 741690*a^4*x^6*y^6 - 26613360*a^4*x^6*y^5 + 27325267380*a^4*x^6*y^4 + 26163842005*a^4*x^6 - 4860*a^4*x^5*y^9 + 1480140*a^4*x^5*y^4 - 2037400560*a^4*x^5*y^3 + 9108422460*a^4*x^5*y^2 + 270*a^4*x^4*y^8 - 9720*a^4*x^4*y^7 + 19960020*a^4*x^4*y^6 + 56964495*a^4*x^4*y^2 + 540*a^4*x^3*y^6 - 1483380*a^4*x^3*y^5 + 6653340*a^4*x^3*y^4 + 4860*a^4*x^2*y^8 + 41340*a^4*x^2*y^4 - 360*a^4*x*y^7 + 1620*a^4*x*y^6 + 10*a^4*y^6 - 506023470*a^3*x^10*y^6 - 1518070410*a^3*x^9*y^4 + 2770984521720*a^3*x^9*y^3 - 739260*a^3*x^8*y^8 - 155461654950*a^3*x^8*y^2 + 2770984521720*a^3*x^8*y - 474184726279335*a^3*x^8 - 2217780*a^3*x^7*y^6 + 6072281640*a^3*x^7*y^5 - 154449608010*a^3*x^7 - 270*a^3*x^6*y^10 - 339566760*a^3*x^6*y^4 + 6072281640*a^3*x^6*y^3 - 1385492260860*a^3*x^6*y^2 - 810*a^3*x^5*y^8 + 4435560*a^3*x^5*y^7 - 338088240*a^3*x^5*y^2 - 247230*a^3*x^4*y^6 + 4435560*a^3*x^4*y^5 - 1518070410*a^3*x^4*y^4 + 1080*a^3*x^3*y^9 - 246690*a^3*x^3*y^4 - 60*a^3*x^2*y^8 + 1080*a^3*x^2*y^7 - 739260*a^3*x^2*y^6 - 60*a^3*x*y^6 - 135*a^3*y^8 + 230915376810*a^2*x^10*y^4 + 461830753620*a^2*x^9*y^2 - 316123150852890*a^2*x^9*y + 506023470*a^2*x^8*y^6 + 17793312646415*a^2*x^8 + 1012046940*a^2*x^7*y^4 - 923661507240*a^2*x^7*y^3 + 369630*a^2*x^6*y^8 + 51820551650*a^2*x^6*y^2 + 739260*a^2*x^5*y^6 - 1012046940*a^2*x^5*y^5 + 90*a^2*x^4*y^10 + 56594460*a^2*x^4*y^4 + 180*a^2*x^3*y^8 - 492840*a^2*x^3*y^7 + 27470*a^2*x^2*y^6 - 90*a^2*x*y^9 + 5*a^2*y^8 - 52687191808815*a*x^10*y^2 - 52687191808815*a*x^9 - 153943584540*a*x^8*y^4 - 153943584540*a*x^7*y^2 - 168674490*a*x^6*y^6 - 168674490*a*x^5*y^4 - 82140*a*x^4*y^8 - 82140*a*x^3*y^6 - 15*a*x^2*y^10 - 15*a*x*y^8 + 4808584372417849*x^10 + 17562397269605*x^8*y^2 + 25657264090*x^6*y^4 + 18741610*x^4*y^6 + 6845*x^2*y^8 + y^10
なんだこれ(困惑)
式は内部で計算できるところまで計算されるので、このように展開された形式で表示されます。ちなみにこれらの処理にかかった時間は平均で120msぐらいでした。累乗を頑張って最適化した甲斐があったと思います。
PolynomialImplに演算アルゴリズムは実装してあるので、もちろん異なる多項式同士を加減乗累するのも簡単です。
ということでついに、目指していたことができるようになりました！おめでとうございます！！
いや～こんなの手入力でなんかやってられんわな～。
まとめ！
以上で構文解析入門はおしまいです！すこしは有意義な記事になったでしょうか？？
構文解析に関する今の僕の知見は、ここでほとんど出しつくしてしまいました。
実は記事を書き始めたとき、こんな2万文字を超えるクソ長記事になるとは思っていませんでした・・・。もしかしたらAdCでやるべき題材じゃなかったかもしれません。長ったらしいので複数回に分けたいぐらいです。
所感ですが、多項式を文字列で扱うというだけで、ここまでたくさんのことをやる羽目になるとは思ってませんでした。(でもやりがいがあって楽しかったです。
最初はちょっと文字列で入力できるようにしようと思っただけだったのに、結局構文解析自体を学ぶことになるとは・・・。
そういえば今回、多項式の構文解析のためだけに、いろいろとたくさんクラスを作りましたね。多項式に関して言えば、実際ここまで細かくクラスを分けてやる必要はないかもしれません。
でもコンパイラとかを作りたい場合は、このぐらい、あるいはもっとたくさんのクラスを用意する必要が出てくると思います。今回、わざと冗長にやったのはそういったことを念頭においてのことです。僕はコンパイラを作る気なんてありませんが。
この記事を読んで、構文解析に興味を持った方はいろいろ調べてみてください。
最近のプログラミング言語は、高級言語で書かれていてオープンソースなことも多いので、そういうのを読んでみるのもいいかもしれません。(ぼくは読んでません
この記事を通じて、少しでも知見を得たり、興味を持っていただけたなら幸いです。
それと、今回の構文解析の全コードは未公開の部分も含めてこちらにおいておきますので、自由に使ってください。少しでも参考になればうれしいです。
Wolfram Alphaでいくつか検算したところ一見、今回作った多項式のプログラムの計算結果に間違いはありませんでした。longがオーバーフローしない限り正しい結果を出してくれるはずです。
ですが、急いで書いたのでちょくちょくバグがあるかもしれません。そこはご了承ください。
個人的な次の目標ですが、係数の体を自由に選べるように拡張したいです。それとGröbner基底の計算ですね。
最後に、ここまで読んでくださった方はありがとうございました！なにかツッコミとかあれば、コメントとかにお願いします！※構文解析のプロによる熱い鉞はお止めください！
そして、明日以降を担当する方はよろしくお願いいたします。
それでは、traP Advent Calendar 2016の12日目はれおなちゃんが担当させていただきました。よいお年を！
