Rust で Nested Comment に対応したパーサーを書く

この記事は TSG Advent Calendar 2021 の 18 日目の記事です。 ~~この記事を執筆しているのは年末ですが (本当)、年内は Advent なので (大嘘) セーフです (大嘘)。~~ 寝ていたら新年になっていました。議論の余地なくアウトです。

三行で要約

Rust で
Nested Comment に対応した言語処理系を書くときには
plex と lalrpop を組み合わせると楽

はじめに

情報系のオタクが自作したいもの TOP3 といえば古来から相場が決まっており「CPU・OS・プログラミング言語」です。特にその中でも「プログラミング言語を作る」というのは自分のパソコン一台あればよく¹、また OS を作るのに比べて調べることが少ないという点でお手軽です²。

また最近は色々なプロダクトを Rust で作るのがブームになっています (要出典)。となるとやはり人は Rust で言語処理系を作りたくなるものでしょう。なるものとします。

さて、プログラミング言語を自作しようと思ったとき、ぜひとも導入したい言語機能があります。そう、Nested Comment です！³ (後述) ところがこの Nested Comment はかなり曲者の仕様であり, 巷によくあるモダンな感じのパーサーコンビネーターでは対応できません。検証はしていませんが、高機能な Document Comment を言語機能で組み込む場合なども同様の問題を抱えています。

というわけで、この記事では Rust で Nested Comment に対応した言語処理系を手軽に作る方法を書いていきます。

前提知識

本題に入る前に、そのために必要な前提知識を大まかに解説します。既に分かっている人は実装の章まで飛ばしてしまって大丈夫です

パーサーとレキサー

まず、プログラミング言語のコンパイラを作ろうと思ったとき、その基本的な流れは以下のようになります。(インタプリタでも 5 番以外はほぼ同様です)

レキサー (字句解析器) を作る
パーサー (構文解析器) を作る
型推論を行う (型付き言語のみ)
抽象構文木を適当に変換して最適化する
最適化した抽象構文木をアセンブリ (または LLVM-IL 等の中間表現) として出力する

ここでレキサーとは文字列で与えられたソースコードをトークン列に変換するプログラムのことで, パーサーはそのトークン列を, プログラムとして意味が通るような構文木に変換するプログラムのことでした。

ここで「なぜレキサーとパーサーを分けるのか」という問が生じます。文字列から構文木を作れれば良いのですから, わざわざ間にトークン列を経由することなく、直接変換してしまえば良いのではないかということです。

なるほど確かにその通りなのですが、この考えには一つ重大な欠点があります。それは「言語の文法が複雑になりすぎる」ということです。

形式言語の理論では、言語の文法がある種の単純さを持っていると構文解析が少ない計算量 (例えば文字列長の線形オーダーや二乗のオーダー) で抑えられることが知られています。また一般に単純な文法はコードで記述するときにも単純になり、処理系のバグが減って保守性も向上することが期待されます。

直感的に理解したければ、自然言語の例を考えても良いでしょう。例えば I have a pen という文字列を英語として解釈するとき、普通はこの文字列を [I, have, a, pen] という4つの単語に分割してから、英語の文法に則って文章の意味を判断するでしょう。もし英文法が「"I" の後に " " があって、その後に "h" が来たら……」のように一文字単位で記述されていたら、その英文法書はとんでもない厚みになる上に柔軟性の無いものになってしまう⁴ はずです。⁵

そんな事情で一般的な言語処理系では、文字列をトークン (単語) の列に分解するレキサーと、トークン列を構文木に変換するパーサー。という役割分担を行うことで言語処理系の実装の単純さと構文解析の高速さを確保しています。

レキサー/パーサージェネレーターについて

とはいえ、言語処理系を作るたびにレキサーやパーサーを一から手書きするのは面倒です。そのため世の中には、レキサーやパーサーの作成を支援するツールが数多く存在します。そしてそれらを総称して「レキサージェネレーター」や「パーサージェネレーター」と呼んでいるわけです。ツールによってはレキサーとパーサーでジェネレーターが別れておらず、一つの文法を記述すると勝手にレキサーとバーサーを両方とも生成してくれる場合もあります⁶。

