カスタム字句解析器を実装する際、生成されるトークンに元の入力文字列への参照を持たせる設計が有効な場合があります。変数名や識別子などの任意の記号を扱う構文木を構築する際、文字列データを複製せず参照を保持することで、メモリアロケーションの削減と解析速度の向上が実現できます。

抽象構文木の定義

まず、識別子を含む計算機の抽象構文木を定義します。数値リテラルと変数名を同じく文字列スライスとして扱える構造を採用し、所有権の複製を避けます。

pub enum SyntaxTree<'src> {
    Identifier(&'src str),
    BinaryOp(Box<SyntaxTree<'src>>, ArithOp, Box<SyntaxTree<'src>>),
    Invalid,
}

トークン型の設計

次に、字句解析器が返すトークンを定義します。`Identifier` バリアントが入力文字列への参照を保持している点に注目してください。

#[derive(Clone, Copy, Debug)]
pub enum TokenKind<'src> {
    Identifier(&'src str),
    AddOrSub(ArithOp),
    MulOrDiv(ArithOp),
    LeftParen,
    RightParen,
}

字句解析器の実装

トークンにスライスを含めるため、レキサ自体が入力文字列への参照を保持する必要があります。

use std::iter::Peekable;
use std::str::CharIndices;

pub struct SourceRefLexer<'src> {
    iter: Peekable<CharIndices<'src>>,
    source: &'src str,
}

impl<'src> SourceRefLexer<'src> {
    pub fn new(src: &'src str) -> Self {
        Self {
            iter: src.char_indices().peekable(),
            source: src,
        }
    }
}

Iterator トレイトを実装し、文字列スキャンを行ないます。区切り文字（演算子や括弧、空白）を検出するまで文字を消費し、該当範囲を参照としてトークンに格納します。

impl<'src> Iterator for SourceRefLexer<'src> {
    type Item = Spanned<TokenKind<'src>, usize, ()>;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some((idx, ch)) = self.iter.next() {
            match ch {
                ' ' | '\n' | '\t' => continue,
                ')' => return Some(Ok((idx, TokenKind::RightParen, idx + 1))),
                '(' => return Some(Ok((idx, TokenKind::LeftParen, idx + 1))),
                '+' => return Some(Ok((idx, TokenKind::AddOrSub(ArithOp::Add), idx + 1))),
                '-' => return Some(Ok((idx, TokenKind::AddOrSub(ArithOp::Sub), idx + 1))),
                '*' => return Some(Ok((idx, TokenKind::MulOrDiv(ArithOp::Mul), idx + 1))),
                '/' => return Some(Ok((idx, TokenKind::MulOrDiv(ArithOp::Div), idx + 1))),
                _ => {
                    let mut head = idx;
                    let mut tail = head + 1;
                    while let Some((&next_pos, next_ch)) = self.iter.peek() {
                        if matches!(next_ch, ')' | '(' | '+' | '-' | '*' | '/' | ' ') {
                            break;
                        }
                        self.iter.next();
                        tail = next_pos + next_ch.len_utf8();
                    }
                    return Some(Ok((head, TokenKind::Identifier(&self.source[head..tail]), tail)));
                }
            }
        }
        None
    }
}

文法定義

LALRPOP の文法ファイルでは、生成されるパーサが借用チェッカーの問題を回避できるよう、明示的に入力のライフタイムを指定します。

grammar<'src>(src: &'src str);

extern {
    type Location = usize;
    type Error = ();

    enum TokenKind<'src> {
        "num" => TokenKind::Identifier(<&'src str>),
        "AddOrSub" => TokenKind::AddOrSub(<ArithOp>),
        "MulOrDiv" => TokenKind::MulOrDiv(<ArithOp>),
        "(" => TokenKind::LeftParen,
        ")" => TokenKind::RightParen,
    }
}

Term: Box<SyntaxTree<'src>> = {
    "num" => Box::new(SyntaxTree::Identifier(<>)),
    "(" <Expr> ")",
};

パーサの実行

定義したレキサとパーサを連携させて実行します。構文解析時に元文字列への参照が適切に伝播するため、追加のメモリ確保なしにASTが構築されます。

let source_text = "22 * pi + 66";
let lexer_instance = SourceRefLexer::new(source_text);
let ast = calculator_module::ExprParser::new()
    .parse(source_text, lexer_instance)
    .expect("Failed to parse");
assert_eq!(&format!("{:?}", ast), r#"(("22" * "pi") + "66")"#);