25日目の記事です．

これは1日目の記事シミュコンパイラ係はやめとけ - f03d-5bab's blog でちょっと言及した話で，先行研究：

の続き，というか1年後の記事です．コンパイラの初めの方の処理の理解が怪しい人は読んできてください．

読みましたか？なんかもう上の記事で結論が出されている感じですが，私の結論は違ったので書きます．

要旨

logosも十分あり
自由な型を入力できるようなparser generatorは多い
yacc定義のPEG形式への翻訳は，precedenceは簡単でassociativityは（専用の機能がなければ）ちょっと難しい
lalrpopはconflictを解消できなくて大変

動機

今回書きたいparserはOCamlのサブセットの言語を入力とするものです．書きたいは嘘だな．もう書いたので書きたくはないです．

ここでは動機づけとしてCPU実験の話をします．1日目の記事で触れたように，CPU実験のコンパイラ係はOCamlのサブセットの言語を入力とするparserを書くことになり（書くことになるわけではなく，自分からこの道を選んでいます（為念）），←こういうネストしたコメントが残念ながらコードに登場してしまいます．どう考えてもネストさせる必要がないものが3箇所だけ*1．だから，ネストしたコメントに対応するparser（lexer）を作りたかったのでした．

実はこの動機づけには不足があり，というのも一体型（文字列から直接構文木を構成するようなもの）になっている多くのパーサジェネレータで，ネストしたコメントに対応するのは簡単だからです．多くのパーサジェネレータは生成規則自身を呼び出すことができ，ocamllex と同じようにコールスタックで実現できます．pegなら次のように書けばよいです．上2つのruleは関係ありません．

peg::parser!(grammar parser() for str {
    pub rule expr() = ident() _ "+" _ ident()
    rule ident() -> &'input str
        = $(quiet!{[c if c.is_ascii_alphabetic()][c if c.is_ascii_alphanumeric()]*})
        / expected!("identifier")
    rule ws() = [' ' | '\t' | '\n']*
    rule _() = ws() ** ("(*" comment())
    rule comment()
        = [^ '(' | '*']* (
            "*)"
            / "(*" comment() comment()
            / [_] comment()
        )
});

"(*"で再入して2回commentを呼んでいるところもocamllexによる標準的な実装と同じですね．ここを1回にするとネストできない版になります．lexerを分離する場合と同じく空白を読み飛ばす部分にコメントを飛ばす処理が混ざってくるため少しだけ非自明な感じですが，C-styleのコメント/* ... */と同じで難しくはないでしょう．（12/29追記：コメントが複数あるものを受け付けない実装になっていたのを修正．）

例の記事のデモも次のように書けます．型定義は例の記事と同じです．

エラー処理は省いていますが明らかな変更のみで対応できます．普段からエラー処理をさぼっているわけではありません．うそじゃないよ

peg::parser!(grammar demo() for str {
    rule num() -> i64 = s:$(['0'..='9']+) { s.parse().unwrap() }
    rule ident() -> &'input str
        = $(quiet!{[c if c.is_ascii_alphabetic()][c if c.is_ascii_alphanumeric()]*})
        / expected!("identifier")
    rule ws() = [' ' | '\t' | '\n']*
    rule _() = ws() ** ("(*" comment())
    rule comment()
        = [^ '(' | '*']* (
            "*)"
            / "(*" comment() comment()
            / [_] comment()
        )
    use BinOpKind::*;
    rule term_op() -> BinOpKind = "+" { Add } / "-" { Sub }
    rule factor_op() -> BinOpKind = "*" { Mul } / "/" { Div }
    rule atom() -> Box<Expr<'input>>
        = "(" _ e:term() _ ")" { e }
        / l:position!() _ x:num() _ r:position!() { Box::new(Spanned::new(ExprKind::Num(x), (l, r))) }
        / l:position!() _ i:ident() _ r:position!() { Box::new(Spanned::new(ExprKind::Var(i), (l, r))) }
    rule term() -> Box<Expr<'input>>
        = precedence!{
            e1:(@) _ op:term_op() _ e2:@ { let l = e1.span.0; let r = e2.span.1; Box::new(Spanned::new(ExprKind::BinOp(op, e1, e2), (l, r))) }
            --
            e1:(@) _ op:factor_op() _ e2:@ { let l = e1.span.0; let r = e2.span.1; Box::new(Spanned::new(ExprKind::BinOp(op, e1, e2), (l, r))) }
            --
            e:atom() { e }
        }
    rule stmt() -> Stmt<'input>
        = l:position!() _ "let" !ident() _ x:ident() _ "=" _ t:term() _ ";" r:position!() { Spanned::new(StmtKind::Let(x, t), (l, r)) }
        / l:position!() _ "print" !ident() _ t:atom() _ ";" r:position!() { Spanned::new(StmtKind::Print(t), (l, r)) }
    pub rule program() -> Vec<Stmt<'input>> = stmt()*
});