そして重要なこととして、多くのパーサージェネレーターは扱う文法が LR(1) 文法であるという比較的緩い仮定をおいている一方で、レキサージェネレーターは効率の良いレキサーを生成するためにレキサーが 正規言語 を処理するという比較的強い仮定をおいているという事実があります。

Nested Comment とは

話は変わって、OCaml などの一部のプログラミング言語には Nested Comment という言語機能が存在します。これは以下のようなコメント文の記述を可能とする言語機能です。

(* This (* is a *) comment *)
print_string "hello, world!"

当たり前のコードに見えるかもしれませんが、例えば C++ で以下のようなコードを書くとエラーになります。

/* This /* is a */ comment */
std::cout << "hello, world!" << std::endl;

おわかりでしょうか。C++ だと 1 つ目の /* と 1 つ目の */ がコメントとして対応してしまい、上のコードで言う comment */ の部分が通常のコードとして扱われてしまうのです。それに対して OCaml のコードではネストした (* と *) の対応がとられ、しっかり comment *) の部分までがコメントとして扱われます。

Nested Comment の問題点

さて上記の Nested Comment は便利な仕様ですが、多くの言語に導入されない大きな理由が一つあります。それは「コメントがネストすると正規言語で表現できなくなる」という問題です。

通常の言語では、コメントというのはレキサーの段階で処理され、空文字列と同様の扱いになります。そして前述の通り一般的なレキサージェネレーターはレキサーが正規言語しか扱わないという仮定をおいています。

ところが、ネストした括弧列は正規言語では表現できないことが知られています。正規言語とはいわゆる「正規表現」で表される言語のことですが、形式言語理論における正規表現では「ネストした括弧」を表現できないことが示されています (後述に注)。

このため、そのへんの適当なレキサー/パーサージェネレーターを用いると、Nested Comment に対応することはできません。Nested Comment に対応するためには、もう少し「柔軟な」(または「美しくない」) レキサー/パーサージェネレーターを用いる必要があります。

(注) 紛らわしい点として、Perl や .NET 系などのプログラミング言語では、利便性のために「正規表現」として形式言語理論で言うところの「正規表現」よりも表現力の高い表現を処理できる実装がなされていて、ネストする括弧の対応も処理することができます⁷。Rust で標準的な regex クレートでもいくつかの便利な記法が追加されていますが、こちらは括弧列の対応などの強い表現はできません。

Rust のパーサージェネレーター事情

以上のことを踏まえ、ある程度名の知られている Rust のレキサー/パーサージェネレーターをいくつか独断と偏見で比較してみます。ソースコード上のロケーション情報を取得できるか否かを Span としています

名前	種類	`Span`	レキサーのカスタム	開発の活発さ	備考
nom	一体型	o	x	◎	おそらく最も有名
pom	一体型	x	x	o
combine	一体型	o	x	◎
pest	一体型	o	x	◎	PEG 形式。リッチなエラー報告付き
plex	両対応	o	◎	x	かなり素朴
lalrpop	一体型(*)	o	o	o	文法は独自形式のスクリプトで定義
peg	一体型	o	x	◎	PEG 形式。
logos	レキサーのみ	o	◎	o	珍しいレキサー特化型

ここで「一体型」とは、レキサーとパーサーのジェネレーターが分離していないことを指しています。ただし lalrpop は、デフォルトでは一体型であるものの、パーサージェネレーターのみを用いる (レキサーは自前で用意する) ことができるようになっています。

plex と LALRPOP

上の表を見ると、まずレキサーをカスタムできる選択肢が極端に少ないことに気が付きます⁸。多くのツール (crate) はレキサー/パーサージェネレーターの一体型であり、レキサーを Nested Comment に対応させることが難しいのです。したがってパーサージェネレーターは plex か lalrpop のものを使用せざるを得ません。

それではレキサーとパーサー両方のジェネレーターを両方備えている plex を使用すれば良いではないかと思うのですが、大きな問題として、plex のパーサージェネレーターは機能がかなり少ない上に、そもそもリポジトリが長らく更新されていません⁹。新しい機能が追加されることを期待するのは望み薄ですし、もしバグがあったとしても修正は遅れるでしょう。パーサージェネレーターとして plex を中心的に使いたくはありません。

