🦋

Rustで自作言語ために字句解析器を作った話

ガレバレ

2024/07/02に公開1件

Rust

tech

リポジトリ

https://github.com/garebareDA/koto

字句解析器(Lexer)とは

文字をトークンの列に変換を行う機構のものです。
たとえば下記のトークンの定義があり、

constはキーワードで1と定義する
aは変数名でキーワード以外は2と定義する
=は演算子で3と定義する
1は数列で4と定義する

const a = 1

上記ののプログラムをトークンの列に変更すると

[1, 2, 3, 4]

このようになります(実際はすべてが数列に置き換わるわけではありません)。
こうすることにより構文解析という次の処理により適した形にすることができます。

実装する際の考え方

トークンの定義は状況と同じ物を使います。

constはキーワードで1と定義する
aは変数名でキーワード以外は2と定義する
=は演算子で3と定義する
1は数列で4と定義する

const a = 1
↑

まずカーソルを用意して一番前の文字から見ていきます。
先頭から空白が見つかるまで移動します。

const a = 1
     ↑

この時点この文字がconstであることがわかるので1を配列に格納します。

const a = 1
      ↑

そして変数を定義するキーワードのあとには変数名がくるので次の文字が変数名であることがわかり、キーワード以外の文字なので2を配列に格納します。

const a = 1
        ↑

次に来るのは演算子なので3を配列に格納します。

const a = 1
          ↑

次は1で数列なので4を配列に格納します

[1, 2, 3, 4]

最終的アウトプットは以上になります。

実装

トークンの定義

pub struct Token {
    pub _if: i64,
    pub _then: i64,
    pub _else: i64,
    pub _for: i64,
    pub _fun: i64,
    pub _print: i64,
    pub _string: i64,
    pub _number: i64,
    pub _comment: i64,
    pub _identifier: i64,
    pub _let: i64,
    pub _bool:i64,
    pub _return: i64,
    pub _vec: i64,
    pub _import: i64,
    pub _const: i64,
}

impl Token {
    pub const fn new() -> Token {
        Token {
            _if: -1,
            _then: -2,
            _else: -3,
            _for: -4,
            _fun: -5,
            _print: -6,
            _string: -7,
            _number: -8,
            _comment: -9,
            _identifier: -10,
            _let: -11,
            _bool:-12,
            _return: -13,
            _vec: -14,
            _import: -15,
            _const:-16,
        }
    }
}

#[derive(Debug, Clone)]
pub struct TokenValue {
    pub token: i64,
    pub val: String,
}

impl TokenValue {
    pub fn new(token:i64, val:&str) -> TokenValue {
        let value = val.to_string();
        TokenValue{
            token:token,
            val:value,
        }
    }
}

トークンは構造体で定義しています。
キーワードは負の値を使い、演算子はバイトに変換しASCIIコードをトークンとして扱います。キーワード、文字、数字、演算子以外のものは変数として扱います。
またTokenValueでtokenとvalueに文字そのものを格納します。

字句解析器(リポジトリから一部抜粋)

        match reg.captures(&last_str) {
            Some(_) => {
                loop {
                    let text = &content.chars().nth(index).expect("Failed").to_string();
                    let reg = Regex::new(r"(\d|[a-zA-Z])+").expect("Failed");
                    let res = match reg.captures(text) {
                        Some(_) => true,
                        None => false,
                    };
                    if !res {
                        break;
                    }
                    identifier_str += text;
                    index += 1;
                }
                if identifier_str == "print" {
                    let token_value = token::TokenValue::new(TOKEN._print, &identifier_str);
                    return (token_value, index);
                }
...

このコードの場合文字を一つずつみて行きprintが完成して瞬間にトークンが発行されます。
キーワードに当てはまらない場合は変数として扱われます。

use regex::Regex;
  Regex::new(r"[0-9]+") //数字
  Regex::new(r#"""#) //文字列

文字列、数列の判断には正規表現を用いています。
キーワードに当てはまらない場合は数字、文字列を判定する処理に入ります。

        let ascii_code = content
            .chars()
            .nth(index)
            .expect("Failed")
            .to_string()
            .as_bytes()[0];

最後に演算子だった場合はASCIIコードに変換されて格納されます。

まとめ

昔、自作言語を作ったのでそれをアウトプットをしようと思った次第です！！
字句解析器は概念もやることも難しくないのでチャレンジしてみてはどうでしょうか？？

GitHubで編集を提案

SMARTCAMP Engineer BlogPublication

SMARTCAMPに所属するエンジニアの個人記事を集めています。記事の内容は個人の見解であり、社内でのレビュー等は行っておりません。

Discussion

msakuta

content.chars().nth(index) というコードが気になります。これはUTF-8の文字数の index 番目を数えているので、毎回文字列全体を読み直す必要があり、長い入力文字列に対しては非常に非効率的になります。

お勧めは chars() を直接ループで回すか、

let mut cursor = content.chars();
for (i, c) in cursor.enumerate() {
    ...
}

イテレータオブジェクトを維持しつつ next() を一度ずつ呼ぶか、

let mut cursor = input.chars();
while let Some(c) = cursor.next() {
    ...
}

文字列スライスを前に進めてしまう方法です。

fn advance_char(input: &str) -> &str {
  let mut chars = input.chars();
  chars.next();
  chars.as_str()
}

次のコードでベンチマークを取ってみました。まず chars().nth() を毎回使う方法です。

chars.rs

fn main() {
    let mut args = std::env::args();
    args.next();
    let size = args.next().and_then(|s| s.parse().ok()).unwrap_or(1024) * 1024;
    let input = String::from_utf8(vec![b'a'; size]).unwrap();

    let mut count = 0;
    let mut i = 0;
    while let Some(c) = input.chars().nth(i) {
        count += c as usize;
        i += 1;
    }
    println!("Total: {count}");
}

次に next() を一度ずつ呼ぶ方法です。

advance.rs

fn main() {
    let mut args = std::env::args();
    args.next();
    let size = args.next().and_then(|s| s.parse().ok()).unwrap_or(1024) * 1024;
    let input = String::from_utf8(vec![b'a'; size]).unwrap();

    let mut count = 0;
    let mut cursor = input.chars();
    while let Some(c) = cursor.next() {
        count += c as usize;
    }
    println!("Total: {count}");
}

また、文字列スライスの代わりにバイト列の配列にしてしまう方法もあります。これだとマルチバイト文字に対応できませんが。

bytes.rs

fn main() {
    let mut args = std::env::args();
    args.next();
    let size = args.next().and_then(|s| s.parse().ok()).unwrap_or(1024) * 1024;
    let input = vec![b'a'; size];

    let mut count = 0;
    for c in input {
        count += c as usize;
    }
    println!("Total: {count}");
}

結果は次のようになりました。横軸がダミーの入力データのサイズで、縦軸が時間です。 chars.rs だけが２次関数的に時間が伸びていることが分かります。