概要

構文と抽象構文木へ変換するコードが書かれたファイルを与えることで、Rust用のLL(1)のトークンパーサを自動生成することができるソフトウェアを作りました。名前はとりあえず"llmaker"にしています。リポジトリはpuripuri2100/llmakerです。

構文等を与えるファイルはRustや、RustでのLR(1)パーサジェネレータであるlarlpopと似ている構文なので、それらのシンタックスハイライトが適用できます。

インストールと使い方

まずRustのライブラリ管理ツールであるCargoをインストールしてください。普通にやればRustのコンパイラ等もついてくるはずです。ついてこなかったら頑張って入れてください。

次にllmakerをインストールします。使うだけであれば

cargo install --git https://github.com/puripuri2100/llmaker

でできるはずです。色々と中身を見たいのであれば、リポジトリを手元にcloneし、そこからインストールしても良いでしょう。

git clone https://github.com/puripuri2100/llmaker.git
cd llmaker

make install

起動はllmaker <input file>だけで行えます。構文等が書かれたファイルを食わせるだけです。拡張子は特に決められていません。出力先のファイル名は自動で生成されますが、調節したい場合はllmaker <input file> -o <output file>で自由に出力先を決められます。

出力されたファイルではparse (tokens: Vec<T>) -> Result<U, ParseError>という関数と、エラー用の列挙型であるParseErrorを提供します。

入力ファイルの書き方。

llmakerでは、Rustの型やコードを解析することはせず、文字列での入力を要求します。気を付けてください。

入力ファイルは大きく分けてヘッダ・設定部分・構文部分の3つに分かれます。

ヘッダでは依存するクレートの読み込みや、必要な関数などを記述することができます。 Rustのコードをそのまま文字列にしたものを並べるだけです。エスケープ文字は\"のみです（\nなどはサポートしていません）。書いた文字列はそのままファイルの先頭部分に出力されます。例えば、

"use super::lexer;"

"fn hoge () {
  println!(\"hoge\");
}"

のように書けば、出力ファイルには

use super::lexer;

fn hoge () {
  println!("hoge");
}

と出るわけです。

設定部分では、externブロックの中で入力するトークンに関する情報を与えます。

構文は

extern {
  enum "トークンの型" {
    トークン名 => "トークンの具体的な中身",
    トークン名 => "トークンの具体的な中身",
    ...
    トークン名 => "トークンの具体的な中身",
  }
}

となっています。トークン名はアルファベット大文字から始まり、アルファベット・数字・アンダーバーが続く必要があります。

具体的にはこのような感じです。トークンの中身を表す文字列は、パターンマッチで判別できるものにしてください（内部でパターンマッチを使っているので）。ですので、ワイルドカード表記が使えます。

extern {
  enum "(lexer::TokenKind, lexer::Range)" {
    Tok_EOF          => "(lexer::TokenKind::EOF            , _)",
    Tok_VAR          => "(lexer::TokenKind::VAR         (_), _)",
    Tok_CONSTRUCTOR  => "(lexer::TokenKind::CONSTRUCTOR (_), _)",
    Tok_LCURLYBRACES => "(lexer::TokenKind::LCURLYBRACES   , _)",
    Tok_RCURLYBRACES => "(lexer::TokenKind::RCURLYBRACES   , _)",
    Tok_EQ           => "(lexer::TokenKind::EQ             , _)",
    Tok_COMMA        => "(lexer::TokenKind::COMMA          , _)",
    Tok_SEMICOLON    => "(lexer::TokenKind::SEMICOLON      , _)",
    Tok_COLON        => "(lexer::TokenKind::COLON          , _)",
    Tok_ARROW        => "(lexer::TokenKind::ARROW          , _)",
  }
}

構文部分ではBNF表記のようなものを連ねていくだけです。一番トップとなる規則にはpubと付けてください（実際には公開されませんが……）。pubとついている規則が一つもないとエラーが出ます。

構文は

規則名 "出力型" = {
  規則 => {
    "コード"
  },
};

で、具体例は

pub main: "types::Term" = {
  <head: head> <_gr: gr> <setting: setting> <body: body> <_v: Tok_EOF> => {
    "let mut v = head;
    v.reverse();
    (v, setting, body)"
  },
};

head: "types::Head" = {
  <tok: Tok_STR> <tail: head_tail> => {
    "let mut tail_v = tail;
    let (stok, rng) = tok;
    let s = lexer::get_string(stok).unwrap();
    tail_v.push((rng, s));
    tail_v"
  },
  => {"Vec::new()"},
};

のような感じです（main規則がトップの規則なのでpubを付けています。これで、最初にmain規則が呼ばれることになります。）。規則は"<変数名: 規則名・トークン名>"で作られます。規則名は小文字スタートで、トークン名は大文字スタートなのでわかりやすいと思います。規則名やトークン名につけた変数名はコードの中で使えます。規則を与えないことで<null>や()に対応するものが与えられます。例中のhead規則での=> {"Vec::new()"},というやつですね。 <null>規則を含む規則は規則列の先頭に使えないという制約があります。

ヘッダ・設定部分・構文部分は

<ヘッダ>

grammar;

<設定部分>

<構文部分>

という風に並べて書きます。順番が変わると構文解析に失敗しますし、grammar;が抜けても失敗します。気を付けてください。

また、

grammar
extern
enum
pub

はそれぞれ予約語です。

実際に使っているファイルを知りたい人はdemoファイルを見てみてください。

使っている技術

iteratorの中でも一つ先読みが可能なPeekableというものを内部で使っています。それぞれの規則の中の先頭をすべて展開してトークンを取得し、1つ先読みのパターンマッチで振り分けています。

トークンパーサなので、構文規則が適切に組まれているときに、規則をすべて展開すれば必ずトークンに行き当たるという性質を利用しています。

一つの規則につき一つの関数を作り、トークン消費にもそれぞれ関数を割り当てているので、機械的に相互に呼び出すだけで構文解析が完了します。

最後に

構文解析の勉強をしてすぐに作った、人生で初めて作るパーサジェネレータなのでバグや勘違いがあるかもしれません。指摘してくださるとうれしいです。

また、Peekableではなくて位置を数で保持することでk個の先読みを可能にし、トークンが重なった時の衝突を回避できるLL(k)のパーサを作ることができるように改造したいとも思っています。

puripuri2100が進捗の報告をするようです

文字列を弄っています

Rust用のLL(1)トークンパーサジェネレータを作った話

概要

インストールと使い方

入力ファイルの書き方。

使っている技術

最後に