結果としてパーサージェネレーターとして使えるのは lalrpop のみとなります。こちらは利用者も多く、開発も一応継続的に行われています。ドキュメントはほぼ更新されていませんが、issue を眺めると新機能の追加にもかなり積極的な様子が伺えます。

これで問題は「レキサージェネレーターに何を用いるか」です。といっても候補は plex と logos しかありません。logos はプロシージャルマクロを利用してレキサーを生成できるかなり良い感じの crate ではあるのですが、いかんせんドキュメントがほぼ Docs.rs しかありません。また issue を覗くと regex のマッチあたりで致命的なバグが放置されている様子があります。今回はレキサーには Nested Comment を追加する以外にはそこまで大規模な改造はしないため、不安定であるならば logos ほどモダンなクレートは不要でしょう。

したがって、ある程度枯れている¹⁰レキサージェネレーターとして plex を利用するのが良さそうです。

実装

さて、前置きと前提知識が長くなりました。やりたいことはレキサージェネレーターとして plex、パーサージェネレーターとして lalrpop を利用してNested Comment に対応した言語処理系を作ることです。そのデモとしてこれ以降では簡単なプログラミング言語を定義し、その言語を抽象構文木に変換するところまでを実装します。

なお実装した内容は、以下のリポジトリで公開しています。

github.com

作っていく言語

以下のような、変数名への結果の保存と呼び出しが可能な算術言語を作ってみましょう。ただし (* と *) で囲まれた箇所がコメントで、これが Nested Comment に対応しています。

(* x = 3 *)
let 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;

前準備

まず cargo new で新しいクレート nested-comment-demo を作り、rust のツールチェインを nightly ビルドに変更します。これは plex のビルドに nightly 限定の機能が必要だからです。

$ cargo new --bin nested-comment-demo
$ cd nested-comment-demo
$ rustup install nightly
$ rustup override add nightly

次に Cargo.toml の dependencies 以降を次のようにします。

[dependencies]
plex = "0.2.5"
lalrpop-util = "0.19.6"
regex = "1"
thiserror = "1.0"
anyhow = "1.0"

[build-dependencies]
lalrpop = "0.19.6"

ここでは plex と lalrpop に加えて、エラー出力のために anyhow や thiserror を追加しています。

Nested Comment に対応したレキサーを作る

まずは plex を用いてコメントに対応していないレキサーを作り、それに Nested Comment のサポートを追加します。

src/ 以下に types.rs というファイルを作り、その中身を以下のようにします。

// ソースコード中の位置情報を範囲で表す
pub type Span = (usize, usize);

#[derive(Debug, Clone, PartialEq)]
pub struct Spanned<T> {
    pub item: T,
    pub span: Span
}

impl<T> Spanned<T> {
    pub fn new(item: T, span: Span) -> Self {
        Self {
            item,
            span
        }
    }
}

// レキサーで用いるトークン
#[derive(Debug, Clone, PartialEq)]
pub enum Tok<'a> {
    Num(i64),
    Ident(&'a str),
    Plus,
    Minus,
    Star,
    Slash,
    LPar,
    RPar,
    Let,
    Equal,
    SemiColon,
    Print,
}

次に lexer.rs を作り、その中身に plex を用いてレキサーを定義していきます。ここではいくつかの正規表現のうち与えられた文字列から合致するものを最長一致でマッチする関数である next_token を、plex を用いて定義しています。逆に言うとそれ以外の部分は手書きなので、空白文字の読み飛ばしなども自分で書いていく必要があります。

今回はパーサーとして lalrpop を用いるので、レキサーは iterator を実装する型にした上で、その出力を

std::result::Result<(Loc, Tok, Loc), Error>;

