JavaでBasicライク言語のインタプリタ実装 #1 字句解析編
これから書く記事の概要
実践的プログラミング
弊学では３年次にJavaでBasicライク言語のインタプリタを実装する、「実践的プログラミング」という講義があります。
弊研のボスがやっている、プログラミング力を一気に上げる講義です。 弊研究室に所属した場合、この講義の単位の修得が要求されます。
よく単位とれないと進級できないとかいう嘘を流してる人が居ますが、あれは嘘です。 履修も絶対しなきゃいけないわけじゃないです。 進級条件にかかってない適当な枠の講義をの単位をネタにそれで進級させないとかして、ゴネたら面倒になるでしょ。 過去に単位取らずに卒業した人も居ます。
ただ、別に面倒なわけじゃないし＆プログラム将来書くなら役に立つこと間違いなしの講義なので、積極的に受けないって方針は採らなくていいと思います。
講義の扱い的には、「実質強制参加の会社の忘年会」的な扱いだと思って下さい。 わたしはまだ忘年会未経験なので本当に合ってるかはわかりませんけど。
この講義、なんか毎度よくわからんと言い始める人がいっぱい居ます。 今年も研究室で騒いでいる人がいっぱい居るので、ほら簡単やろ？って証明するために去年私が作ったコードをひたすら載せつつ、解説します。
成果物
最終的にこんなのが作れますよ。
PRINT "x^2 -8x -16"
a = 1
b = -8
c = -16
def = SQRT((b * b) - (4 * a * c))
res1 = ( -b - def) / 2 * a
res2 = ( -b + def) / 2 * a
PRINT "x = (" + res1 + "," + res2 + ")"
Syntax parsed --- PRINT[x^2 -8x -16];a[1];b[SUB[8]];c[SUB[16]];def[SQRT[SUB[MUL[b,b],MUL[MUL[4,a],c]]]];res1[MUL[DIV[SUB[SUB[b],def],2],a]];res2[MUL[DIV[ADD[SUB[b],def],2],a]];PRINT[ADD[ADD[ADD[ADD[x = (,res1],,],res2],)]] ----------------- -------run!------ x^2 -8x -16 x = (-1.6568542494923806,9.65685424949238)
連載目次
１日で全部書くと長くなるので何日かに分けて書いて公開していこうと思います。
講義の流れとして 字句解析＝＞構文解析＝＞実行系 という形でプログラムを作っていくので、それに添った形で書いていきます。
というスケジュールで行きます。 書きためしてコミケ中のネタ用に数日増やすかもしれません。
さて書いていきます。 今日は講義攻略のおすすめ方針と、第一回のレポートのネタになる字句解析部分のプログラム解説をします。
講義攻略方針
この講義の難易度は、３年次に並行して走ってる kmd先生の「形式言語とオートマトン」 という講義を取ったかどうかで天と地の差が生まれます。 基本的にプログラミング言語の構成を知っていればインタプリタの作り方は分かるので、コンパイラの作り方を説明するkmd先生の講義を取り概略をつかめば何をすれば良いか全部分かります。
この講義を取るか、コンパイラの作り方を一度どっかで勉強したことがあれば特に困ることはありません。
逆にしていないとよくわからなくなります。 ボスの説明を頑張って聞いて作りましょう。
字句解析
字句解析とは
字句解析とは素のプログラムを読み込んで、書かれている単語のまとまりを作り、１つ１つにどういう意味があるのか判明させる処理です。
具体的には、
a = 1
という素のプログラムから a , = , 1 と分割し、それぞれa(変数名)、=(演算子 Equal)、1(値,整数, 1) というように意味をラベル付けしていきます。
要求される動作
レポートではこれを満たす必要があります。
以下の入力を受け取り
a = 50.1 DO UNTIL a < 1 PRINT "Hello" a = a - 10 LOOP END
以下の出力を行うこと
NAME: a EQ DOUBLEVAL: 50.1 NL DO UNTIL NAME: a LT INTVAL: 1 NL NAME: PRINT LITERAL: Hello NL NAME: a EQ NAME: a SUB INTVAL: 10 NL LOOP NL END EOF
字句解析部分の攻略方
kmd先生の講義を取っていれば、字句解析は正規表現と深い関わりがあり、(普通の)正規表現は有限オートマトンで処理できるーということを知ることが出来ます。 取ってない人も今知りましたね？
字句はすべて正規表現で表現が可能です。
- WORD(a, DO, WHILE, END) =>
^[a-zA-Z]\\w* - LITERAL("hogehgoe") =>
^\"[^\"]*\"? - NUMBER (4423, 4.2) =>
[0-9.]+ - 一字のOPERATER( =, + , - +=) =>
[\\.\n\\+\\-\\*\\/\\)\\(,]
こんな感じですね。(全部は網羅してません＆複数の字句がマッチする場合あり）
読み込んだプログラムをの状態遷移図を作成し、最適化を施し、その状態遷移を実現するようにJavaのコードを書けば字句判定が完成します。 これがお作法っぽい作り方です。
ただし、状態遷移図からJavaのコードをIFやループを使って生み出すと面倒なので、 字句を正規表現で表した後、Javaの標準ライブラリに正規表現処理をさせてやればいいです。
ここで正規表現処理エンジンを作らせたるよう強制しないのがボスの優しさですね。 正規表現エンジンも作ったりした方が良いと思うんだけどなぁ。
アルゴリズム
１つの字句は以下の手順で得られる.
- 字句の始まりとなり得る文字(英数字, 記号, 改行文字) を得る
- その文字が, 変数or 予約語, 数字, リテラル, 演算子のどれに該当するのか判断する
- 対応する種別に応じて字句に許容されない文字が現れるまでソースを読み, 初めの字から許容されない 文字が現れるまでの文字をつなげた物を１字句の内容とする
- 得られた文字列に対して実際にどのような字句なのか, 予約語なのか, どの演算子なのか等をより細かく 見て字句を確定し出力する
ソースコードを読みこみながら、上記手順を繰り返すことでソースコードから字句を１つずつ取り出すことが出来ます。
コードの書きやすさ的には、これを実装に移すのが一番さっくりいくと思います。 実装にJava力をちょっと必要としますが。。。。
実装
すべての実装は
にあります。lexical_parserパッケージ及びcoreパッケージが字句解析に関連した部分です。
メインエントリポイント
public class Main { public static void main(String[] args) throws Exception { LexicalAnalyzer analyzer = new LexicalAnalyzerImpl("test1.bas"); LexicalUnit unit; for (unit = analyzer.get(); unit.type != LexicalType.EOF; unit = analyzer.get()) { System.out.println(unit); } System.out.println(unit); } }
字句を切り出しLexicalUnit作る処理部分
アルゴリズムに基づいてまず大まかに分けるようにします。 ここを正規表現でやるのがコード簡略化のこつです。
public enum TokenType { NUMBER("[0-9.]+"), // 0-9から始まりdotを含んで連続する(笑) WORD("^[a-zA-Z]\\w*"), // A-Za-zから始まって単語構成文字が連続する LITERAL("^\"[^\"]*\"?"), // "から始まりε "があったらそれでおしまい.（エスケープシーケンス） SINGLE_OPERATOR("[\\.\n\\+\\-\\*\\/\\)\\(,]"), // １文字で構成される字句 MULTY_OPERATOR("[><=]|=[><]|[><]=|<>"); // 複数文字で構成されうる演算子 > < = => >= =< // <= <> private final Pattern pattern; private TokenType(String regx) { this.pattern = Pattern.compile(regx); } public boolean isMatch(String test) { return pattern.matcher(test).matches(); } }
定義的に正規表現を埋め込んだこのEnumを使って、一気に処理します。
下のクラスは ソースコード（テキスト）を１文字ずつよんで、なんか意味ある始めの一字（EOFやスペースではなく次のTokenを構成する１字） まで読み、上のEnumのマッチを使ってどれか確定させ、tokenにします。
/** * Streamを読んでTokenに切り出すクラス. * テキストデータを１文字ずつよんでTokenに分割 */ public class TokenParser { /** * テキストデータ読み込みReader */ private Reader reader; private boolean readerIsEOF = false; public TokenParser(Reader reader) { super(); this.reader = reader; } /** * 字句確定のためにreadしちゃった次の字句を持っておく */ private String nextTokenBuff = ""; /** * 次のTokenを得ます. */ public Token get() { if (readerIsEOF == true) { return null; } // EOFやスペースではなく次のTokenを構成する１字を得る String tokenFirstStr = normalizeStr(nextTokenBuff); if (!readerIsEOF && tokenFirstStr.isEmpty()) { tokenFirstStr += readNextStr(); } // トークン始まりの字にマッチするtokenTypeを得る TokenType tokenType = getMatchTokenType(tokenFirstStr); // マッチが外れ、違う字句になるまで読みTokenの値を得る String tokenVal = tokenFirstStr; while (!readerIsEOF && tokenType.isMatch(tokenVal)) { tokenVal += readNext(); } // マッチ外れたときに入ったアルファベットは次の字句の可能性ありありなので保持 // cf. a= はa=のときにマッチが外れるが=はそれ自体次の字句 this.nextTokenBuff = String.valueOf(tokenVal.charAt(tokenVal.length() - 1)); // 出力するトークンからは次の字句の文字は消す tokenVal = tokenVal.substring(0, tokenVal.length() - 1); return new Token(tokenType, tokenVal); } /** * TokenTypeからTokenTypeのパラメータに一致するやつ探し出す. * <始めの１字がどのトークンタイプか判別する.> * @param tokenFirstStr Tokenの初めの１字 */ private TokenType getMatchTokenType(String tokenFirstStr) { Optional<TokenType> tokenTypeOpt = EnumSet.allOf(TokenType.class) .stream() .filter(t -> t.isMatch(tokenFirstStr)) .findFirst(); return tokenTypeOpt.get(); } /** * 文字を標準化 * CRをスペースに （LFだけにする） * タブはスペースに * 最後にスペースは消し去ります */ private String normalizeStr(String str) { return str .replaceAll("\t", " ") .replace('\r', ' ') .replaceAll(" ", ""); } /** * 次の"字"を１つ読み返すよ * (スペースとかは無視されるよ) */ private String readNextStr() { String tmp = ""; while (tmp.isEmpty() && !readerIsEOF) { char c = readNext(); tmp += c; tmp = normalizeStr(tmp); } return tmp; } /** * ストリームから１"文字"読みます. (スペースとかが返ってくるよ） * もしEOFだったらisEOFをtrueにして0を返します... */ private char readNext() { if (this.readerIsEOF == true) { return 0; } int ci = 0; try { ci = reader.read(); } catch (IOException ex) { ex.printStackTrace(); } // EOF if (ci == -1) { this.readerIsEOF = true; try { reader.close(); } catch (IOException ex) { ex.printStackTrace(); } return 0; } return (char) ci; } }
これで１字句分がTokenインスタンスとして切り出せます。 EnumのSetに対してストリームAPIを利用し一気にマッチ処理をさせるのがポイントです。
とれたTokenクラスは
/** * Token * ソースコードから切り出したトークン * * SorceCode -> Token -> LexcalUnit * @author namaz * */ public class Token { private TokenType type; private String value; Token(TokenType type, String value) { this.type = type; this.value = value; } public TokenType getType() { return type; } public String getValue() { return value; } /** * このトークンをタイプに応じて解析し, * より詳しく細分化されたLexicalUnitへ変換します. */ public LexicalUnit parseLexicalUnit() { // それぞれのトークン種別に応じて解析. LexicalUnit res = null; switch (type) { case NUMBER: res = parseNumberToken(); break; case WORD: res = parseWordToken(); break; case LITERAL: res = parseLiteralToken(); break; case SINGLE_OPERATOR: case MULTY_OPERATOR: res = parseOperatorToken(); break; } return res; } private LexicalUnit parseWordToken() { // 予約語の抽出. Optional<ReservedWord> reservedWordOpt = EnumSet.allOf(ReservedWord.class) .stream() .filter(t -> t.isMatch(value)) .findFirst(); if (reservedWordOpt.isPresent()) { // 予約語とマッチした. LexicalType type = reservedWordOpt.get().getType(); return new LexicalUnit(type); } // 予約語とマッチしない 単語 -> 変数. return new LexicalUnit(LexicalType.NAME, new ValueImpl(value)); } private LexicalUnit parseNumberToken() { // Double if (value.contains(".")) { return new LexicalUnit(LexicalType.DOUBLEVAL, new ValueImpl(value)); } // Intval return new LexicalUnit(LexicalType.INTVAL, new ValueImpl(value)); // TODO: もっと精巧な.とかの処理. 指数部とか + - とかの符号もね } private LexicalUnit parseLiteralToken() { // ”を消す String literalVal = value.replaceAll("\"", ""); return new LexicalUnit(LexicalType.LITERAL, new ValueImpl(literalVal)); } private LexicalUnit parseOperatorToken() { // オペレーター種別の識別. Optional<Operator> operatorOpt = EnumSet.allOf(Operator.class) .stream() .filter(t -> t.isMatch(value)) .findFirst(); if (operatorOpt.isPresent()) { // 値に該当するオペレーターが存在した LexicalType type = operatorOpt.get().getType(); return new LexicalUnit(type); } // 該当しないはずがない return null; } }
こんな感じで、より詳細に調べてLexicalUnitを作ります。
LexicalAnalyzerImpl
こうしてToken => LexicalUnitとすることで, ボスが渡してくるLexicalAnalyerImplは
public class LexicalAnalyzerImpl implements LexicalAnalyzer { private TokenParser tokenParser; public LexicalAnalyzerImpl(String filePath) throws Exception { tokenParser = new TokenParser(new FileReader(filePath)); } @Override public LexicalUnit get() { Token nextToken = tokenParser.get(); // TokenをLexicalUnitへ if (nextToken == null) { // nullが返ってきたらEOF return new LexicalUnit(LexicalType.EOF); } return nextToken.parseLexicalUnit(); } }
こんな風に書けます。
予約語とか演算子のLexicalTypeとの関連付け判定
文字から予約語や、記号からどの記号のLexicalTypeになるか？とかいう部分については 下のように、全ての演算子を網羅したEnumを用意しておき。。。
/** * すべての演算子の列挙 及びLexcalTypeとの関連付け * 一時決まりの字句とかもここだよ. */ public enum Operator { EQ(LexicalType.EQ, "="), LT(LexicalType.LT, "<"), GT(LexicalType.GT, ">"), LE(LexicalType.LE, "<=", "=<"), GE(LexicalType.GE, ">=", "=>"), NE(LexicalType.NE, "<>"), ADD(LexicalType.ADD, "+"), SUB(LexicalType.SUB, "-"), MUL(LexicalType.MUL, "*"), DIV(LexicalType.DIV, "/"), LP(LexicalType.LP, ")"), RP(LexicalType.RP, "("), COMMA(LexicalType.COMMA, ","), NL(LexicalType.NL, "\n"), DOT(LexicalType.DOT, "."); private final String[] vals; private final LexicalType type; private Operator(LexicalType type, String... vals) { // >= => とかが同じ意味なので配列にしときます. this.vals = vals; this.type = type; } /** * 与えられた文字列と字句の決まり字が一致するかどうか */ public boolean isMatch(String test) { for (String string : vals) { if (string.equals(test)) { return true; } } return false; } public LexicalType getType() { return type; } }
この全ての定義を見て、確定させる処理を
// オペレーター種別の識別. Optional<Operator> operatorOpt = EnumSet.allOf(Operator.class) .stream() .filter(t -> t.isMatch(”Tokenの文字”)) .findFirst(); if (operatorOpt.isPresent()) { // 値に該当するオペレーターが存在した LexicalType type = operatorOpt.get().getType(); return new LexicalUnit(type); }
こんな感じで一気に行うのが楽しい。 全部Mapに突っ込んで引くという方法もあるけどね。
valueimpl
これを作れーってボスが言いますが まぁ
public class ValueImpl implements Value { private ValueType type; // 全部stringで持っとけ・・・ private String val; public ValueImpl(String s) { type = ValueType.STRING; val = s; } public ValueImpl(int i) { type = ValueType.INTEGER; val = i + ""; } public ValueImpl(double d) { type = ValueType.DOUBLE; val = d + ""; } public ValueImpl(boolean b) { type = ValueType.BOOL; val = b + ""; } @Override public String getSValue() { return val; } @Override public int getIValue() { return Integer.parseInt(val); } @Override public double getDValue() { return Double.parseDouble(val); } @Override public boolean getBValue() { return Boolean.parseBoolean(val); } @Override public ValueType getType() { return type; } }
こんなんで良いでしょう。 値はString形式で常に持っておくとわざわざ面倒な処理を書かなくてもいい。
字句解析まとめ
字句の正規表現が考えられさえすれば、あとはいろいろな方法でコードにできるでしょう。 何も難しいことなし。
一年経った今になって考えると、もっとざばっと単純明快に処理する方法を思いついていて、あーーーってなりながら今日書きました。 LexicalTypeってEnumを渡されるので、そこに手を入れて、すべて正規表現を書き、他の字句と一致した場合の優先度とかも書けば、LexicalTypeを一回見るだけで特定が可能じゃんって。。。 無駄に２段階挟んだりしてやらなくてもよかった。
明日
明日は、絶賛レポート締め切りが近いらしい、構文解析部分の実装を書いていこうと思います。 一気に構文解析部分を書くのは辛いので、式部分以外を明日は書こうかな。 それでは。