fn main() {
    demo::program(
        r#"(* x = 3 *)
let (* x = 3 *) (* x = 3 *) x = 1 + 2;
let y = x * 4;
let z = x + y * x; (* 39 *)
print (x + y + z); (* 54 *)
let w = z / 3 + y;
(* 計算の (* 結果は *) 0 になる *)
let ans = x * (y - w) + y;
print ans;"#,
    )
    .unwrap();
}

空白を読み飛ばす部分が大量に出てきて鬱陶しいですね．pegは_, __, ___の名前がついたruleを括弧なしで呼べるため薄目で見れば気にな…ります．仕方ない．

じゃあなんでまだパーサーの選定で悩むことがあるかというと，3Sの講義でLR構文解析のアルゴリズムとそれがそこそこ複雑であることを学び，失敗したらバックトラックをする（失敗する前にコピーをする）ような構文解析はLR文法であるところのOCamlに不向きかなと思ったのです．実装して比較する時間すら惜しかったため憶測でしかありません．同じLR法なら文法ファイルの移植も簡単だと踏んでいたという理由もあります（実際は全然そんなことありませんでした．上の例からわかるように，precedence指定されているものだけならPEGで容易に書き換えができ，combineやpegはプログラミング言語で出てくるような文法をparseすることに特化した機能を持っているため，LR法に強いこだわりがなければ全然これらのほうが良いです）．

というわけで，コンパイラとしてOCamlのサブセットの文法を入力とし，エラー出力のために位置情報を改行込みで認識したいという前提で，LR法にどれだけ準拠しているかと，nested commentを扱うために行う作業の量の観点から，rustで使えるlexer + parser各ライブラリの比較をします．例えば，入力がバイト列であったり，C-styleのコメントだけで十分だったりする状況なんかは考慮していません．時間が取れなくて全部は試せていないもののテストやexampleは全部読んでいます．なお実際に実装で用いたのはplexとlalrpopの組み合わせです．

比較

crate name	version	type
`plex`	`0.2.5`	lexer, parser
`logos`	`0.12.1`	lexer
`nom`	`7.1.1`	parser
`combine`	`4.6.6`	parser
`peg`	`0.8.1`	parser
`lalrpop`	`0.19.8`	parser

この記事がmajor update後に読まれている気が全くしませんが，versionを固定しています．

コンパイラやアセンブラやlinterを作ろうと思った場合は特に，構文木の要素が入力のどの部分から来たのかという情報がほしいです．これを位置情報と呼ぶことにします．構文木の各要素の，対応する入力文字列におけるline numberとcolumn numberのことです．rustcやclippyのあの丁寧なエラー報告も，構文解析時の開始地点と終了地点それぞれのline numberとcolumn numberを全ての要素がずっと持ち続けているからexactな場所に波線を引けるんですね（波線を引いている人は位置情報を受け取ったannotate-snippetsとかrust-analyzerだけど）．今回は文字のbyte offsetだけだと困ります．人間には改行文字が特別な形で見えているため．後から改行文字を数えるのはなんか気に入らないので，それを踏まえるとplexくらい自由度があるとよさそうです．

