伝えたいこと
- 構文木という木構造で表現することができる。
- 便利なのは「関心の分離ができているから」
優先度をつけて処理をしていきたい！
前回までで、単語単語をrecordというものの集合に分けられたので、次は構文木というものを作る作業になる。
抽象構文木とは
今のTokenの状態はただのやるべきことの集まりの状態である。この状態には処理するにあたっての２つの課題が存在する
-
（や）といった実際の処理に関係ない（処理順のみを定義している）文字が存在する - やるべきことの集まりが関係性を明確に持っていない（例えばAddには、引数があるはずだが引数がどれなのかわからない）
実際Tokenの定義には(、)が含まれていることやPlusに果たすために必要な引数についての情報が載っていません。
public abstract record Token();
public abstract record TokenSymble():Token;
public record TokenNumber(int Number):Token;
public record TokenPlus():TokenSymble;
public record TokenSlash():TokenSymble;
public record TokenMinus():TokenSymble;
public record TokenAsterisk():TokenSymble;
public record TokenStartSection():Token;
public record TokenEndSection():Token;
一方で抽象構文木を作る際に使われるrecordとして定義したASTには実際に使う演算子とその引数、数字だけが残っています！
public abstract record Ast();
public record AstNumber(int Number) : Ast;
public record AstAdd(Ast hidari, Ast migi) : Ast;
public record AstSub(Ast hidari, Ast migi) : Ast;
public record AstMul(Ast hidari, Ast migi) : Ast;
public record AstDiv(Ast hidari, Ast migi) : Ast;
実際にはASTはこのようなデータ構造として表現されます。
入力値： 1+2+3*4
AstAdd {
hidari = AstAdd {
hidari = AstNumber { Number = 1 },
migi = AstNumber { Number = 2 }
},
migi = AstMul {
hidari = AstNumber { Number = 3 },
migi = AstNumber { Number = 4 }
}
}
抽象構文木に解釈する実装手法として再起下降パーサーというものがあるので今回はそれを使う。
再帰降下パーサーとその嬉しさ。
再帰呼び出しを活用したパーサーのことを指す。トークンや文字列を、左から読み進め各処理単位（≒関数）が各文法のルールを実装できるためプログラムの構造と文法の構造が似通った構造になる利点がある。また、Haskellなどの関数型言語との相性が特に良い。
「処理単位が各文法のルール実装できる」ということはどういうことか
一つの文法の生成規則、例えばAdd（left,right）は二つの引数の合計を足す操作といった部分、を一つの関数として括り出しそれ以外については関心を持たなくて良い状態になるということを表現している。
メリットとして以下を上げられる。
- 親関数は子関数を呼び出しており、子関数を呼び出して解釈した結果を持って初めて親関数が処理を行うような構造にすることで状態を管理する関数が不用になる。
- 演算子に対して強さ、例えば
+、-よりも*や/が優先されること、を表現することが可能である（最初に呼び出し先の処理をやって残ったものを呼び出し元が実装するので親＜子になる。）
実際にそれを意識して書いたコードが以下になる。それぞれのTokenの時のやることがcase以下のみに収まっており、優先度が同等の処理が同じ関数内にまとまり処理の見通しが良いことがわかるだろう。
(全体のソースコード）
{
public static (Ast, shisoku.Token[]) parse(shisoku.Token[] input)
{
(var result, var rest) = parseMaldiv(input);
while (rest is [TokenPlus or TokenMinus, .. var rest2])
{
switch (rest[0])
{
case TokenPlus:
var (addRhs, addRest) = parseMaldiv(rest2);
result = new AstAdd(result, addRhs);
rest = addRest;
break;
//（中略）
}
}
return (result, rest);
}
public static (Ast, shisoku.Token[]) parseMaldiv(shisoku.Token[] input)
{
(var result, var rest) = parseNumOrSection(input);
while (rest is [TokenSlash or TokenAsterisk, .. var rest2])
{
switch (rest[0])
{
case TokenAsterisk:
// （中略）
}
return (result, rest);
}
// （以下略）
while (rest is [TokenPlus or TokenMinus, .. var rest2])
このWhile文の条件式は変数restがTokenPlusもしくはTokenMinusで始まるときである。その上で２番目の要素意向をrest2の配列に格納するということもさらに行なっている。条件式であるTokenPlusもしくはTokenMinusを表現するだけであればTokenPlusとTokenMinusの継承元をTokenを継承したTokenPlusMinusにするだけで
while (rest is [TokenPlusMinus, .. var rest2])
という形で表現することもできる。リストパターン内でorが展開できるということを覚えていれば便利な場面は多くあるので覚えておくと便利なテクではある。