はじめに
コンパイラ実装の処理過程に構文解析があります。
単純な字句解析をJavaで実装するの続きで、
構文解析のごくごく原始的なものをJavaで実装してみたいとおもいます。
構文解析でやりたいこと
実装にあたりやりたいことを確認します。
プログラムになっている文字列が四則演算だったとします。
構文解析ではその四則演算をどういう順序で計算するかを解析します。
下の式を例に考えます。
a = 3 + 4 * 5
一目瞭然ですが、下の順序で括弧を付けた部分から計算します。
(4 * 5)
(3 + (4 * 5))
(a = (3 + (4 * 5)))
構文解析ではこの順序付けを行います。
実際のプログラムでは関数の定義や呼び出しなどがあります。
簡単のためにまずは四則演算と、変数への代入が解析できることをめざします。
順序付けの表現方法
順序付けをしたいことは分かりました。
順序付けした状態を実装でどう表現するか考えます。
例の式の一部、4 * 5
からみていきましょう。
前回の記事で式をトークンへ分解しました。
4 * 5
はトークンに分解すると、4
、*
、5
の3つになります。
ここで4 * 5
の状態を表現するために、*
トークンに対して、左に4
トークン、右に5
トークンを持っているとわかるように、フィールド変数を追加してあげます。
具体的には前回の記事のTokenクラスの実装に、left
とright
を追加してあげます。
public class Token {
public String kind;
public String value;
public Token left;
public Token right;
@Override
public String toString() {
return kind + " \"" + value + "\"";
}
public String paren() {
if (left == null && right == null) {
return value;
} else {
StringBuilder b = new StringBuilder();
b.append("(");
if (left != null) {
b.append(left.paren()).append(" ");
}
b.append(value);
if (right != null) {
b.append(" ").append(right.paren());
}
b.append(")");
return b.toString();
}
}
}
これで*
トークンのleft
に4
トークンを持たせ、right
に5
トークンを持たせれば、4 * 5
の状態を表現できます。
次に3 + (4 * 5)
の状態を表現します。
同じ考え方で、+
トークンのleft
に3
トークンを持たせ、right
に*
トークンを持たせます。
ここで*
トークンは先の説明でleft
とright
に4
と5
のトークンを持っています。
つまり4 * 5
となっています。
まとめると、+
トークンがあって、left
に3
トークン、right
が4 * 5
トークンとなり、3 + (4 * 5)
の状態が表現できました。
話がそれますが、内容の確認用に括弧付きの状態を表すparen()もTokenクラスへ追加しました。
順序付けの仕方
次はこの順序付けの仕方を考えます。
例の式では、3つの演算子が登場します。=
、+
、*
の3つです。
順序の基準になっているのはそれらの演算子です。
構文解析でやりたいことで確認した順序では、*
が1番、+
が2番、=
が3番でした。
ここでこの順序に対して先にくる方の演算子へ、先にくる度合いの数値を割り当てます。
具体的には*
に60
を、+
に50
を、=
に10
を割り当てます。
この度合いを基準に、数値が大きい方から先に括弧付をしていきます。
*
が60
で度合いが1番大きいので、最初に括弧付され、
=
は10
で度合いが1番小さいので、最後に括弧付されることになります。
Javaで実装してみる
実装にうつります。
構文解析を行うクラスを部分的にみていきます。
はじめはトークンの意味に対して、どう動作するかを定義します。
degrees
は演算子順序の度合いを定義します。
factorKinds
はa
トークンや3
トークンなど、式の左右の端にくるトークンのkind
を定義します。
binaryKinds
は=
トークンや+
トークンなど、式の真ん中にくるトークンのkind
を定義します。
rightAssocs
は=
トークンへの順序付けで、特別扱いをする必要があり、そのための定義です。
public class Parser {
private Map<String, Integer> degrees;
private List<String> factorKinds;
private List<String> binaryKinds;
private List<String> rightAssocs;
public Parser() {
degrees = new HashMap<>();
degrees.put("*", 60);
degrees.put("/", 60);
degrees.put("+", 50);
degrees.put("-", 50);
degrees.put("=", 10);
factorKinds = Arrays.asList(new String[] { "digit", "variable" });
binaryKinds = Arrays.asList(new String[] { "sign" });
rightAssocs = Arrays.asList(new String[] { "=" });
}
続いて構文解析を行う前の初期化の部分です。
字句解析で分解されたトークンのリストを受けとります。
このトークンリストへ構文解析をかけます。
解析で終端を処理するのに都合がいいので、トークンリストの末尾へ終端をあらわすeob
トークンを追加します。
またトークンリストを先頭から終端へ順に参照するためのインデックスi
も0にします。
private List<Token> tokens;
private int i;
public Parser init(List<Token> tokens) {
i = 0;
this.tokens = new ArrayList<Token>(tokens);
Token eob = new Token();
eob.kind = "eob";
eob.value = "(eob)";
this.tokens.add(eob);
return this;
}
トークンリストを順に参照する機能です。
token()
はトークンリスト中の現在注目しているトークンです。
next()
は注目していたトークンを返し、注目する位置を次へ進めます。
private Token token() throws Exception {
if (tokens.size() <= i) {
throw new Exception("No more token");
}
return tokens.get(i);
}
private Token next() throws Exception {
Token t = token();
++i;
return t;
}
解析をする部分の説明へ入っていきます。
lead()
はa
や3
など、式の左右の端にこられるトークンであることを解析して、そのトークンを返します。
private Token lead(Token token) throws Exception {
if (factorKinds.contains(token.kind)) {
return token;
} else {
throw new Exception("The token cannot place there.");
}
}
degree()
はトークンの優先順位度合いを返します。
bind()
は演算子トークンへ左右にくるトークンを割り付け、割り付けの済んだ演算子トークンを返します。
private int degree(Token t) {
if (degrees.containsKey(t.value)) {
return degrees.get(t.value);
} else {
return 0;
}
}
private Token bind(Token left, Token operator) throws Exception {
if (binaryKinds.contains(operator.kind)) {
operator.left = left;
int leftDegree = degree(operator);
if (rightAssocs.contains(operator.value)) {
leftDegree -= 1;
}
operator.right = expression(leftDegree);
return operator;
} else {
throw new Exception("The token cannot place there.");
}
}
bind()
について詳しくみていきます。
bind()
は引数に式の左にくるトークンと、式の演算子トークンをとります。
bind()
ではまず、その左にくるトークンを演算子トークンのoperator.left
へ割り付けます。
operator.right
へ割り付けるトークンは、expression()
を呼んだ戻り値を割り付けます。
expression()
がどのようなトークンを返すかを説明しましょう。
expression()
を呼び出すとき引数に、演算子トークンの優先順位度合いを渡します。
渡された度合いはexpression()
の中で、トークンリストで後に続く演算子の度合いと比較されます。
渡された度合が大きいか同じときは、後に続く演算子トークンの前のトークンを、expression()
は返します。
例えば下の式で、bind()
を引数にleft
が6
でoperator
が+
で呼び出したときを考えます。
6 + 7 - 8
expression()
は+
の度合い50
で呼び出され、後にくる-
の度合い50
と比較します。
度合いは同じなので、-
の前にくるトークン7
を返します。
そしてbind()
に戻り7
はoperator.right
へ割り付けられます。
これで6 + 7
に関連付けた+
をbind()
は返します。
度合い比較でleftDegree
が小さい場合は、あとで説明します。
expression()
は演算子の優先順位度合いをつかって、トークンの関連付けを制御します。
先に説明した、lead()
とbind()
をexpression()
が呼び出します。
public Token expression(int leftDegree) throws Exception {
Token left = lead(next());
int rightDegree = degree(token());
while (leftDegree < rightDegree) {
Token operator = next();
left = bind(left, operator);
rightDegree = degree(token());
}
return left;
}
expression()
の動きを幾つかのトークンリストを例にとってみてみましょう。
トークンリストがa
だけの場合
まず初めのexpression()
の呼び出しではleftDegree
は0
で呼び出します。
a
だけの場合、lead()
の呼び出しで、a
が返され、left
がa
で決まりす。
次のdegree()
では終端しやすいように追加した(eob)
の度合いが返されrightDegree
は0
です。
leftDegree
が0
、rightDegree
が0
でwhile
が成立せず、left
のa
がそのまま返されます。
つまりa
だけのトークンリストが解析できました。
トークンリストがa = 3
の場合
a = 3
の場合も、lead()
の呼び出しで、a
が返され、left
がa
で決まります。
次のdegree()
では=
の度合いが返されrightDegree
は10
です。
先の場合と同じでexpression()
は、leftDegree
が0
で呼び出されていてwhile
が成立します。
するとbind()
をa
と=
を引数に呼び出します。
bind()
で説明したように、bind()
では式の右側のトークンを解析するために、expression()
を呼び出します。
bind()
でexpression()
を呼び出すときは、a =
まで解析できているので、トークンリストに残るトークンは、3
のみです。
これは先に説明した、「トークンリストがa
だけの場合」と同じ状況です。
つまりbind()
で呼び出したexpression()
は3
を返し、operator.right
は3
で決まります。
bind()
は呼び出し元のexpression()
へ=
を返し、
呼び出し元のexpression()
のleft
は=
で決まります。
bind()
呼び出しの次の行のdegree()
は(eob)
の度合い0
を返すので、while
を抜けます。
これで=
に決まったleft
をexpression()
が返し、解析ができました。
またこの説明は、あとで説明するとしていた度合い比較でleftDegree
が小さい場合の説明にもなっています。
解析をする部分の最後の説明です。
block()
はトークンリストが(eob)
になるまで、expression()
を呼び出し、その解析結果をリストへ追加します。
トークンリストにある式の数だけ、blk
に解析結果が追加されます。
public List<Token> block() throws Exception {
List<Token> blk = new ArrayList<Token>();
while (!token().kind.equals("eob")) {
blk.add(expression(0));
}
return blk;
}
以上の実装を使って、例のプログラムになっている文字列
a = 3 + 4 * 5
を構文解析し、標準出力へプリントします。
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
for (Token ast : blk) {
System.out.println(ast.paren());
}
// --> (a = (3 + (4 * 5)))
}
}
実装は以上です。
ありがとうございました。
おわりに
ソースはこちらで公開しています。
Calc
https://github.com/quwahara/Calc/tree/article-2-parser/Calc/src/main/java
続きの記事があります。
単純なインタプリタをJavaで実装する
http://qiita.com/quwahara/items/30e93dfd2690913d66c0
最後に、Parserクラスをまとめたものもあげておきます。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Parser {
private Map<String, Integer> degrees;
private List<String> factorKinds;
private List<String> binaryKinds;
private List<String> rightAssocs;
public Parser() {
degrees = new HashMap<>();
degrees.put("*", 60);
degrees.put("/", 60);
degrees.put("+", 50);
degrees.put("-", 50);
degrees.put("=", 10);
factorKinds = Arrays.asList(new String[] { "digit", "variable" });
binaryKinds = Arrays.asList(new String[] { "sign" });
rightAssocs = Arrays.asList(new String[] { "=" });
}
private List<Token> tokens;
private int i;
public Parser init(List<Token> tokens) {
i = 0;
this.tokens = new ArrayList<Token>(tokens);
Token eob = new Token();
eob.kind = "eob";
eob.value = "(eob)";
this.tokens.add(eob);
return this;
}
private Token token() throws Exception {
if (tokens.size() <= i) {
throw new Exception("No more token");
}
return tokens.get(i);
}
private Token next() throws Exception {
Token t = token();
++i;
return t;
}
private Token lead(Token token) throws Exception {
if (factorKinds.contains(token.kind)) {
return token;
} else {
throw new Exception("The token cannot place there.");
}
}
private int degree(Token t) {
if (degrees.containsKey(t.value)) {
return degrees.get(t.value);
} else {
return 0;
}
}
private Token bind(Token left, Token operator) throws Exception {
if (binaryKinds.contains(operator.kind)) {
operator.left = left;
int leftDegree = degree(operator);
if (rightAssocs.contains(operator.value)) {
leftDegree -= 1;
}
operator.right = expression(leftDegree);
return operator;
} else {
throw new Exception("The token cannot place there.");
}
}
public Token expression(int leftDegree) throws Exception {
Token left = lead(next());
int rightDegree = degree(token());
while (leftDegree < rightDegree) {
Token operator = next();
left = bind(left, operator);
rightDegree = degree(token());
}
return left;
}
public List<Token> block() throws Exception {
List<Token> blk = new ArrayList<Token>();
while (!token().kind.equals("eob")) {
blk.add(expression(0));
}
return blk;
}
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
for (Token ast : blk) {
System.out.println(ast.paren());
}
// --> (a = (3 + (4 * 5)))
}
}