文法の記述をどこに行うかは意外と重要で，lexerについてはlogosもplexも.rsに書けるので大差なく，parserについてはpegに軍配が上がります．人間よりIDEに考えてもらったほうが変なミスが少ないですからね．

lexerとparserで分けてはいますが，parserが正規表現に近いことしかしないなら機能としてはlexerなんですよね（ここでparserとして紹介しているものをlexerとして用いることができるということです．文字列からVecなどに入ったトークン列を構成する，.lexと似たような非常に単純なparserを作る（ライブラリを使わないほうが簡単に書けそうだけど））．なので，lexerの選択肢が極端に少ないということはなく，問題はlalrpopとpeg，nom，combineくらいしか入力に（ほぼ）任意の型を取れない点にあります．あれ，意外と多いじゃん

lexer

全体の比較はこれくらいにして，まずはlexerからそれぞれの特徴を見てみます．

`plex`

「次の文字列」を読んでユーザー定義の型を返すというインターフェースが用意されます．任意の型Tokenに対し，次のように書き，

lexer! {
    fn next_token(text: 'input) -> Token;
    /* ここにruleを書く */
}

次のシグネチャを持つグローバル関数定義が出力されます．Tokenは当然（←w）'inputに依存できます．

fn next_token<'input>(input: &'input str) -> Option<(Token, &'input str)>;

「次の文字列」というのはこの関数の入力の先頭からの文字列のことです．何らかにマッチしたらその文字分進んだ&'input strが一緒に帰ってくるので，それを適当な構造体で持ち回してIteratorとかを実装するのが主な使い方です．Tokenとしてトークンではなく制御パターン（とその中身にトークン）を持つようにすると，簡単にDFAなどを構成できます．実装量は少し多めだけど，マクロの箱の中身が単純であり，インターフェースが入力とほぼ乖離しないところがだいぶ素朴で扱いやすい．

nested commentには，例の記事で実装が示されていたように，コメントの内部とそれ以外の2種類のlexer!を用いて，後者に制御のための構造をはさむことで対応できます．

位置情報は，改行のたびに現在位置を適切に更新し，文字列を読んだ際に残りの文字列に対して.chars().count()をした結果を覚えておき，消費された文字数を計算すると計算回数が減らせます．こういう感じです

pub struct Lexer<'input> {
    remain: &'input str,
    last_remain_len: usize,
    current_loc: Loc,
}

// in next():
let state = next_token(self.remain);

let (state, remaining) = state?;

self.remain = remaining;

let remain_len = remaining.chars().count();
let consumed = self.last_remain_len - remain_len;
self.last_remain_len = remain_len;

let lo = self.current_loc;
self.current_loc.col += consumed;
let hi = self.current_loc;
// ...

ルールの右辺は<syn::Expr as syn::parse::Parse>::parseで処理される部分につき，rust-analyzerによる補完が効きます．

`logos`

トークンを一つのenumで表す（これをenum Tokenとします）ことを前提にし，derive(logos::Logos)を生やしてTokenの各メンバのattributeに&strからの対応を書くようです．一つのメンバにつき複数の対応を書くことができ，クロージャをその場で書けたり関数を呼べたりするみたいです．attributeの内部に書くのはrust-analyzerが何も言ってくれないので微妙そう．pure rustで書いた関数を呼べる上に戻り値の型で簡単に制御を表せる点はとても良いですね．callbackの戻り値はenumに包まれていないのでテストも分離しやすい．

Tokenのメンバについたattributeについて，入力を読んで正規表現とのマッチに成功した際に実行されるクロージャや関数は，lex: &mut logos::Lexer<Token>を引数にとり，マッチした文字列はlex.slice()により獲得します．

nested commentに対応するには，plexで考えた実装と同じようなことをすればよいです．2つのenumにLogosを生やして，コメントの開始のcallbackでlogos::Lexer::remainder(&self)（lex.slice()より後の文字列を返す）とかlogos::Lexer::bump(&mut self, n: usize)（n文字進める）を呼んでいい感じにします．コメントを飛ばす処理はスクラッチした方が簡単だと思います．