という形式にする必要があります。ここで Loc はソースコード上の位置情報を表す型を、Tok と Error はそれぞれトークン型とユーザー定義のエラー型をそれぞれユーザーが任意に指定します。今回は

 std::result::Result<(usize, Tok<'a>, usize), Spanned<Error>>;

という形式になります。これを lexer::Result 型としてしまいましょう。

plex でのレキサーの書き方自体は単純なので、本家のリポジトリの examples を見ればなんとなく察せると思います。

use plex::lexer;
use thiserror::Error;

use crate::types::{ Spanned, Tok };

#[derive(Debug, Clone, PartialEq, Error)]
pub enum Error {
    #[error("unrecognized token `{0}`")]
    UnrecognizedToken(String),
    #[error("integer constant `{0}` is too large")]
    TooLargeInteger(String)
}

enum LexState<'a> {
    Token(Tok<'a>),
    Skip,
    Err(Error)
}

lexer! {
    fn next_token(text: 'input) -> LexState<'input>;

    r"[\t\n\r ]" => LexState::Skip,
    r"\+" => LexState::Token(Tok::Plus),
    r"\-" => LexState::Token(Tok::Minus),
    r"\*" => LexState::Token(Tok::Star),
    r"/" => LexState::Token(Tok::Slash),
    r"\(" => LexState::Token(Tok::LPar),
    r"\)" => LexState::Token(Tok::RPar),
    r"let" => LexState::Token(Tok::Let),
    r"=" => LexState::Token(Tok::Equal),
    r";" => LexState::Token(Tok::SemiColon),
    r"print" => LexState::Token(Tok::Print),
    r"[a-z][0-9A-Za-z_]*" => LexState::Token(Tok::Ident(text)),
    r"[0-9]+" => {
        if let Ok(i) = text.parse() {
            LexState::Token(Tok::Num(i))
        } else {
            LexState::Err(Error::TooLargeInteger(text.to_string()))
        }
    },
    r"." => LexState::Err(Error::UnrecognizedToken(text.to_owned()))
}

#[derive(Debug, Clone)]
pub struct Lexer<'input> {
    original: &'input str,
    remaining: &'input str
}

impl<'input> Lexer<'input> {
    pub fn new(s: &'input str) -> Self {
        Lexer {
            original: s,
            remaining: s,
        }
    }
}

// lalrpop が受理する形式に合わせる
type Result<'a> = std::result::Result<(usize, Tok<'a>, usize), Spanned<Error>>;

impl<'input> Iterator for Lexer<'input> {
    type Item = Result<'input>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let state = next_token(self.remaining);
            if state.is_none() {
                // EOF
                return None;
            }

            let (state, remaining) = state.unwrap();

            // 読んだ箇所を更新
            let lo = self.original.len() - self.remaining.len();
            let hi = self.original.len() - remaining.len();
            self.remaining = remaining;

            match state {
                LexState::Token(tok) => {
                    // 正しいトークンなら lalrpop が受理する形に変換
                    return Some(Ok((lo, tok, hi)));
                },
                LexState::Skip => continue, // 空白は読み飛ばす
                LexState::Err(e) => {
                    // エラーであればそれを返す
                    return Some(Err(Spanned::new(e, (lo, hi))));
                },
            }
        }
    }
}

それではこれに Nested Comment を対応させていきましょう。大まかな方針は「コメントが始まったらコメント中専用のレキサーの状態遷移を用いるようにする」です。まずは lexer.rs に以下のコードを追加します。

enum CommentState {
    ReOpen,
    Close,
    Continue
}

