実践: 数式パーサの作成
LuneScript の強力な型システム、特に代数的データ型 (Algebric Data Type) とパターンマッチを活用して、数式パーサ（計算機）を作成してみましょう。
このチュートリアルでは、"1 + 2 * 3" のような文字列を解析し、計算結果を出すプログラムをステップ・バイ・ステップで作成します。
目標
以下の機能を実装します。
- 四則演算 (
+,-,*,/) と括弧()のサポート。 - 整数の計算。
- REPL (Read-Eval-Print Loop) 形式での対話的実行。
Step 1: トークン定義
まずは、入力文字列を意味のある単位（トークン）に分解するための型を定義します。
LuneScript の alge (Algebric Data Type) が最適です。
// @lnsFront: skip
// Token 型の定義
alge Token {
Num( val: int ), // 数字: 123
Op( val: str ), // 演算子: +, -, *, / (, )
Eof, // 文字列の終端
}
Step 2: 字句解析 (Lexer)
文字列を読み取って Token を生成する Lexer クラスを作成します。
// @lnsFront: skip
class Lexer {
let text: str;
let len: int;
let mut pos: int;
pub fn __init( text:str ) {
self.text = text;
self.len = #text;
self.pos = 1;
}
// 現在の文字を取得 (範囲外なら 0 の文字コード)
fn getChar(): int {
if self.pos > self.len { return 0; }
return self.text.byte( self.pos );
}
// 次のトークンを取得
pub fn next() mut: Token {
// 空白スキップ
while self.getChar() == ? {
self.pos = self.pos + 1;
}
let ch = self.getChar();
if ch == 0 { return .Eof; }
// 数字の場合
if ch >= ?0 and ch <= ?9 {
let mut numVal = 0;
while true {
let cur = self.getChar();
if cur < ?0 or cur > ?9 { break; }
numVal = numVal * 10 + ( cur - ?0 );
self.pos = self.pos + 1;
}
return Token.Num( numVal );
}
// 演算子の場合
self.pos = self.pos + 1;
return Token.Op( "%c" ( ch ) );
}
}
? は文字コードリテラルです (?A は 65)。
Step 3: 構文木 (AST) の定義
構文解析の結果を格納する木構造を定義します。ここでも alge が活躍します。
// @lnsFront: skip
alge Ast {
Val( val: int ), // 数値
Bin( op: str, left: Ast, right: Ast ), // 二項演算 (左辺 op 右辺)
}
Step 4: 構文解析 (Parser)
再帰下降構文解析法 (Recursive Descent Parsing) を用いて、トークン列を AST に変換します。
優先順位を扱うため、Expr (式), Term (項), Factor (因子) にメソッドを分割します。
// @lnsFront: skip
class Parser {
let mut lexer: Lexer;
let mut cur: Token;
pub fn __init( text: str ) {
self.lexer = new Lexer( text );
self.cur = self.lexer.next();
}
// トークンを進める
fn next() mut {
self.cur = self.lexer.next();
}
// 因子: 数値 または (式)
fn parseFactor() mut: Ast {
match self.cur {
case .Num( val ) {
self.next();
return .Val( val );
}
case .Op( op ) {
if op == "(" {
self.next();
let node = self.parseExpr();
match self.cur {
case .Op( nextOp ) {
if nextOp == ")" {
self.next();
return node;
}
}
default {}
}
print( "Error: missing )" );
return node;
}
}
default {
print( "Error: unexpected token" );
}
}
return .Val( 0 );
}
// 項: 掛け算、割り算
fn parseTerm() mut: Ast {
let mut left = self.parseFactor();
while true {
match self.cur {
case .Op( op ) {
if op == "*" or op == "/" {
self.next();
let right = self.parseFactor();
left = .Bin( op, left, right );
} else {
break;
}
}
default { break; }
}
}
return left;
}
// 式: 足し算、引き算
pub fn parseExpr() mut: Ast {
let mut left = self.parseTerm();
while true {
match self.cur {
case .Op( op ) {
if op == "+" or op == "-" {
self.next();
let right = self.parseTerm();
left = .Bin( op, left, right );
} else {
break;
}
}
default { break; }
}
}
return left;
}
}
Step 5: 評価と実行
最後に、生成された AST を再帰的に処理して計算結果を求める関数を作成します。
match 式を使うことで、簡潔に記述できます。
// @lnsFront: skip
fn eval( node: Ast ): int {
match node {
case .Val( val ) {
return val;
}
case .Bin( op, left, right ) {
let l = eval( left );
let r = eval( right );
switch op {
case "+" { return l + r; }
case "-" { return l - r; }
case "*" { return l * r; }
case "/" { return l / r; }
}
}
}
return 0;
}
// メイン処理
let input = "1 + 2 * (3 + 4)";
let mut parser = new Parser( input );
let ast = parser.parseExpr();
print( "%s = %d" ( input, eval( ast ) ) );
これを実行すると 1 + 2 * (3 + 4) = 15 が出力されます！
完成コード
すべてのコードをまとめたものが以下になります。
alge Token {
Num( val: int ),
Op( val: str ),
Eof,
}
class Lexer {
let text: str;
let len: int;
let mut pos: int;
pub fn __init( text:str ) {
self.text = text;
self.len = #text;
self.pos = 1;
}
fn getChar(): int {
if self.pos > self.len { return 0; }
return unwrap self.text.byte( self.pos ) default 0;
}
pub fn next() mut: Token {
while self.getChar() == ? {
self.pos = self.pos + 1;
}
let ch = self.getChar();
if ch == 0 { return .Eof; }
if ch >= ?0 and ch <= ?9 {
let mut numVal = 0;
while true {
let cur = self.getChar();
if cur < ?0 or cur > ?9 { break; }
numVal = numVal * 10 + ( cur - ?0 );
self.pos = self.pos + 1;
}
return Token.Num( numVal );
}
self.pos = self.pos + 1;
return Token.Op( "%c" ( ch ) );
}
}
alge Ast {
Val( val: int ),
Bin( op: str, left: Ast, right: Ast ),
}
class Parser {
let mut lexer: Lexer;
let mut cur: Token;
pub fn __init( text: str ) {
self.lexer = new Lexer( text );
self.cur = self.lexer.next();
}
fn next() mut {
self.cur = self.lexer.next();
}
fn parseFactor() mut: Ast {
match self.cur {
case .Num( val ) {
self.next();
return .Val( val );
}
case .Op( op ) {
if op == "(" {
self.next();
let node = self.parseExpr();
match self.cur {
case .Op( nextOp ) {
if nextOp == ")" {
self.next();
return node;
}
}
default {}
}
print( "Error: missing )" );
return node;
}
}
default {
print( "Error: unexpected token" );
}
}
return .Val( 0 );
}
fn parseTerm() mut: Ast {
let mut left = self.parseFactor();
while true {
match self.cur {
case .Op( op ) {
if op == "*" or op == "/" {
self.next();
let right = self.parseFactor();
left = .Bin( op, left, right );
} else {
break;
}
}
default { break; }
}
}
return left;
}
pub fn parseExpr() mut: Ast {
let mut left = self.parseTerm();
while true {
match self.cur {
case .Op( op ) {
if op == "+" or op == "-" {
self.next();
let right = self.parseTerm();
left = .Bin( op, left, right );
} else {
break;
}
}
default { break; }
}
}
return left;
}
}
fn eval( node: Ast ): int {
match node {
case .Val( val ) {
return val;
}
case .Bin( op, left, right ) {
let l = eval( left );
let r = eval( right );
switch op {
case "+" { return l + r; }
case "-" { return l - r; }
case "*" { return l * r; }
case "/" { return l / r; }
}
}
}
return 0;
}
// メイン処理
let input = "1 + 2 * (3 + 4)";
let mut parser = new Parser( input );
let ast = parser.parseExpr();
print( "%s = %d" ( input, eval( ast ) ) );