位置情報はbyte posしか取れないみたいです．

速いことは確かなようで，lookup tableとかを自分で実装する手間もないため，単純な字句解析がしたいならこれで十分そうです．使い方を知るのが大変寄り．

parser as lexer

parser generatorにlexerを生成させることを考えます．可能というだけで効率が良いわけでは決してなさそうなので軽く．nested commentは違いますけど，正規言語の範囲ならふつうバックトラックが不要なのでpegやcombineでも本領発揮できるはずで，nomのように入力をバケツリレーするとかえってわかりにくくなりそうなものです．この話おわり．logosかplex使おう．

parser

`nom`

現行のversion 7はコンビネータもしっかりサポートされており，だいぶcombineに似ているというか仕事を奪っている感じです．今回は関係ないけどstreamingに対応しているのが偉い．

parserの役割を担うのはnom::Parser<I, O, E>を実装する型であり，このtraitのfn parse(&mut self, input: I) -> nom::IResult<I, O, E>がparseを行います．IResultはpub type IResult<I, O, E = Error<I>> = Result<(I, O), nom::Err<E>>;のことで，

nomの長所である，Iが&[u8]や&strであるparserが多いということが入力の型を任意にしようとすると活かせません．それでもandやorはnom::Parserにくっついているのでそんな不自由することでもないし，トークンに対するパターンマッチを実行するのも容易です．

pomはnomの下位互換だと思うので紹介しません．

`combine`

parsecを元にしているだけあってトレイトが重く使われており，入力もそんな感じです．

parserの役割を担うのはcombine::Parser<Input: combine::Stream>を実装する型であり，このtraitのfn parse(&mut self, input: Input) -> Result<(Self::Output, Input), <Input as StreamOnce>::Error>がparseを行います．combine::Streamはpub trait Stream: combine::StreamOnce + combine::stream::ResetStream + combine::Positioned { }であり，特にcombine::StreamOnceでSelf::Token: Cloneが課せられています．提供されている実装は&strとimpl<'a, T> StreamOnce for &'a [T] where T: Clone + PartialEq （と&mut版）に対してで，一応そこそこ自由な入力ができることがわかります．もちろんpub traitなので実装もできます．

docs.rs

入力の型を変えるとコンビネータしか使えなくなるのはnomと同じで，違うのはResult::<T, E>のTのタプルの順と，しれっと付いているToken: Cloneです．トークン列のスライスを入力にすればいいだけですけど，attemptを頻繁に使いたいような場合，選ぶならnomでしょうか．

try operatorはいいですね．やっぱりparsecが書きやすく読みやすいのはコンビネータ中心であることよりdo記法に依るところが大きいと思います．使うことに関してのモナドはみんなそうか．

`peg`

入力に&[T] where T: Copyを選べます．正確にはruleで用いる機能ごとにpeg::ParseElem（パターンマッチ）, peg::ParseLiteral（リテラル（これはlalrpopに似ている））, peg::ParseSlice（マッチする入力のスライスを返す）の3つのtraitがあり，それぞれを実装するものがその機能を利用できます．使わない機能のtraitを実装しないことができます．T: 'input + Copyに対して[T]へのこれらのtraitがすでにimplされています．T: Copyは次のように参照を渡せばトークンの型には要求されません．

https://github.com/kevinmehall/rust-peg/blob/df9b0caf6c9696f233bc6ea4e78afd893ec7ab02/tests/run-pass/tokens_struct.rs

ParseElemにrustのpatの文法が利用できます．charに対してパターンマッチというと聞こえが悪いですが，後置ifが使えるんですよね．