lexer! {
    fn comment_consume(_text: 'input) -> CommentState;
    
    r"\(\*" => CommentState::ReOpen,
    r"\*\)" => CommentState::Close,
    r"." => CommentState::Continue
}

そして LexState と lexer::Error の定義をそれぞれ以下のように変更します

#[derive(Debug, Clone, PartialEq, Error)]
pub enum Error {
    #[error("unclosed comment")]
    UnclosedComment, // 追加
    #[error("unrecognized token `{0}`")]
    UnrecognizedToken(String),
    #[error("integer constant `{0}` is too large")]
    TooLargeInteger(String)
}

// ...
// (中略)
// ...

enum LexState<'a> {
    Token(Tok<'a>),
    Skip,
    CommentBegin, // 追加
    Err(Error)
}

あとはこれに対応するため Lexer のメソッドを以下のように変更するだけです。

impl<'input> Lexer<'input> {
    pub fn new(s: &'input str) -> Self {
        Lexer {
            original: s,
            remaining: s,
        }
    }

    // コメント中で用いるレキサーの状態遷移
    // コメントの括弧が正しく対応しているかを返す
    fn skip_comment(&mut self) -> bool {
        loop {
            use CommentState::*;
            let state = comment_consume(self.remaining);
            if state.is_none() {
                // EOF
                return false;
            }
            
            let (state, remaining) = state.unwrap();

            self.remaining = remaining;                
            match state {
                ReOpen => {
                    if self.skip_comment() {
                        continue;
                    }
                    return false;
                },
                Close => {
                    return true;
                },
                Continue => continue
            }
        }
    }
}


impl<'input> Iterator for Lexer<'input> {
    type Item = Result<'input>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let state = next_token(self.remaining);
            if state.is_none() {
                // EOF
                return None;
            }

            let (state, remaining) = state.unwrap();

            // 読んだ箇所を更新
            let lo = self.original.len() - self.remaining.len();
            let hi = self.original.len() - remaining.len();
            self.remaining = remaining;

            match state {
                LexState::Token(tok) => {
                    // 正しいトークンなら lalrpop が受理する形に変換
                    return Some(Ok((lo, tok, hi)));
                },
                LexState::Skip => continue, // 空白は読み飛ばす
                LexState::Err(e) => {
                    // エラーであればそれを返す
                    return Some(Err(Spanned::new(e, (lo, hi))));
                },
                LexState::CommentBegin => { // 追加
                    if self.skip_comment() {
                        continue;
                    }
                    // コメントが閉じていない
                    return Some(Err(Spanned::new(Error::UnclosedComment, (lo, hi))));
                }
            }
        }
    }
}

これで無事 Nested Comment に対応したレキサーができました。

LALRPOP でパーサーを作る

レキサーができたので、あとはパーサーを作っていくだけです。基本は lalrpop のドキュメント通りなのですが、少しだけドキュメントにない便利な機能を使います。個々の細かい機能の解説はしませんので、lalrpop を知らないという方は雰囲気で察してください。

まず先ほど作った types.rs に抽象構文木を表す以下の型を追加します。

// 二項演算の種類
#[derive(Debug, Clone, PartialEq)]
pub enum BinOpKind {
    Add,
    Sub,
    Mul,
    Div,
}

// 式

#[derive(Debug, Clone, PartialEq)]
pub enum ExprKind<'a> {
    Num(i64),
    Var(&'a str),
    BinOp(BinOpKind, Box<Expr<'a>>, Box<Expr<'a>>),
}

pub type Expr<'a> = Spanned<ExprKind<'a>>;

// 文

#[derive(Debug, Clone, PartialEq)]
pub enum StmtKind<'a> {
    Let(&'a str, Box<Expr<'a>>),
    Print(Box<Expr<'a>>),
}

pub type Stmt<'a> = Spanned<StmtKind<'a>>;

あとは lalrpop を利用して文法を記述していきましょう。ただその前に、クレートのルート (src/ 以下ではない) に build.rs というファイルを作り、以下のコードを記述します。これは lalrpop が文法ファイルをコンパイルするためのものです。

extern crate lalrpop;

fn main() {
    lalrpop::process_root().unwrap();
}

次に src/ 以下に grammer.lalrpop を作り、以下のように文法を記述していきます。

このとき lalrpop のデフォルトのレキサーではなく自前のレキサーを用いるため、チュートリアルのこことここを参考に extern 節を書く必要があります。

また lalrpop のドキュメントにない機能なのですが、パーサー中では precedence と assoc という属性を用いて、ルールの優先順位と演算子の結合法則を指定することができます¹¹。

use crate::types::*;
use crate::lexer::Error as LexError;

