Whitespace言語のパースにおけるレキサー実装

Whitespace言語をパースする際、次のような文法構造を想定します：

pub Program = <Statement*>;

Statement: ast::Stmt = {
    " " <StackOp>,
    "\t" " " <MathOp>,
    "\t" "\t" <HeapOp>,
    "\n" <FlowCtrl>,
    "\t" "\n" <Io>,
};

StackOp: ast::Stmt = {
    " " <Number> => ast::Stmt::Push(<>),
    "\n" " " => ast::Stmt::Dup,
    "\t" " " <Number> => ast::Stmt::Copy(<>),
    "\n" "\t" => ast::Stmt::Swap,
    "\n" "\n" => ast::Stmt::Discard,
    "\t" "\n" <Number> => ast::Stmt::Slide(<>),
};

LALRPOPがデフォルトで生成するトークナイザは空白文字をすべてスキップしてしまうため、この構文は動作しません。今回は空白文字をトークンとして扱い、他の文字はコメントとして無視する必要があります。

ストリーム形式の定義

パーサーは次のような構造のイテレータを受け取ります：

pub type Spanned<Tok, Loc, Error> = Result<(Loc, Tok, Loc), Error>;

ここで： - Loc は入力文字列内のバイトオフセットを表すusize - Error は任意のエラータイプ - Tok はストリーム内のトークン値

トークンの定義

Whitespace言語では次の3つのトークンのみが有効です：

pub enum Tok {
    Space,
    Tab,
    Linefeed,
}

その他の文字はすべてコメントとして扱います。構文エラーは発生しないため、空の列挙型でエラータイプを定義します：

pub enum LexicalError {}

レキサーの実装

文字列スライスを入力とするレキサーを実装します：

use std::str::CharIndices;

pub struct Lexer<'input> {
    chars: CharIndices<'input>,
}

impl<'input> Lexer<'input> {
    pub fn new(input: &'input str) -> Self {
        Lexer { chars: input.char_indices() }
    }
}

次のようなルールでトークンを生成します：

• ' ' → Tok::Space
• '\t' → Tok::Tab
• '\n' → Tok::Linefeed
• それ以外の文字はスキップ
• 文字列末尾に到達したらNoneを返してEOFを通知

このルールを元に、Iteratorトレイトを実装します：

impl<'input> Iterator for Lexer<'input> {
    type Item = Spanned<Tok, usize, LexicalError>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.chars.next() {
                Some((i, ' ')) => return Some(Ok((i, Tok::Space, i+1))),
                Some((i, '\t')) => return Some(Ok((i, Tok::Tab, i+1))),
                Some((i, '\n')) => return Some(Ok((i, Tok::Linefeed, i+1))),
                None => return None,
                _ => continue,
            }
        }
    }
}

LALRPOPとの連携

LALRPOPでこのレキサーを使用するため、次のようにexternブロックを定義します：

extern {
    type Location = usize;
    type Error = lexer::LexicalError;

    enum lexer::Tok {
        " " => lexer::Tok::Space,
        "\t" => lexer::Tok::Tab,
        "\n" => lexer::Tok::Linefeed,
    }
}

これにより、パーサーは文字列スライスではなくLexerを受け取るようになります：

let lexer = lexer::Lexer::new("\n\n\n");
match parser::parse_Program(lexer) {
    // ...
}