位置情報の取得は，規則で得た値の束縛と同じように行います．position!()をrule名が来る場所で使うとpeg::Parse::PositionReprが束縛できます．トークン列の型Tokens: Parseに対し<Tokens as peg::Parse>::position_repr(&'input self, p: usize)を呼んでいるということです．

入力が正しい場合，rust-analyzerのsemantic highlightingがいい感じに効きます．規則にマッチした後実行されるコード部分の{,}内とruleの引数の(,)内は直のproc_macro2::TokenStreamなので補完も効きます．ruleの名前をそのまま関数名に使ってくれていないようで，go to definitionできないのが少しだけ残念．かなり気に入っています．

pestはpegの下位互換だと思うので紹介しません．

`plex`

plexもparserを作れます．入力は自由なenumにできるみたいですね．crate lalrが提供するLALR(1)状態の構成を使っているようで，そこでconflictが見つかるとエラーとするようです．lalrはpriority（？）が同一なreduce/reduce conflictと，全てのshift/reduce conflictをconflictとして報告します．precedenceとassociativityを反映する機能はなさそうでした．lalrpopの下位互換です．

`lalrpop`

lalrpopが入力とするのは，Writing a custom lexerに記載のある通り，pub type Spanned<Tok, Loc, Error> = Result<(Loc, Tok, Loc), Error>;をItemとするIterator<Item>です．ここでTok, Loc, Errorはユーザー定義の型であり，Loc: Clone以外のtrait制約はありません．文法は.lalrpopという拡張子のファイルに保存します．grammar<'input>;としておくと必要な箇所全てでこのライフタイムが使えるようになるため，TokやErrorが入力のライフタイムを持ち越せます．ちなみにclippyするとここまで紹介した機能でめっちゃ警告がでます．codegen部に#[allow()]差し込むだけでいいのに．

位置情報の取得は，規則で得た値の束縛と同じように行います．@Lや@Rを文法名が来る場所で使うとそれぞれ最左，最右の要素の左，右の位置が束縛できます．

名前に反してLR法を謳っており（LALRに弱めることはできる），まだ（2年間も）ドキュメント化されていないものの生成規則のprecedenceとassociativityを自動で解決する例の機能*2はあるのに，shift/reduce conflict, reduce/reduce conflictの解消方法を持たないんです．yaccはprecedenceとassociativityを指定することにより次の規則に従って勝手にreduceとshiftを選択してくれますが，lalrpopにはそれができません．.yの中身をただ置き換えるだけで動かないということに気づいたのがこれを選んで翻訳を終えた後で，結構ショックでした．目立つ場所に書いておいてほしい．うちではconflict解消やってません，って．

If there is a shift-reduce conflict and both the grammar rule and the input character have precedence and associativity associated with them, then the conflict is resolved in favor of the action -- shift or reduce -- associated with the higher precedence. If precedences are equal, then associativity is used. Left associative implies reduce; right associative implies shift; nonassociating implies error.

https://docs.oracle.com/cd/E19504-01/802-5880/6i9k05dh3/index.html

dangling ifのshift/reduce conflict解消ですら難しいのに，OCamlくらいの規模の文法で発生するconflictを解消するのがかなり骨の折れる作業で，これにかなり時間を持っていかれた記憶があります．次からは絶対pegの方使う．yaccの現代的なrust portとして十分輝けるだけに惜しいです．役割として被っていそうな，最近出てきたlrparはこれを読む限りreduce/reduce conflictを教えることはできるみたいです．yaccとの互換性がほしいならこっちを使ったほうがよさげ．

softdevteam.github.io

結び

この記事はこれで終わりです．実装の章がないので短めですね．

あ，ぼっち・ざ・ろっく！は観てくださいね．最高のアニメでした．

ISer Advent Calendar 2022に記事を書いてくれた21er, 22er, 23erの方々，ありがとうございました！

*1:え？そんなにネストしたコメントが嫌なら字句解析の前に処理すればよいのでは，だって？そうですね．それをCPU実験の担当者がコードを配布する前にしてくれればよかったんですけどね（カウンター）．今度交渉してみます．

*2:このPR https://github.com/lalrpop/lalrpop/pull/555 を参照

f03d-5bab's blog

物置

RustでOCamlのパーサーを書くために

要旨

動機

比較

lexer

`plex`

`logos`

parser as lexer

parser

`nom`

`combine`

`peg`

`plex`

`lalrpop`

結び