grammar<'input>;
extern {
    type Location = usize;
    type Error = Spanned<LexError>;

    // lalrpop の構文定義中で使う「文字列⇒トークン」の置換表
    enum Tok<'input> {
        "(" => Tok::LPar,
        ")" => Tok::RPar,
        Num => Tok::Num(<i64>),
        Ident => Tok::Ident(<&'input str>),
        "-" => Tok::Minus,
        "+" => Tok::Plus,
        "*" => Tok::Star,
        "/" => Tok::Slash,
        "let" => Tok::Let,
        "=" => Tok::Equal,
        ";" => Tok::SemiColon,
        "print" => Tok::Print,
    }
}

TermOp: BinOpKind = {
    "+" => BinOpKind::Add,
    "-" => BinOpKind::Sub,
};

FactorOp: BinOpKind = {
    "*" => BinOpKind::Mul,
    "/" => BinOpKind::Div
};

Atom: Box<Expr<'input>> = {
    "(" <e:Term> ")" => e,
    <l:@L> <x:Num> <r:@R> => Box::new(Spanned::new(ExprKind::Num(x), (l, r))),
    <l:@L> <x:Ident> <r:@R> => Box::new(Spanned::new(ExprKind::Var(x), (l, r))),
}

Term: Box<Expr<'input>> = {
    #[precedence(level="0")]
    Atom,

    // * /
    #[precedence(level="1")]
    #[assoc(side="left")]
    <l:@L> <e1:Term> <op:FactorOp> <e2:Term> <r:@R> => Box::new(Spanned::new(ExprKind::BinOp(op, e1, e2), (l, r))),

    // + -
    #[precedence(level="2")]
    #[assoc(side="left")]
    <l:@L> <e1:Term> <op:TermOp> <e2:Term> <r:@R> => Box::new(Spanned::new(ExprKind::BinOp(op, e1, e2), (l, r))),
}

Statement: Stmt<'input> = {
    <l:@L> "let" <x: Ident> "=" <t:Term> ";" <r:@R> => Spanned::new(StmtKind::Let(x, t), (l, r)),
    <l:@L> "print" <t:Atom> ";" <r:@R> => Spanned::new(StmtKind::Print(t), (l, r)),
}

pub Program: Vec<Stmt<'input>> = {
    Statement => vec![<>],
    <mut p:Program> <s:Statement> => {
        p.push(s);
        p
    }
}

パーサーを呼び出す

これでレキサーとパーサーが定義できたので、あとはこの文法通りに与えられた文字列をパースするプログラムを追加するだけです。まずは src/ 以下に parser.rs を追加し、以下のプログラムを記述します。

use thiserror::Error;
use crate::types::{Stmt, Tok, Spanned};
use crate::lexer;

lalrpop_mod!(pub grammer);

type LalrpopError<'a> = lalrpop_util::ParseError<usize, Tok<'a>, Spanned<lexer::Error>>;

#[derive(Debug, Clone, PartialEq, Error)]
pub enum ErrorKind<'a> {
    #[error("parse error: unexpected end of file")]
    Eof,
    #[error("lexer error: {0}")]
    Lexical(lexer::Error),
    #[error("parse error: found extra token `{0:?}`")]
    ExtraToken(Tok<'a>),
    #[error("parse error: unrecognized token `{0:?}`, expected `{1}`")]
    UnrecognizedToken(Tok<'a>, String)
}

pub type Error<'a> = Spanned<ErrorKind<'a>>;

// lalrpop のエラーを自前のエラー型に変換
fn convert_error(err: LalrpopError) -> Error {
    match err {
        LalrpopError::InvalidToken { location } => Spanned::new(ErrorKind::Eof, (location, location)),
        LalrpopError::ExtraToken { token: (lo, tok, hi) } => Spanned::new(ErrorKind::ExtraToken(tok), (lo, hi)),
        LalrpopError::User { error } => Spanned::new(ErrorKind::Lexical(error.item), error.span),
        LalrpopError::UnrecognizedToken {
            token: (lo, tok, hi),
            expected
        } => {
            assert!(!expected.is_empty());
            // 最初の候補だけ見る
            let expected = expected[0].clone();

            Spanned::new(ErrorKind::UnrecognizedToken(tok, expected), (lo, hi))
        },
        LalrpopError::UnrecognizedEOF { location, .. } => Spanned::new(ErrorKind::Eof, (location, location)),
    }
}

pub fn parse<'input>(src: &'input str) -> Result<Vec<Stmt>, Error> {
    let lex = lexer::Lexer::new(src);
    let parser = grammer::ProgramParser::new();

    parser.parse(lex).map_err(convert_error)
}

