第1回目である今回は、半分コラムみたいな文を書いてみたいと思う。もちろん技術的に深掘りするつもりであるが、設計面や思想的なところを最初は書きたい。 現状はまだフロントエンドができかけ、といったところ。

きっかけ

発端はVHDLという言語（プログラミング言語ではない）を拡張して、C++のテンプレートのごとく機能拡張するのが夢だった。VHDLはCFG（文脈自由文法）ではないため、それ系の生成器は使えない。パーサの手書きが決定した。開発期間が短すぎてVHDL拡張は夢で終わった。

ちなみに自己紹介すると、私はプロのコンパイラ屋さんではない。アマチュアである。

Rustで自作のコンパイラを作りたい

しかしコンパイラ開発欲は止まらない。学生時代、コンパイラを作成する講義や実験を履修したものである。もうちょっとadvancedであるとか、IR(中間表現)に凝ってみるとかやってみたい。今回は実装言語にRustを使いたい。

ドラゴンブック、タイガーブックなどの教科書を逐次参考にしてもよいが、今の時代からするとやや古かったり自分とアンマッチな気もする。

以下の方針で作成する。

• 自作のプログラミング言語を作る
  • 文法はScalaとGoやPythonとRustが混ざった感じで、小さい集合で自作しやすいよういいとこ取りをする
  • 静的型付け言語である
  • C言語よりリッチそうな機能（クラスやインスタンス等）は後から考える
  • 言語仕様は後から詰めるとして、当初はざっくりで良い
• フロントエンド（字句解析、構文解析）はライブラリとして独立させたい
  • 欲を言えばLinterなどの開発に適用してもいい。実装1回目はあまり考えないでおく
  • 字句解析は自作のlexer generatorを使う。VHDL拡張を考えたときに自作した
  • 構文解析は前述の通り手書きである。LL(1)あたりを想定しておく
• バックエンド
  • 実行処理系はLuaJITなどを考えても良い

字句解析器

rflex

自作で、当初はRust newbieだったため、作るのに1年近くかかった。

• https://crates.io/crates/rflex

• まずlexer用のDSL(.l らしき)ファイルのパーサを手書きで書いた
• 正規表現のパーサも手書きで書いた
• オートマトンの構築・変換（NFA→DFA）のコードを書いた
• オートマトンの最小化のコードを書いた（正確にはこのへんは移植をしていた
  • 目的のためならばライセンスの範囲で移植なども行う。そもそもlexer generator作るのが実装を遅くする原因ではあったのだが、ここはこだわりポイントだった
• lexer生成のコードを書き、Rustで動くテンプレートエンジンでコード生成器を作り上げた
• 名をrflexと名付けOSSとしてリリースし、後日何件かPRを受け付けた

自作言語っぽいトークンの定義を書く

欲しいキーワードと対応するトークンを決めて定義していく。 複数行コメント、複数行文字列、浮動小数点数といったちょっと難しいこと、考えたくないことは今は考えないでおく。

• lexer.l
• lib.rs

lexerはrflexによってコードが自動生成されるので、Parser structを作る。 &str からlexerがトークンに変換しつつ、parser側では手動であーでもないこーでもないとマッチするかしないかを実装していった。

単体テストでlexerが動くかは確認しておく。

    #[test]
    fn lexer_simple_keyword() {
        let s = " if else while break continue for class fn val var";
        let mut l = lexer::Lexer::new(&s, 1u64);
        assert_eq!(l.yylex().unwrap(), Token::If);
        assert_eq!(l.yylex().unwrap(), Token::Else);
        assert_eq!(l.yylex().unwrap(), Token::While);
        assert_eq!(l.yylex().unwrap(), Token::Break);
        assert_eq!(l.yylex().unwrap(), Token::Continue);
        assert_eq!(l.yylex().unwrap(), Token::For);
        assert_eq!(l.yylex().unwrap(), Token::Class);
        assert_eq!(l.yylex().unwrap(), Token::Function);
        assert_eq!(l.yylex().unwrap(), Token::Val);
        assert_eq!(l.yylex().unwrap(), Token::Var);
    }

構文解析器

BNFらしきもので構文を定義すると、現在の最新版では以下のようになっている。 細かな命名や定義ミスはご了承いただきたい。

    // prog := expr NewLine expr | expr | e
    // expr := assign | if_expr
    // block := "{" prog* "}"
    // if_expr := "if" expr block else_expr?
    // else_expr := "else" block
    // assign := val_def | identifier "=" logical_expr | logical_expr
    // val_def := "val" identifier (":" def_ty)? ("=" logical_expr)
    // def_ty := Int64 | UInt64 | identifier | Unknown
    // logical_expr := equality ("&&" relational | "||" relational)*
    // equality := relational ("==" relational | "!=" relational)*
    // relational := add ("<" add | "<=" add | ">" add | ">=" add")*
    // add := mul ("+" mul | "-" mul)*
    // mul := primary ("*" mul | "/" mul)*
    // primary := "(" expr ")" | identifier "(" expr_list ")" |
    //            identifier |
    //            UInt64 | Int64 | Integer | Null
    // expr_list = "" | expr | expr "," expr_list

impl<'a> Parser<'a> {
    pub fn new(input: &'a str) -> Self {}
}

 fn peek(&mut self) -> Option<&Token> {}
 fn next(&mut self) {}
  pub fn expect_err(&mut self, accept: &Token) -> Result<(), String> {}

peekを呼ぶと現状から1個トークンが返り（無いときはNoneである）、それを順にmatchで想定しているトークンかどうかパターンマッチで比較していくものである。

• peek: 1個トークンを先読みする
• next: 現在読み込んだ1つ目のトークンを捨てる
• expect_err: 引数acceptと同一トークンのときnextを呼び、異なるときはエラーを返す

今回はエラーは文字列で返すこととしていた。返り値の型は std::Result<(), String> 。 今思い返すとanyhowなどのほうが良い気もするが、体力があれば更新したい。

AST

当初は ast.rs のようなツリー構造を書いていた。

執筆時点では、以下のような文書を読み、ASTのExpr以下はフラット化している (ast.rs)。

• AST のフラット化 - https://zenn.dev/nissy_dev/scraps/2e224466af001e#comment-96b2f2611ec314
• Adrian Sampson: Flattening ASTs (and Other Compiler Data Structures)
• Rust+LLVMでコンパイラを作る：#3 大枠づくり

終わり

part1はここで終了する。ASTの記述あたりから力尽きてきたので、part2があれそこから解説するかもしれない。 無事パーサを書き終えることができたら、IRの表現やコード生成などのトピックもコードを交えすることができると思う。

• https://crates.io/crates/rflex
• https://github.com/suma/toylangc/