![02 トークンと字句解析器の役割と実装 [オリジナル言語インタプリタを作る]](https://webbibouroku.com/wp-content/uploads/eye_gorilla.png)
トークンと字句解析器の役割と実装
ここではトークンと字句解析器の実装を行います。
インタプリタがソースコードを実行するまでの流れ
インタプリタはソースコードを入力として受け取り、それを実行します。コンパイラと違い実行形式のファイルを生成したりはせず、すぐにコードを実行します。
入力から実行までの大まかな流れは以下の通りです。
- ソースコード(文字列)を入力として受け取る
- 字句解析によりトークン列を取得する
- 構文解析によりトークン列から抽象構文木を生成する
- 抽象構文木を評価する
Gorilla も上の流れに沿って処理できるように実装していきます。
トークンとは何か
上記 2 の処理に出てくるトークン列が何かというと、与えられたソースコード(文字列)を分解し、処理しやすい単位にまとめたもののことです。例えば以下のようなソースコードを考えます。
let x = 1;
これのコードを字句解析により分解すると、以下のようなトークン列が得られます。
[
{"type": "LET", "literal": "let"},
{"type": "IDENT", "literal": "x"},
{"type": "EQ", "literal": "="},
{"type": "INT", "literal": "5"},
{"type": "SEMICOLON", "literal": ";"},
]
トークンの構成要素は一例です。字句解析では、構文上意味のある語でトークン列を生成します。ソースコードからトークン列を生成する機能を 字句解析器(Lexer) と呼びます。
例えば変数を束縛するための let は、”l”, “e”, “t” の識別子に分割されては困りますし、識別子 “let” と認識されても困ります。予約語である let として、トークンに変換される必要があります。
Gorilla の構文規則では空白や改行は意味を持たないので字句解析時に削除しています。Pythonなど空白やタブの数等に意味を持つ言語の場合、トークンとして保持する必要があります。
トークンの定義
では、ソースコード上でトークンを定義して行きます。
開発方針として最小限の構文をサポートする字句解析器を作成し、必要に応じて拡張していきます。まずは、以下のソースコードからトークン列を生成することを考えます。
let five = 5;
let ten = 10;
let add = fn(x, y) {
x + y;
};
let result = add(five, ten);
トークンが保持すべき情報とはどんなものでしょうか。
まずトークンの種類を特定できる必要があります。それからトークンに対応するソースコード上の文字列も保持しておきます。
例えば let というソースコード上の文字列を1つのトークンとして見ると、LETという種類のトークンで、ソースコード上の文字列は “let” であるという情報を保持します。
より機能を充実させようとするとそのほかの情報も保持させるといいかもしれません。例えば構文エラーで実行できないような場合、トークン上に出現位置(ファイル名や行数、列数)を保持しておくとより詳細なエラー内容を表示できます。しかし、今回はわかりやすくするため種類とリテラル文字列のみを保持します。
以下、C#でのコードです。Token というクラスで管理します。構造体でもいいかもですが。構文解析で用いるのでLexingディレクトリ以下に作成します。
Lexing/Token.cs
namespace Gorilla.Lexing
{
public class Token
{
public Token(TokenType type, string literal)
{
this.Type = type;
this.Literal = literal;
}
public TokenType Type { get; set; }
public string Literal { get; set; }
}
public enum TokenType
{
// 不正なトークン, 終端
ILLEGAL,
EOF,
// 識別子、整数リテラル
IDENT,
INT,
// 演算子
ASSIGN,
PLUS,
// デリミタ
COMMA,
SEMICOLON,
// 括弧(){}
LPAREN,
RPAREN,
LBRACE,
RBRACE,
// キーワード
FUNCTION,
LET,
// その他必要になったら追加します。
}
}
Type(トークンの種類)は、列挙体で定義することにします。ひとまず上のコードを網羅するための種類をすべて定義しておきましょう。
特別な種類のトークンとして ILLEGAL と EOF を用意しています。ILLEGAL は字句解析で正しく処理できなかった文字列の場合に割り振られる種類です。EOF はソースコードの終端を表すトークンで、後作成する構文解析器はこのトークンを見つけたら処理を終了します。
字句解析器の役割
字句解析器(Lexer) は、ソースコードを入力として受け取り、トークン列を生成します。つまり、string型の値を受け取り、上で定義したTokenオブジェクトの配列を返すという処理を作成するということです。
字句解析器(Lexer)の定義・実装
具体的な処理を作成する前ににガワだけ定義してみます。
Lexing/Lexer.cs
namespace Gorilla.Lexing
{
public class Lexer
{
public Lexer(string input)
{
}
public Token NextToken()
{
return null;
}
}
}
コンストラクタでソースコードを渡して初期化し、NextToken() を呼び出すごとに、ソースコードからトークンを生成していくといった処理の流れを想定しています。
ここまで定義できたらテスト用プロジェクトに字句解析器のテストを作成します。
LexerTest.cs
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;
using Gorilla.Lexing;
namespace UnitTestProject
{
[TestClass]
public class LexerTest
{
[TestMethod]
public void TestNextToken1()
{
var input = "=+(){},;";
var testTokens = new List<Token>();
testTokens.Add(new Token(TokenType.ASSIGN, "="));
testTokens.Add(new Token(TokenType.PLUS, "+"));
testTokens.Add(new Token(TokenType.LPAREN, "("));
testTokens.Add(new Token(TokenType.RPAREN, ")"));
testTokens.Add(new Token(TokenType.LBRACE, "{"));
testTokens.Add(new Token(TokenType.RBRACE, "}"));
testTokens.Add(new Token(TokenType.COMMA, ","));
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, "トークンのリテラルが間違っています。");
}
}
}
}
記号だけの文字列を与え、正しくトークンが生成されるかテストしています。ソースコードは構文として意味のないでたらめな文字列ですが、字句解析器ではあくまでトークン列を生成するのが役割であり、その意味を解析して構文エラーの判定をするのは、構文解析器の役割です。
ソースコードの最後は、終端用のトークンが生成されることも確認しています。
ということでテストを実行してみます。
メッセージ: Test method UnitTestProject.LexerTest.TestNextToken1 threw exception:
System.NullReferenceException: Object reference not set to an instance of an object.
当然処理の実装がまだなのでエラーになります。最初の実装はこのテストを通すところからです。
まずは、構文解析器で管理する状態は以下の通りです。
public class Lexer
{
public string Input { get; private set; }
public char CurrentChar { get; private set; }
public char NextChar { get; private set; }
public int Position { get; private set; } = 0;
public Lexer(string input) => this.Input = input;
// ...
}
コンストラクタでソースコードを受け取りこれを保持します。トークンを生成するにあたってこのソースコードから文字を読みだしていきます。
Position は現在読みだしている文字の位置を保持します。このインデックスが指す値が CurrentChar です。NextChar はさらにその次の文字を先読みして保持しておきます。
NextChar が先読みして値を保持する必要があるのは、数値や識別子、== 等の記号をうまくトークンにするためです。例えば 現在の文字が “=” だった場合に、これを値を代入する演算子なのか、等価を判定するための == 演算子の一部なのかは次の文字を見なければわかりません。そのため常に1文字先を読めるようにしています。
ちなみに先読みできるのは1文字だけでよいです。前の文字に戻ったり、何文字も先にいきなりジャンプしたりする必要もありません。
文字を1文字読みこれらの状態を更新するためのメソッドを定義します。
public class Lexer
{
// ...
private void ReadChar()
{
if (this.Position >= this.Input.Length)
{
this.CurrentChar = (char)0;
}
else
{
this.CurrentChar = this.Input[this.Position];
}
if (this.Position + 1 >= this.Input.Length)
{
this.NextChar = (char)0;
}
else
{
this.NextChar = this.Input[this.Position + 1];
}
this.Position += 1;
}
// ...
}
ReadChar() は、1文字を読み進めるためのメソッドです。範囲外まで進むとNULL文字(0)で終端を表しています。現在の文字を読むついでにその次の文字を読み込んでいます。これも範囲外の参照をしないように気を付けます。
C# の char型は16ビットであり、一通りの日本語は1文字として処理されます。したがって日本語の識別子等にも対応できるようになっています。
ReadChar の実装が済んだら、Lexer クラスのコンストラクタで呼び出すようにします。これは初期化時点で1文字目がすでに読み込まれている状態にするためです。こうすることで後の都合がよくなります。
public Lexer(string input)
{
this.Input = input;
this.ReadChar();
}
では、NextToken() を実装します。まずは先ほどのテストを通すため、”=+(){},;” の各種トークンを生成できるようにします。これはそれぞれ1文字の記号なので、難しくありません。
public class Lexer
{
// ...
public Token NextToken()
{
Token token = null;
switch (this.CurrentChar)
{
case '=':
token = new Token(TokenType.ASSIGN, this.CurrentChar.ToString());
break;
case ';':
token = new Token(TokenType.SEMICOLON, this.CurrentChar.ToString());
break;
case '(':
token = new Token(TokenType.LPAREN, this.CurrentChar.ToString());
break;
case ')':
token = new Token(TokenType.RPAREN, this.CurrentChar.ToString());
break;
case '{':
token = new Token(TokenType.LBRACE, this.CurrentChar.ToString());
break;
case '}':
token = new Token(TokenType.RBRACE, this.CurrentChar.ToString());
break;
case (char)0:
token = new Token(TokenType.EOF, "");
break;
}
this.ReadChar();
return token;
}
// ...
}
現在の文字を読み、各種記号に一致していればそれに対応するトークンを生成しています。その後文字を次の文字に進めます。
これで先ほど作成したテストが突破できます。
テスト名: TestNextToken1
テストの完全名: UnitTestProject.LexerTest.TestNextToken1
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\LexerTest.cs : 行 11
テスト成果: 成功
テスト継続時間: 0:00:00.0135801
ひとまずここまでとします。
ここまでのソース
mntm0/Gorilla at 79352e67a827d9a08e5218a5d24a9b09f0cc282b
次はよりそれっぽいソースコードからトークン列を得られるようにしていきます。
let five = 5;
let ten = 10;
let add = fn(x, y) {
x + y;
};
let result = add(five, ten);
上記のコードを入力として与え、正しくトークン列を生成できるようにします。これには識別子や数値リテラルをうまく読み取る必要があります。
以上。