lalrpop のエラーを隠蔽して自作のエラー型に変換していますが、本体はレキサーとパーサーを構築して呼び出すだけの parse 関数です。あとは main.rs を以下のように変更して、この parse 関数を呼び出すようにすれば終わりです。

mod types;
mod lexer;
mod parser;

use anyhow::{ Result, Context };

#[macro_use]
extern crate lalrpop_util;

fn load_file(path: &str) -> Result<String> {
    std::fs::read_to_string(path).context(format!("failed to open file: {}", path))
}

fn main() -> Result<()> {
    let path = "test.txt"; // ソースファイルへのパス
    let src = load_file(path)?;
    let ast = parser::parse(&src).map_err(|err| {
        anyhow::format_err!("[{}:{}:{}] {}", path, err.span.0, err.span.1, err.item)
    })?;
    println!("{:#?}", ast);
    Ok(())
}

最終的なクレートの構成は以下のようになります

nested-comment-demo/
├ src/
│ ├ main.rs
│ ├ types.rs
│ ├ lexer.rs
│ ├ parser.rs
│ └ grammer.lalrpop
├ build.rs
└ Cargo.toml

あとはクレートのルートに test.txt を以下の内容で作成し、cargo run すれば求める出力が得られていることが確認できるはずです (長いため省略)。

(* x = 3 *)
let 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;

なおこの記事のプログラムではレキサーとパーサーのみを実装し、インタプリタは実装していません。簡単に実装できると思いますので、興味がある人は実装してみてください (丸投げ)。

まとめ

以上のように、Nested Comment というそのへんのモダンなクレートでは扱いにくい仕様が入っていても、plex と lalrpop を利用すればそれなりに手軽にレキサーやパーサーを作れることができました¹²。

また、今回対応したのは Nested Comment という比較的マイナーな仕様でしたが、今回用いた手段と同様の策を用いることで、レキサーの改造が必要そうな諸々の仕様 (例: Document Comment) を自作言語に組み込みやすくなると思われます。

皆さんがレキサーやパーサーのような非本質的な部分¹³で躓くことなく、楽しく自作言語の処理系を作る一助になれば幸いです。

なおこの記事は、理情の CPU 実験において、min-caml という Nested Comment が入った言語のパーサーを作るために四苦八苦した僕の備忘録でもあります。

……2022年の目標は、アドカレで遅刻しないことです。

謎の基盤や FPGA を買わないで良いということ↩
つまり、みんなやろうということです↩
この記事は飛ばし記事であり、Nested Comment は実用上かなりマイナーな言語機能です。またおそらく採用する優先度が高い言語機能でもありません↩
例えば新しい単語が登場するたびに「文法」を書き換えなければなりません↩
言語によっては、レキサーとパーサーを分離できないことが知られています。例えば分かち書きをしない日本語では「ももももも。すももももも。」という文が「もも/も/もも。すもも/も/もも」なのか「もも/もも/も。す/もも/もも/も」なのか、構文解析なしに判断することは困難です↩
本記事ではこのような統合されたジェネレーターも「パーサージェネレーター」と呼称します↩
このために、形式言語理論で言う正規表現を regular expression、プログラミング言語が提供する「正規表現」を regex と言い分ける場合もあるようです↩
このような事情からかは分かりませんが、Rust で書かれた言語処理系はレキサーやパーサーを一から手書きしているものが結構あるようです↩
記事執筆時点で最終コミットが 14 ヶ月前↩
ここでは「モダンではないがある程度安定している」という意味↩
この issue を参照↩
もっと楽な方法があるよ！という方がいましたら、気になるのでぜひ教えて下さい↩
言語の文法をどうするかは非常に重要ですが、そのレキサーやパーサーの実装は基本的には作業です↩

進捗置き場というわけでもない場所

プログラミングしてる中で見つけたこととか

目次