![03 字句解析器(Lexer) の実装完了 [オリジナル言語インタプリタを作る]](https://webbibouroku.com/wp-content/uploads/eye_gorilla.png)
字句解析器の実装続き
続けて新たなテストを作成し、プログラムのソースコードに似た入力からトークン列を得られるようにしていきましょう。テストする入力データは以下の通り。
let five = 5;
let ten = 10;
let add = fn(x, y) {
x + y;
};
let result = add(five, ten);
早速テストコードを書きます。
LexerTest.cs
[TestMethod]
public void TestNextToken2()
{
var input = @"let five = 5;
let ten = 10;
let add = fn(x, y) {
x + y;
};
let result = add(five, ten);";
var testTokens = new List<Token>();
// let five = 5;
testTokens.Add(new Token(TokenType.LET, "let"));
testTokens.Add(new Token(TokenType.IDENT, "five"));
testTokens.Add(new Token(TokenType.ASSIGN, "="));
testTokens.Add(new Token(TokenType.INT, "5"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
// let ten = 5;
testTokens.Add(new Token(TokenType.LET, "let"));
testTokens.Add(new Token(TokenType.IDENT, "ten"));
testTokens.Add(new Token(TokenType.ASSIGN, "="));
testTokens.Add(new Token(TokenType.INT, "10"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
// let add = fn(x, y) { x + y; };
testTokens.Add(new Token(TokenType.LET, "let"));
testTokens.Add(new Token(TokenType.IDENT, "add"));
testTokens.Add(new Token(TokenType.ASSIGN, "="));
testTokens.Add(new Token(TokenType.FUNCTION, "fn"));
testTokens.Add(new Token(TokenType.LPAREN, "("));
testTokens.Add(new Token(TokenType.IDENT, "x"));
testTokens.Add(new Token(TokenType.COMMA, ","));
testTokens.Add(new Token(TokenType.IDENT, "y"));
testTokens.Add(new Token(TokenType.RPAREN, ")"));
testTokens.Add(new Token(TokenType.LBRACE, "{"));
testTokens.Add(new Token(TokenType.IDENT, "x"));
testTokens.Add(new Token(TokenType.PLUS, "+"));
testTokens.Add(new Token(TokenType.IDENT, "y"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
testTokens.Add(new Token(TokenType.RBRACE, "}"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
// let result = add(five, ten);
testTokens.Add(new Token(TokenType.LET, "let"));
testTokens.Add(new Token(TokenType.IDENT, "result"));
testTokens.Add(new Token(TokenType.ASSIGN, "="));
testTokens.Add(new Token(TokenType.IDENT, "add"));
testTokens.Add(new Token(TokenType.LPAREN, "("));
testTokens.Add(new Token(TokenType.IDENT, "five"));
testTokens.Add(new Token(TokenType.COMMA, ","));
testTokens.Add(new Token(TokenType.IDENT, "ten"));
testTokens.Add(new Token(TokenType.RPAREN, ")"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
testTokens.Add(new Token(TokenType.EOF, ""));
var lexer = new Lexer(input);
foreach (var testToken in testTokens)
{
var token = lexer.NextToken();
Assert.AreEqual(testToken.Type, token.Type, "トークンの種類が間違っています。");
Assert.AreEqual(testToken.Literal, token.Literal, "トークンのリテラルが間違っています。");
}
}
当然まだ識別子等をトークンにする処理を実装していないのでテストはエラーです。このテストを通せるように処理を追加します。
識別子とキーワード
Switch文にdefault分岐を追加し、ここに来た文字はすべて識別子候補としてチェックします。識別子に該当する文字かどうかをチェックして、そうであれば識別子に対応する文字数分すべて読み取ります。
この時、何文字目までが識別子に対応するのかを判定するために先読みする必要があります。
また、識別子よりもキーワードが優先されます。例えば x は識別子ですが、 let は識別子ではなく、キーワード(予約語)としてトークンにしなければなりません。
したがって、得られた識別子をチェックして予約語であれば対応する種類のトークンとして処理します。
Lexing/Lexer.cs
public Token NextToken()
{
Token token = null;
switch (this.CurrentChar)
{
// ..
default:
if (this.IsLetter(this.CurrentChar))
{
var identifier = this.ReadIdentifier();
var type = Token.LookupIdentifier(identifier);
token = new Token(type, identifier);
}
else
{
token = new Token(TokenType.ILLEGAL, this.CurrentChar.ToString());
}
break;
}
this.ReadChar();
return token;
}
なお、すべてのどの種類にも一致しないものは不正なトークンとして処理します。これでNULL参照のエラーにはならなくなります。
では、ReadIdentifier() の実装です。これは現在の文字から識別子に対応した文字である限り読み進め、識別子に対応した文字列を返します。
public class Lexer
{
// ..
private string ReadIdentifier()
{
var identifier = this.CurrentChar.ToString();
// 次の文字が Letter であればそれを読んで加える
while (this.IsLetter(this.NextChar))
{
identifier += this.NextChar;
this.ReadChar();
}
return identifier;
}
private bool IsLetter(char c)
{
return ('a' <= c && c <= 'z')
|| ('A' <= c && c <= 'Z')
|| c == '_';
}
}
ReadIdentifier() が呼ばれる時点でチェック済のため、現在の文字1文字は必ず識別子になる文字です。したがって、その文字プラス何文字分かで識別子となります。ループで次の文字が識別子に対応する文字化をチェックし、対応文字であれば末尾に追加して、ReadChar() を呼び出して読み進めます。
識別子は、”_” もしくは “a”～”Z”のいずれかからなる文字列です。数字は含みません。判定用の処理を別メソッドで定義しています。
ReadIdentifier() が呼び出されると、識別子に対応する文字列を返します。この時、Lexerは、識別子末尾の文字まで読み進めた状態になります。Switch文後の ReadChar() でちょうど識別子の次の文字からちょうど読むようになります。
識別子として取得した文字列は、別途キーワード(予約語)に該当するかどうかをチェックしなければなりません。LookupIdentifier() は文字列を引数にとり、それがキーワードかどうかを判定し、キーワードであれば該当するTokenTypeを返します。キーワードでない場合は識別子のTokenTypeを返します。
Lexing/Token.cs
public class Token
{
// ..
public static TokenType LookupIdentifier(string identifier)
{
if (Token.Keywords.ContainsKey(identifier))
{
return Keywords[identifier];
}
return TokenType.IDENT;
}
public static Dictionary<string, TokenType> Keywords
= new Dictionary<string, TokenType>() {
{ "let", TokenType.LET },
{ "fn", TokenType.FUNCTION },
};
}
static な Dictionary<string, TokenType> でキーワードを管理しています。キーワードを拡張する場合はこの辞書に項目を追加します。LookupIdentifier() も static で定義しておきます。
これで識別子とキーワードがうまく処理できるようになりました。
数値リテラル
次に数値リテラルをうまくトークンにする方法を考えます。基本は識別子と同じ考えです。
識別子でない場合に、数字かどうかを判定します。数字であれば数字をすべて続けて読みんで数値のリテラル文字列を取得します。
public Token NextToken()
{
Token token = null;
switch (this.CurrentChar)
{
// ..
default:
if (this.IsLetter(this.CurrentChar))
{
var identifier = this.ReadIdentifier();
var type = Token.LookupIdentifier(identifier);
token = new Token(type, identifier);
}
else if (this.IsDigit(this.CurrentChar))
{
var number = this.ReadNumber();
token = new Token(TokenType.INT, number);
}
else
{
token = new Token(TokenType.ILLEGAL, this.CurrentChar.ToString());
}
break;
}
this.ReadChar();
return token;
}
// ..
private string ReadNumber()
{
var number = this.CurrentChar.ToString();
// 次の文字が Digit であればそれを読んで加える
while (this.IsDigit(this.NextChar))
{
number += this.NextChar;
this.ReadChar();
}
return number;
}
private bool IsDigit(char c)
{
return '0' <= c && c <= '9';
}
やっていることは、識別子の時とほとんど同じです。ここでは、整数リテラルのみを考慮しています。浮動小数点数や16進数など複雑な数値には対応していません。ひとまずは整数のみで動くようにします。
ホワイトスペースの除去
ここまででテストを動かすと、ソースコード上の半角スペースや改行が不正なトークンとして処理されてしまいます。
作成しているインタプリタが実行するコードにおいて、空白や改行は意味を持ちません。括弧やカンマ、セミコロンが区切り文字としての意味を持つためです。
Pythonなどインデントが意味を持つ言語であれば、また異なる処理を考える必要がありますが、ここでは空白はトークン列を生成する前に読み飛ばしてしまいましょう。
読み飛ばすのは半角スペース、タブ文字、改行文字です。
public Token NextToken()
{
this.SkipWhiteSpace();
Token token = null;
// ..
}
// ..
private void SkipWhiteSpace()
{
while (this.CurrentChar == ' '
|| this.CurrentChar == '\t'
|| this.CurrentChar == '\r'
|| this.CurrentChar == '\n')
{
this.ReadChar();
}
}
実装は非常にシンプルで現在の文字が読み飛ばすべき文字であれば次の文字に読み勧めるだけです。
テストを動かす
これで識別子とキーワード、整数リテラルのトークンがうまく生成されるようになりました。正しく実装できていれば、上で作成したテストが通るはずです。
テスト名: TestNextToken2
テストの完全名: UnitTestProject.LexerTest.TestNextToken2
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\LexerTest.cs : 行 37
テスト成果: 成功
テスト継続時間: 0:00:00.0085904
ここまでのソースは以下のリンクから確認できます。
mntm0/Gorilla at f06368876a22b233458a9a61ca13c2bf46396ace
その他演算子
さらに演算子を追加してみます。追加するのは “==”, “!”, “!=”, “-“, “*”, “/”, “<“, “>” です。
テストプロジェクトにテストを追加しましょう。
LexerTest.cs
[TestMethod]
public void TestNextToken3()
{
var input = "1 == 1; 1 != 0; ><*/-=";
var testTokens = new List<Token>();
// 1 == 1;
testTokens.Add(new Token(TokenType.INT, "1"));
testTokens.Add(new Token(TokenType.EQ, "=="));
testTokens.Add(new Token(TokenType.INT, "1"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
// 1 != 0;
testTokens.Add(new Token(TokenType.INT, "1"));
testTokens.Add(new Token(TokenType.NOT_EQ, "!="));
testTokens.Add(new Token(TokenType.INT, "0"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
// ><*/-
testTokens.Add(new Token(TokenType.GT, ">"));
testTokens.Add(new Token(TokenType.LT, "<"));
testTokens.Add(new Token(TokenType.ASTERISK, "*"));
testTokens.Add(new Token(TokenType.SLASH, "/"));
testTokens.Add(new Token(TokenType.MINUS, "-"));
testTokens.Add(new Token(TokenType.ASSIGN, "="));
testTokens.Add(new Token(TokenType.EOF, ""));
var lexer = new Lexer(input);
foreach (var testToken in testTokens)
{
var token = lexer.NextToken();
Assert.AreEqual(testToken.Type, token.Type, "トークンの種類が間違っています。");
Assert.AreEqual(testToken.Literal, token.Literal, "トークンのリテラルが間違っています。");
}
}
構文的にはでたらめですが、正しくトークンになっているかをテストしています。構文のチェックは構文解析器の仕事なので、字句解析器は正しくトークンが生成できれば良いのです。
このテストが通るように処理を追加していきます。
1文字の演算子についてはすでに “+” や “=” で実装されているので、Token.TokenType に項目を追加して、swicth文に分岐を追加するだけです。
2文字の演算子については、先頭の文字を読み取った先でさらに次の文字を読む処理を追加する必要があります。
ひとまず、Token.TokenType に項目を追加します。
Lexing/Token.cs
public enum TokenType
{
// ..
// 演算子
ASSIGN,
PLUS,
MINUS,
ASTERISK,
SLASH,
BANG,
LT,
GT,
EQ,
NOT_EQ
// ..
}
Lexerクラスの NextToken() を拡張します。
Lexing/Lexer.cs
// ..
public Token NextToken()
{
this.SkipWhiteSpace();
Token token = null;
switch (this.CurrentChar)
{
case '=':
if (this.NextChar == '=')
{
token = new Token(TokenType.EQ, "==");
this.ReadChar();
}
else
{
token = new Token(TokenType.ASSIGN, this.CurrentChar.ToString());
}
break;
case '+':
token = new Token(TokenType.PLUS, this.CurrentChar.ToString());
break;
case '-':
token = new Token(TokenType.MINUS, this.CurrentChar.ToString());
break;
case '*':
token = new Token(TokenType.ASTERISK, this.CurrentChar.ToString());
break;
case '/':
token = new Token(TokenType.SLASH, this.CurrentChar.ToString());
break;
case '!':
if (this.NextChar == '=')
{
token = new Token(TokenType.NOT_EQ, "!=");
this.ReadChar();
}
else
{
token = new Token(TokenType.BANG, this.CurrentChar.ToString());
}
break;
case '>':
token = new Token(TokenType.GT, this.CurrentChar.ToString());
break;
case '<':
token = new Token(TokenType.LT, this.CurrentChar.ToString());
break;
case ',':
token = new Token(TokenType.COMMA, this.CurrentChar.ToString());
break;
// ..
“*” や “/” といった1文字からなる演算子については特に説明すべき点はありません。”==” と “!=” については、別途判定を行う必要があるのでその処理を追加しています。
“==” を正しく処理するには、現在の文字が ‘=’ のときに、次の文字を先読みして ‘=’ であればそれを合わせて “==” として処理します。次の文字が ‘=’ 以外であれば何もせず “=” のトークンとして処理します。
ちなみに先読みした文字は、Lexer.ReadChar() で次の文字を読むときにさらにその次の文字を読んでその文字を保持するようにしています。
注意点は、先読みした文字と合わせてトークンとする場合、先読みしているのでその分余計に読み飛ばす必要があるということです。ReadChar() が追加で呼ばないと、次のトークンで “=” が余計に生成されてしまいます。
“!=” についても同様です。現在の文字が ‘!’ であれば先読みして “!=” とするのかどうか分岐します。
これでテストが通るようになります。
テスト名: TestNextToken3
テストの完全名: UnitTestProject.LexerTest.TestNextToken3
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\LexerTest.cs : 行 102
テスト成果: 成功
テスト継続時間: 0:00:00.0008731
参考にしている書籍では、なぜか “<=” と “>=” の演算子がないのですが、上記の通り先読みを使えば、同じように実装できるはずです。
ここまでのソース
mntm0/Gorilla at 4fb63bade0228aa33a4a5c89ed61680f7110f039
if文 と bool値
これで字句解析器の実装はひとまず最後になります。if文とbool値のリテラルをトークンにできるようにします。
テストコードを追加します。
[TestMethod]
public void TestNextToken4()
{
var input = @"if (5 < 10) {
return true;
} else {
return false;
}";
var testTokens = new List<Token>();
testTokens.Add(new Token(TokenType.IF, "if"));
testTokens.Add(new Token(TokenType.LPAREN, "("));
testTokens.Add(new Token(TokenType.INT, "5"));
testTokens.Add(new Token(TokenType.LT, "<"));
testTokens.Add(new Token(TokenType.INT, "10"));
testTokens.Add(new Token(TokenType.RPAREN, ")"));
testTokens.Add(new Token(TokenType.LBRACE, "{"));
testTokens.Add(new Token(TokenType.RETURN, "return"));
testTokens.Add(new Token(TokenType.TRUE, "true"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
testTokens.Add(new Token(TokenType.RBRACE, "}"));
testTokens.Add(new Token(TokenType.ELSE, "else"));
testTokens.Add(new Token(TokenType.LBRACE, "{"));
testTokens.Add(new Token(TokenType.RETURN, "return"));
testTokens.Add(new Token(TokenType.FALSE, "false"));
testTokens.Add(new Token(TokenType.SEMICOLON, ";"));
testTokens.Add(new Token(TokenType.RBRACE, "}"));
testTokens.Add(new Token(TokenType.EOF, ""));
var lexer = new Lexer(input);
foreach (var testToken in testTokens)
{
var token = lexer.NextToken();
Assert.AreEqual(testToken.Type, token.Type, "トークンの種類が間違っています。");
Assert.AreEqual(testToken.Literal, token.Literal, "トークンのリテラルが間違っています。");
}
}
キーワードの項目定義を追加するだけです。これだけで必要なキーワードの構文解析は完了します。簡単ですね。
Lexing/Token.cs
public class Token
{
// ..
public static Dictionary<string, TokenType> Keywords
= new Dictionary<string, TokenType>() {
{ "let", TokenType.LET },
{ "fn", TokenType.FUNCTION },
{ "if", TokenType.IF },
{ "else", TokenType.ELSE },
{ "return", TokenType.RETURN },
{ "true", TokenType.TRUE },
{ "false", TokenType.FALSE },
};
}
テストが通ることが確認できればOKです。
テスト名: TestNextToken4
テストの完全名: UnitTestProject.LexerTest.TestNextToken4
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\LexerTest.cs : 行 137
テスト成果: 成功
テスト継続時間: 0:00:00.0009939
ここまでのソース
mntm0/Gorilla at ced7c4d422e4c2ec1631354ca823fe4eb1b8c990
まとめ
字句解析器は入力としてソースコードを受け取り、トークン列を生成します。トークン列を生成するだけでソースコードの構文的な部分のチェックは行いません。文字を読み進めながら対応するトークンを生成するだけです。
今回 Gorilla で実行可能になるコードはここで追加したトークンに対応するもののみです。
変数や関数の定義、簡単な四則演算、if文による条件分岐、それくらいです。非常にシンプルな構文しかサポートしませんが、そのため実装もシンプルで拡張もしやすそうです。
ひとまずは字句解析器をここまでとし、次回は REPL の実装を行います。とはいってもまだ字句解析器の実装しか住んでいませんので、字句解析器を表示するためのREPLになります。
以上。
ここまでのソース
