はじめに
コンパイラ実装の処理過程に字句解析があります。
その字句解析のごくごく原始的なものをJavaで実装してみたいとおもいます。
去る2017年1月28日に開催されたコンパイラ勉強会に刺激をうけて書きました。
当の勉強会の発表内容の高度さには遠く及ばずそのような知識もありませんが、
コンパイラ実装のHello, World!的な記事もあったら楽しいかもとおもい書きました。
字句解析でやりたいこと
実装にあたり、まずはやりたいことを確認しましょう。
字句解析はプログラムになっている文字列を、字句またはトークンとよばれるものへ分解します。
例を見ながら説明します。
足し算の結果を変数へ代入する、プログラムになっている文字列があります。
ans1 = 10 + 20
この文字列をans1と=、10、+、20の５つへ分解するのが、字句解析の目的です。
分解した文字列は字句あるいはトークンと呼びます。
またこの５つのトークンは、それぞれ意味のある単位になっています。
意味は直感的に分かるとおもいますが、ans1が変数、=と+は演算子、10と20は数字です。
トークンにそのような意味付けをするのも字句解析の目的です。
実装では「文字列がans1で意味が変数」、「文字列が=で意味が演算子」というように、
文字列と意味をひとまとめにした方が便利です。
そのため実装では文字列と意味をまとめてトークンのオブジェクトにします。
もう一度字句解析でやりたいことをまとめると、
「プログラムになっている文字列を、文字列と意味を表すトークンへ分解したい」となります。
分解の仕方
やりたいことが分かったので、どうやるかを考えます。
分解をするにはトークンに制約を付けてそれを利用します。
その制約はこうです。
- トークンの1文字目を見れば、そのトークンの意味が決まる
- トークンの意味が決まる1文字目は、意味によってそれぞれ別々になっていて重複がない
変数名、演算子、数字についてこの制約を考えてみます。
1文字目の制約を決めます。
- 変数名の1文字目は、アルファベット
- 演算子の1文字目は、
=または+ - 数字の1文字目は
0から9の数字
そして1文字目に重複がないことの制約もみたせています。
ではこの制約を利用して、トークンへ分解します。
先ほどの例をまたみてみます。
ans1 = 10 + 20
例のプログラムになっている文字列を左から順に1文字ずつなぞっていきます。
a→n→s→1・・・と順になぞり、最後の0までです。
ここで最初のaをなぞったとき、aはアルファベットなので、
制約からaは変数名の1文字目だと決まります。
変数名ときまったので、それに続くn→s→1も変数名の文字列のつらなりとして順になぞっていきます。
1の後ろの文字は、変数名の一部とはならないので、そこまでが変数名にあたる文字列としてトークンに分解できます。
続けてなぞっていきます。
=の前の空白は、どのトークンにも関わらないので、単純にとばします。
そして=に出会います。これも制約から演算子と決まり、演算子トークンが分解できます。
分解の仕方をまとめると、トークンの制約を作り、プログラムになっている文字列をなぞって、1文字目の制約にあう意味のトークンへ、順番に最後まで分解していきます。
Javaで実装してみる
実装にうつります。
まずはトークンを表すクラスです。
クラスのフィールド変数は、意味を表すkindと文字列を保持するvalueの２つです。
字句解析を行うクラスで、プログラムになっている文字列からこのTokenへ分解していきます。
内容の確認用にtoString()を実装しました。
public class Token {
public String kind;
public String value;
@Override
public String toString() {
return kind + " \"" + value + "\"";
}
}
字句解析を行うクラスをみていきます。
部分的にみていきましょう。
処理のはじめの部分です。
プログラムになっている文字列を保持する、textフィールドがあります。
そしてその文字列をなぞっていくためのインデックスになるiフィールドがあります。
initメソッドでそれらを初期化します。
import java.util.ArrayList;
import java.util.List;
public class Lexer {
private String text;
private int i;
public Lexer init(String text) {
i = 0;
this.text = text;
return this;
}
文字列をなぞっていく仕組みの部分です。
isEOTはなぞる文字がこれ以上ないことを表します。
c()はプログラムになっている文字列で、なぞっている途中の注目している位置にある文字です。
next()は注目していた文字を返し、注目する位置を次へ進めます。
private boolean isEOT() {
return text.length() <= i;
}
private char c() throws Exception {
if (isEOT()) {
throw new Exception("No more character");
}
return text.charAt(i);
}
private char next() throws Exception {
char c = c();
++i;
return c;
}
文字列をなぞっていく仕組みを利用する部分を順に説明します。
skipSpace()はスペースなどトークンと関係ない文字を読みとばします。
プログラムになっている文字列の先頭や末尾、式の途中にスペースが何文字入っていても、これでOKです。
private void skipSpace() throws Exception {
while (!isEOT() && Character.isWhitespace(c())) {
next();
}
}
1文字目の制約を判定する部分です。
順に、演算子、数字、変数名の1文字目かを判定します。
private boolean isSignStart(char c) {
return c == '=' || c == '+' || c == '-' || c == '*' || c == '/';
}
private boolean isDigitStart(char c) throws Exception {
return Character.isDigit(c);
}
private boolean isVariableStart(char c) throws Exception {
return Character.isAlphabetic(c);
}
トークンへ分解する部分です。
順に、演算子、数字、変数名のトークンへ分解します。
プログラムになっている文字列の、注目する位置iはnext()によって、
トークンへ分解できたぶんだけ進められます。
private Token sign() throws Exception {
Token t = new Token();
t.kind = "sign";
t.value = Character.toString(next());
return t;
}
private Token digit() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && Character.isDigit(c())) {
b.append(next());
}
Token t = new Token();
t.kind = "digit";
t.value = b.toString();
return t;
}
private Token variable() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && (Character.isAlphabetic(c()) || Character.isDigit(c()))) {
b.append(next());
}
Token t = new Token();
t.kind = "variable";
t.value = b.toString();
return t;
}
以上の1文字目の制約を判定する部分と、トークンへ分解する部分を使って、
注目している位置から、最初に見つかったトークンを返します。
まずスペースが読みとばされ、
注目している位置にある文字によってトークンが決まり、トークンへ分解されます。
public Token nextToken() throws Exception {
skipSpace();
if (isEOT()) {
return null;
} else if (isSignStart(c())) {
return sign();
} else if (isDigitStart(c())) {
return digit();
} else if (isVariableStart(c())) {
return variable();
} else {
throw new Exception("Not a character for tokens");
}
}
前述のnextToken()を使って、プログラムになっている文字列を、すべてTokenへ分解します。
public List<Token> tokenize() throws Exception {
List<Token> tokens = new ArrayList<>();
Token t = nextToken();
while (t != null) {
tokens.add(t);
t = nextToken();
}
return tokens;
}
以上の実装を使って、例のプログラムになっている文字列
ans1 = 10 + 20
を字句解析し、標準出力へプリントします。
public static void main(String[] args) throws Exception {
String text = " ans1 = 10 + 20 ";
List<Token> tokens = new Lexer().init(text).tokenize();
for (Token token : tokens) {
System.out.println(token.toString());
}
// --> variable "ans1"
// --> sign "="
// --> digit "10"
// --> sign "+"
// --> digit "20"
}
}
実装は以上です。
ありがとうございました。
おわりに
ソースはこちらで公開しています。
Calc
https://github.com/quwahara/Calc/tree/lexer/Calc/src/main/java
続きの記事があります。
単純な構文解析をJavaで実装する
http://qiita.com/quwahara/items/9bf468ff4286b28d2a24
念のため、class Lexerをまとめたものもあげておきます。
import java.util.ArrayList;
import java.util.List;
public class Lexer {
private String text;
private int i;
public Lexer init(String text) {
i = 0;
this.text = text;
return this;
}
private boolean isEOT() {
return text.length() <= i;
}
private char c() throws Exception {
if (isEOT()) {
throw new Exception("No more character");
}
return text.charAt(i);
}
private char next() throws Exception {
char c = c();
++i;
return c;
}
private void skipSpace() throws Exception {
while (!isEOT() && Character.isWhitespace(c())) {
next();
}
}
private boolean isSignStart(char c) {
return c == '=' || c == '+' || c == '-' || c == '*' || c == '/';
}
private boolean isDigitStart(char c) throws Exception {
return Character.isDigit(c);
}
private boolean isVariableStart(char c) throws Exception {
return Character.isAlphabetic(c);
}
private Token sign() throws Exception {
Token t = new Token();
t.kind = "sign";
t.value = Character.toString(next());
return t;
}
private Token digit() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && Character.isDigit(c())) {
b.append(next());
}
Token t = new Token();
t.kind = "digit";
t.value = b.toString();
return t;
}
private Token variable() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && (Character.isAlphabetic(c()) || Character.isDigit(c()))) {
b.append(next());
}
Token t = new Token();
t.kind = "variable";
t.value = b.toString();
return t;
}
public Token nextToken() throws Exception {
skipSpace();
if (isEOT()) {
return null;
} else if (isSignStart(c())) {
return sign();
} else if (isDigitStart(c())) {
return digit();
} else if (isVariableStart(c())) {
return variable();
} else {
throw new Exception("Not a character for tokens");
}
}
public List<Token> tokenize() throws Exception {
List<Token> tokens = new ArrayList<>();
Token t = nextToken();
while (t != null) {
tokens.add(t);
t = nextToken();
}
return tokens;
}
public static void main(String[] args) throws Exception {
String text = " ans1 = 10 + 20 ";
List<Token> tokens = new Lexer().init(text).tokenize();
for (Token token : tokens) {
System.out.println(token.toString());
}
// --> variable ,"ans1"
// --> sign "="
// --> digit "10"
// --> sign "+"
// --> digit "20"
}
}