Memo

メモ > 技術 > プログラミング言語: Rust > プログラミング言語（ruscal）
プログラミング言語（ruscal）

Rustで作るプログラミング言語 ―コンパイラ／インタプリタの基礎からプログラミング言語の新潮流まで：書籍案内｜技術評論社
https://gihyo.jp/book/2024/978-4-297-14192-9

GitHub - msakuta/ruscal: Programming language implementation learning project
https://github.com/msakuta/ruscal

以下のとおり、プロジェクトを作成する。

>cd C:\Users\refirio\Rust
>cargo new ruscal --bin
>cd ruscal

■構文へのマッチ

src/main.rs の内容を以下のようにする。

fn main() {
    let source = "123 world";
    println!(
        "source: {}, parsed: {:?}",
        source,
        ident(whitespace(number(source)))
    );
}

// スペースを認識する（文字列の先頭にあるスペースを取り除く）
fn whitespace(mut input: &str) -> &str {
    while matches!(
        input.chars().next(),   // 先頭の文字を取得（charsでイテレータを取得し、nextで最初の文字が参照される）
        Some(' ')   // 先頭の文字がスペースかどうか
    ) {
        let mut chars = input.chars();  // 文字列のイテレータを取得
        chars.next();   // 最初の文字を取得（この時点で、先頭のスペースが消費される）
        input = chars.as_str(); // 残りの文字列を再割り当て（この時点で、inputから先頭のスペースが取り除かれる）
    }
    input
}

fn ident(mut input: &str) -> &str {
    if matches!(
        input.chars().next(),
        Some(_x @ ('a'..='z' | 'A'..='Z'))  // 先頭の文字がアルファベットかどうか
    ) {
        while matches!(
            input.chars().next(),
            Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))  // 2文字目がアルファベットもしくは数字かどうか
        ) {
            let mut chars = input.chars();
            chars.next();
            input = chars.as_str();
        }
    }
    input
}

fn number(mut input: &str) -> &str {
    if matches!(
        input.chars().next(),
        Some(_x @ ('-' | '+' | '.' | '0'..='9'))    // 先頭の文字が数字かどうか（プラスマイナスの記号も含む）
    ) {
        while matches!(
            input.chars().next(),
            Some(_x @ ('.' | '0'..='9'))    // 2文字目が数字かどうか（プラスマイナスの記号は含まない）
        ) {
            let mut chars = input.chars();
            chars.next();
            input = chars.as_str();
        }
    }
    input
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_whitespace() {
        assert_eq!(whitespace("    "), "");
    }

    #[test]
    fn test_ident() {
        assert_eq!(ident("Adam"), "");
    }

    #[test]
    fn test_number() {
        assert_eq!(number("123.45 "), " ");
    }
}


以下のように実行できる。

>cargo run
source: 123 world, parsed: ""

※「_x」はパターンマッチに成功したときの値を一時的に保持する変数だが、今回は使用していない。
  詳細は「パターンマッチ」を参照。

■トークンの切り出し

src/main.rs の内容を以下のようにする。

fn main() {
    let input = "123 world";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "Hello World";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "      world";
    println!("source: {}, parsed: {:?}", input, source(input));
}

fn source(mut input: &str) -> Vec<Token> {
    let mut tokens = vec![];
    while !input.is_empty() {
        input = if let (next_input, Some(token)) = token(input) {
            tokens.push(token);
            next_input
        } else {
            break;
        }
    }
    tokens
}

#[derive(Debug, PartialEq, Eq)]
enum Token {
    Ident,
    Number,
}

fn token(i: &str) -> (&str, Option<Token>) {
    if let (i, Some(ident_res)) = ident(whitespace(i)) {
        return (i, Some(ident_res));
    }
    if let (i, Some(number_res)) = number(whitespace(i)) {
        return (i, Some(number_res))
    }
    (i, None)
}

// スペースを認識する（文字列の先頭にあるスペースを取り除く）
fn whitespace(mut input: &str) -> &str {
    while matches!(
        input.chars().next(),   // 先頭の文字を取得（charsでイテレータを取得し、nextで最初の文字が参照される）
        Some(' ')   // 先頭の文字がスペースかどうか
    ) {
        let mut chars = input.chars();  // 文字列のイテレータを取得
        chars.next();   // 最初の文字を取得（この時点で、先頭のスペースが消費される）
        input = chars.as_str(); // 残りの文字列を再割り当て（この時点で、inputから先頭のスペースが取り除かれる）
    }
    input
}

// アルファベットを認識する（文字列の先頭にあるアルファベットを取り除く）
fn ident(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        input.chars().next(),
        Some(_x @ ('a'..='z' | 'A'..='Z'))  // 先頭の文字がアルファベットかどうか
    ) {
        while matches!(
            input.chars().next(),
            Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))  // 2文字目がアルファベットもしくは数字かどうか
        ) {
            let mut chars = input.chars();
            chars.next();
            input = chars.as_str();
        }
        (input, Some(Token::Ident))
    } else {
        (input, None)
    }
}

// 数字を認識する（文字列の先頭にある数字を取り除く）
fn number(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        input.chars().next(),
        Some(_x @ ('-' | '+' | '.' | '0'..='9'))    // 先頭の文字が数字かどうか（プラスマイナスの記号も含む）
    ) {
        while matches!(
            input.chars().next(),
            Some(_x @ ('.' | '0'..='9'))    // 2文字目が数字かどうか（プラスマイナスの記号は含まない）
        ) {
            let mut chars = input.chars();
            chars.next();
            input = chars.as_str();
        }
        (input, Some(Token::Number))
    } else {
        (input, None)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_whitespace() {
        assert_eq!(whitespace("    "), "");
    }

    #[test]
    fn test_ident() {
        assert_eq!(ident("Adam"), ("", Some(Token::Ident)));
    }

    #[test]
    fn test_number() {
        assert_eq!(number("123.45 "), (" ", Some(Token::Number)));
    }
}


以下のように実行できる

>cargo run
source: 123 world, parsed: [Number, Ident]
source: Hello World, parsed: [Ident, Ident]
source:       world, parsed: [Ident]

■カッコによるグループ化

src/main.rs の内容を以下のようにする

fn main() {
    let input = "(123 456 world)";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "((car cdr) cdr)";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "()())))((()))";
    println!("source: {}, parsed: {:?}", input, source(input));
}

fn advance_char(input: &str) -> &str {
    let mut chars = input.chars();
    chars.next();
    chars.as_str()
}

fn peek_char(input: &str) -> Option<char> {
    input.chars().next()
}

fn source(mut input: &str) -> Vec<Token> {
    let mut tokens = vec![];
    while !input.is_empty() {
        input = if let (next_input, Some(token)) = token(input) {
            tokens.push(token);
            next_input
        } else {
            break;
        }
    }
    tokens
}

#[derive(Debug, PartialEq, Eq)]
enum Token {
    Ident,
    Number,
    LParen,
    RParen,
}

fn token(i: &str) -> (&str, Option<Token>) {
    if let (i, Some(ident_res)) = ident(whitespace(i)) {
        return (i, Some(ident_res));
    }
    if let (i, Some(number_res)) = number(whitespace(i)) {
        return (i, Some(number_res))
    }
    if let (i, Some(number_res)) = lparen(whitespace(i)) {
        return (i, Some(number_res))
    }
    if let (i, Some(number_res)) = rparen(whitespace(i)) {
        return (i, Some(number_res))
    }
    (whitespace(i), None)
}

// スペースを認識する（文字列の先頭にあるスペースを取り除く）
fn whitespace(mut input: &str) -> &str {
    while matches!(
        peek_char(input),
        Some(' ')   // 先頭の文字がスペースかどうか
    ) {
        input = advance_char(input);
    }
    input
}

// アルファベットを認識する（文字列の先頭にあるアルファベットを取り除く）
fn ident(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        peek_char(input),
        Some(_x @ ('a'..='z' | 'A'..='Z'))  // 先頭の文字がアルファベットかどうか
    ) {
        while matches!(
            peek_char(input),
            Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))  // 2文字目がアルファベットもしくは数字かどうか
        ) {
            input = advance_char(input);
        }
        (input, Some(Token::Ident))
    } else {
        (input, None)
    }
}

// 数字を認識する（文字列の先頭にある数字を取り除く）
fn number(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        peek_char(input),
        Some(_x @ ('-' | '+' | '.' | '0'..='9'))    // 先頭の文字が数字かどうか（プラスマイナスの記号も含む）
    ) {
        while matches!(
            peek_char(input),
            Some(_x @ ('.' | '0'..='9'))    // 2文字目が数字かどうか（プラスマイナスの記号は含まない）
        ) {
            input = advance_char(input);
        }
        (input, Some(Token::Number))
    } else {
        (input, None)
    }
}

// 左カッコを認識する（文字列の先頭にある左カッコを取り除く）
fn lparen(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        peek_char(input),
        Some('(')   // 先頭の文字が左カッコかどうか
    ) {
        input = advance_char(input);
        (input, Some(Token::LParen))
    } else {
        (input, None)
    }
}

// 右カッコを認識する（文字列の先頭にある右カッコを取り除く）
fn rparen(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        peek_char(input),
        Some(')')   // 先頭の文字が右カッコかどうか
    ) {
        input = advance_char(input);
        (input, Some(Token::RParen))
    } else {
        (input, None)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_whitespace() {
        assert_eq!(whitespace("    "), "");
    }

    #[test]
    fn test_ident() {
        assert_eq!(ident("Adam"), ("", Some(Token::Ident)));
    }

    #[test]
    fn test_number() {
        assert_eq!(number("123.45 "), (" ", Some(Token::Number)));
    }
}


以下のように実行できる。

>cargo run
source: (123 456 world), parsed: [LParen, Number, Number, Ident, RParen]
source: ((car cdr) cdr), parsed: [LParen, LParen, Ident, Ident, RParen, Ident, RParen]
source: ()())))((())), parsed: [LParen, RParen, LParen, RParen, RParen, RParen, RParen, LParen, LParen, LParen, RParen, RParen, RParen]

■木構造の構築

src/main.rs の内容を以下のようにする。

fn main() {
    let input = "Hello world";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "(123 456 ) world";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "((car cdr) cdr)";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "()())))((()))";
    println!("source: {}, parsed: {:?}", input, source(input));
}

fn advance_char(input: &str) -> &str {
    let mut chars = input.chars();
    chars.next();
    chars.as_str()
}

fn peek_char(input: &str) -> Option<char> {
    input.chars().next()
}

fn source(mut input: &str) -> (&str, TokenTree) {
    let mut tokens = vec![];
    while !input.is_empty() {
        input = if let Some((next_input, token)) = token(input) {
            match token {
                Token::LParen => {
                    let (next_input, tt) = source(next_input);
                    tokens.push(tt);
                    next_input
                }
                Token::RParen => {
                    return (next_input, TokenTree::Tree(tokens))
                }
                _ => {
                    tokens.push(TokenTree::Token(token));
                    next_input
                }
            }
        } else {
            break;
        }
    }
    (input, TokenTree::Tree(tokens))
}

#[derive(Debug, PartialEq)]
enum Token<'src> {
    Ident(&'src str),
    Number(f64),
    LParen,
    RParen,
}

#[derive(Debug, PartialEq)]
enum TokenTree<'src> {
    Token(Token<'src>),
    Tree(Vec<TokenTree<'src>>),
}

fn token(input: &str) -> Option<(&str, Token)> {
    if let Some(res) = ident(whitespace(input)) {
        return Some(res);
    }
    if let Some(res) = number(whitespace(input)) {
        return Some(res);
    }
    if let Some(res) = lparen(whitespace(input)) {
        return Some(res);
    }
    if let Some(res) = rparen(whitespace(input)) {
        return Some(res);
    }
    None
}

// スペースを認識する（文字列の先頭にあるスペースを取り除く）
fn whitespace(mut input: &str) -> &str {
    while matches!(
        peek_char(input),
        Some(' ')   // 先頭の文字がスペースかどうか
    ) {
        input = advance_char(input);
    }
    input
}

// アルファベットを認識する（文字列の先頭にあるアルファベットを取り除く）
fn ident(mut input: &str) -> Option<(&str, Token)> {
    let start = input;
    if matches!(
        peek_char(input),
        Some(_x @ ('a'..='z' | 'A'..='Z'))  // 先頭の文字がアルファベットかどうか
    ) {
        while matches!(
            peek_char(input),
            Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))  // 2文字目がアルファベットもしくは数字かどうか
        ) {
            input = advance_char(input);
        }
        Some((
            input,
            Token::Ident(&start[..(start.len() - input.len())]),
        ))
    } else {
        None
    }
}

// 数字を認識する（文字列の先頭にある数字を取り除く）
fn number(mut input: &str) -> Option<(&str, Token)> {
    let start = input;
    if matches!(
        peek_char(input),
        Some(_x @ ('-' | '+' | '.' | '0'..='9'))    // 先頭の文字が数字かどうか（プラスマイナスの記号も含む）
    ) {
        while matches!(
            peek_char(input),
            Some(_x @ ('.' | '0'..='9'))    // 2文字目が数字かどうか（プラスマイナスの記号は含まない）
        ) {
            input = advance_char(input);
        }
        if let Ok(num) = start[..(start.len() - input.len())].parse::<f64>() {
            Some((input, Token::Number(num)))
        } else {
            None
        }
    } else {
        None
    }
}

// 左カッコを認識する（文字列の先頭にある左カッコを取り除く）
fn lparen(mut input: &str) -> Option<(&str, Token)> {
    if matches!(
        peek_char(input),
        Some('(')   // 先頭の文字が左カッコかどうか
    ) {
        input = advance_char(input);
        Some((input, Token::LParen))
    } else {
        None
    }
}

// 右カッコを認識する（文字列の先頭にある右カッコを取り除く）
fn rparen(mut input: &str) -> Option<(&str, Token)> {
    if matches!(
        peek_char(input),
        Some(')')   // 先頭の文字が右カッコかどうか
    ) {
        input = advance_char(input);
        Some((input, Token::RParen))
    } else {
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_whitespace() {
        assert_eq!(whitespace("    "), "");
    }

    #[test]
    fn test_ident() {
        assert_eq!(ident("Adam"), Some(("", Token::Ident("Adam"))));
    }

    #[test]
    fn test_number() {
        assert_eq!(number("123.45 "), Some((" ", Token::Number(123.45))));
    }
}


以下のように実行できる。

>cargo run
source: Hello world, parsed: ("", Tree([Token(Ident("Hello")), Token(Ident("world"))]))
source: (123 456 ) world, parsed: ("", Tree([Tree([Token(Number(123.0)), Token(Number(456.0))]), Token(Ident("world"))]))
source: ((car cdr) cdr), parsed: ("", Tree([Tree([Tree([Token(Ident("car")), Token(Ident("cdr"))]), Token(Ident("cdr"))])]))
source: ()())))((())), parsed: ("))((()))", Tree([Tree([]), Tree([])]))

■式の構文木

src/main.rs の内容を以下のようにする。

fn main() {
    let input = "123";
    println!("source: {}, parsed: {:?}", input, expr(input));

    let input = "Hello + world";
    println!("source: {}, parsed: {:?}", input, expr(input));

    let input = "(123 + 456 ) + world";
    println!("source: {}, parsed: {:?}", input, expr(input));

    let input = "car + cdr + cdr";
    println!("source: {}, parsed: {:?}", input, expr(input));

    let input = "((1 + 2) + (3 + 4)) + 5 + 6";
    println!("source: {}, parsed: {:?}", input, expr(input));
}

fn advance_char(input: &str) -> &str {
    let mut chars = input.chars();
    chars.next();
    chars.as_str()
}

fn peek_char(input: &str) -> Option<char> {
    input.chars().next()
}

#[derive(Debug, PartialEq)]
enum Expression<'src> {
    Ident(&'src str),
    NumLiteral(f64),
    Add(Box<Expression<'src>>, Box<Expression<'src>>),
}

// 式の全体を処理する
fn expr(input: &str) -> Option<(&str, Expression)> {
    if let Some(res) = add(input) {
        return Some(res);
    }
    if let Some(res) = term(input) {
        return Some(res);
    }
    None
}

// カッコで囲まれた式を処理する
fn paren(input: &str) -> Option<(&str, Expression)> {
    let next_input = lparen(whitespace(input))?;

    let (next_input, expr) = expr(next_input)?;

    let next_input = rparen(whitespace(next_input))?;

    Some((next_input, expr))
}

// 加算演算の左側を処理する
fn add_term(input: &str) -> Option<(&str, Expression)> {
    let (next_input, lhs) = term(input)?;
    let next_input = plus(whitespace(next_input))?;

    Some((next_input, lhs))
}

// 加算式を処理する
fn add(mut input: &str) -> Option<(&str, Expression)> {
    let mut left = None;
    while let Some((next_input, expr)) = add_term(input) {
        if let Some(prev_left) = left {
            left = Some(Expression::Add(
                Box::new(prev_left),
                Box::new(expr),
            ))
        } else {
            left = Some(expr);
        }
        input = next_input
    }

    let left = left?;
    let (next_input, rhs) = expr(input)?;

    Some((
        next_input,
        Expression::Add(Box::new(left), Box::new(rhs)),
    ))
}

// 項を処理する
fn term(input: &str) -> Option<(&str, Expression)> {
    if let Some(res) = paren(input) {
        return Some(res)
    }
    if let Some(res) = token(input) {
        return Some(res)
    }
    None
}

// 文字列を処理する
fn token(input: &str) -> Option<(&str, Expression)> {
    if let Some(res) = ident(whitespace(input)) {
        return Some(res);
    }
    if let Some(res) = number(whitespace(input)) {
        return Some(res);
    }
    None
}

// スペースを認識する（文字列の先頭にあるスペースを取り除く）
fn whitespace(mut input: &str) -> &str {
    while matches!(
        peek_char(input),
        Some(' ')   // 先頭の文字がスペースかどうか
    ) {
        input = advance_char(input);
    }
    input
}

// アルファベットを認識する（文字列の先頭にあるアルファベットを取り除く）
fn ident(mut input: &str) -> Option<(&str, Expression)> {
    let start = input;
    if matches!(
        peek_char(input),
        Some(_x @ ('a'..='z' | 'A'..='Z'))  // 先頭の文字がアルファベットかどうか
    ) {
        while matches!(
            peek_char(input),
            Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))  // 2文字目がアルファベットもしくは数字かどうか
        ) {
            input = advance_char(input);
        }
    }
    if start.len() == input.len() {
        None
    } else {
        Some((
            input,
            Expression::Ident(&start[..(start.len() - input.len())]),
        ))
    }
}

// 数字を認識する（文字列の先頭にある数字を取り除く）
fn number(mut input: &str) -> Option<(&str, Expression)> {
    let start = input;
    if matches!(
        peek_char(input),
        Some(_x @ ('-' | '+' | '.' | '0'..='9'))    // 先頭の文字が数字かどうか（プラスマイナスの記号も含む）
    ) {
        while matches!(
            peek_char(input),
            Some(_x @ ('.' | '0'..='9'))    // 2文字目が数字かどうか（プラスマイナスの記号は含まない）
        ) {
            input = advance_char(input);
        }
        if let Ok(num) = start[..(start.len() - input.len())].parse::<f64>() {
            Some((input, Expression::NumLiteral(num)))
        } else {
            None
        }
    } else {
        None
    }
}

// 左カッコを認識する（文字列の先頭にある左カッコを取り除く）
fn lparen(input: &str) -> Option<&str> {
    if matches!(
        peek_char(input),
        Some('(')   // 先頭の文字が左カッコかどうか
    ) {
        Some(advance_char(input))
    } else {
        None
    }
}

// 右カッコを認識する（文字列の先頭にある右カッコを取り除く）
fn rparen(input: &str) -> Option<&str> {
    if matches!(
        peek_char(input),
        Some(')')   // 先頭の文字が右カッコかどうか
    ) {
        Some(advance_char(input))
    } else {
        None
    }
}

// プラスを認識する（文字列の先頭にあるプラスを取り除く）
fn plus(input: &str) -> Option<&str> {
    if matches!(
        peek_char(input),
        Some('+')   // 先頭の文字がプラスかどうか
    ) {
        Some(advance_char(input))
    } else {
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_whitespace() {
        assert_eq!(whitespace("    "), "");
    }

    #[test]
    fn test_ident() {
        assert_eq!(ident("Adam"), Some(("", Expression::Ident("Adam"))));
    }

    #[test]
    fn test_number() {
        assert_eq!(number("123.45 "), Some((" ", Expression::NumLiteral(123.45))));
    }
}


以下のように実行できる。

>cargo run
source: 123, parsed: Some(("", NumLiteral(123.0)))
source: Hello + world, parsed: Some(("", Add(Ident("Hello"), Ident("world"))))
source: (123 + 456 ) + world, parsed: Some(("", Add(Add(NumLiteral(123.0), NumLiteral(456.0)), Ident("world"))))
source: car + cdr + cdr, parsed: Some(("", Add(Add(Ident("car"), Ident("cdr")), Ident("cdr"))))
source: ((1 + 2) + (3 + 4)) + 5 + 6, parsed: Some(("", Add(Add(Add(Add(NumLiteral(1.0), NumLiteral(2.0)), Add(NumLiteral(3.0), NumLiteral(4.0))), NumLiteral(5.0)), NumLiteral(6.0))))

■パーサコンピュータ nom

「anyhow v1.0.86」を使用する。

nom - crates.io: Rust Package Registry
https://crates.io/crates/nom

Cargo.toml の「[dependencies]」部分に以下を追加する。

nom = "7.1.3"


src/main.rs の内容を以下のようにする。

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{
        alpha1, alphanumeric1, char, multispace0,
    },
    combinator::recognize,
    multi::{fold_many0, many0},
    number::complete::recognize_float,
    sequence::{delimited, pair},
    IResult,
};

fn main() {
    let input = "123";
    println!("source: {:?}, parsed: {:?}", input, expr(input));

    let input = "Hello + world";
    println!("source: {:?}, parsed: {:?}", input, expr(input));

    let input = "(123 + 456 ) + world";
    println!("source: {:?}, parsed: {:?}", input, expr(input));

    let input = "car + cdr + cdr";
    println!("source: {:?}, parsed: {:?}", input, expr(input));

    let input = "((1 + 2) + (3 + 4)) + 5 + 6";
    println!("source: {:?}, parsed: {:?}", input, expr(input));
}

#[derive(Debug, PartialEq, Clone)]
enum Token<'src> {
    Ident(&'src str),
    Number(f64),
}

#[derive(Debug, PartialEq, Clone)]
enum Expression<'src> {
    Value(Token<'src>),
    Add(Box<Expression<'src>>, Box<Expression<'src>>),
}

fn term(i: &str) -> IResult<&str, Expression> {
    alt((number, ident, parens))(i)
}

fn ident(input: &str) -> IResult<&str, Expression> {
    let (r, res) = delimited(multispace0, identifier, multispace0)(input)?;
    Ok((r, Expression::Value(Token::Ident(res))))
}

fn identifier(input: &str) -> IResult<&str, &str> {
    recognize(pair(
        alt((alpha1, tag("_"))),
        many0(alt((alphanumeric1, tag("_")))),
    ))(input)
}

fn number(input: &str) -> IResult<&str, Expression> {
    let (r, v) = delimited(multispace0, recognize_float, multispace0)(input)?;
    Ok((
        r,
        Expression::Value(Token::Number(v.parse().map_err(
            |_| {
                nom::Err::Error(nom::error::Error {
                    input,
                    code: nom::error::ErrorKind::Digit,
                })
            },
        )?)),
    ))
}

fn parens(i: &str) -> IResult<&str, Expression> {
    delimited(
        multispace0,
        delimited(tag("("), expr, tag(")")),
        multispace0
    )(i)
}

fn expr(i: &str) -> IResult<&str, Expression> {
    let (i, init) = term(i)?;

    fold_many0(
        pair(delimited(multispace0, char('+'), multispace0), term),
        move || init.clone(),
        |acc, (_op, val): (char, Expression)| {
            Expression::Add(Box::new(acc), Box::new(val))
        },
    )(i)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_number() {
        assert_eq!(expr("123"), Ok(("", Expression::Value(Token::Number(123.0)))));
    }

    #[test]
    fn test_ident() {
        assert_eq!(expr("hello"), Ok(("", Expression::Value(Token::Ident("hello")))));
    }
}


以下のように実行できる。

>cargo run
source: "123", parsed: Ok(("", Value(Number(123.0))))
source: "Hello + world", parsed: Ok(("", Add(Value(Ident("Hello")), Value(Ident("world")))))
source: "(123 + 456 ) + world", parsed: Ok(("", Add(Add(Value(Number(123.0)), Value(Number(456.0))), Value(Ident("world")))))
source: "car + cdr + cdr", parsed: Ok(("", Add(Add(Value(Ident("car")), Value(Ident("cdr"))), Value(Ident("cdr")))))
source: "((1 + 2) + (3 + 4)) + 5 + 6", parsed: Ok(("", Add(Add(Add(Add(Value(Number(1.0)), Value(Number(2.0))), Add(Value(Number(3.0)), Value(Number(4.0)))), Value(Number(5.0))), Value(Number(6.0)))))

■パーサコンピュータ nom（基本的な使い方を確認）

Rust: nom によるパーサー実装 - MOXBOX
https://hazm.at/mox/lang/rust/nom/index.html

nomの基本的な挙動を確認する。
「42abc」という文字が与えられたとして、digit1関数によって「42」という数値部分を取得する。
厳密には「前方一致する部分と、それ以降の部分に分割する」という挙動になる。

use nom::{
    character::complete::digit1,
    IResult,
};

fn main() {
    let input = "42abc";

    match number(input) {
        Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
        Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
    }
}

fn number(input: &str) -> IResult<&str, &str> {
    let (input, value) = digit1(input)?;

    Ok((input, value))
}


以下のとおり実行できる。

>cargo run
Input: "42abc", Parsed: "42", Remaining: "abc"

multispace0関数によって0文字以上の空白を取得できる。
これを組み合わせれば、以下のように数字部分のみを取得できる。

use nom::{
    character::complete::digit1,
    character::complete::multispace0,
    IResult,
};

fn main() {
    let input = "  42  ";

    match number(input) {
        Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
        Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
    }
}

fn number(input: &str) -> IResult<&str, &str> {
    let (input, _) = multispace0(input)?;
    let (input, value) = digit1(input)?;
    let (input, _) = multispace0(input)?;

    Ok((input, value))
}


以下のとおり実行できる

>cargo run
Input: "  42  ", Parsed: "42", Remaining: ""

delimited関数によって、複数の関数をひとまとめにして使用できる。
「multispace0, digit1, multispace0」を認識する関数を準備し、その関数に「input」という引数を渡して解析する。
なお、このように関数をひとまとめにできるのは、Rustにおける関数合成の文法によるもの。

use nom::{
    character::complete::digit1,
    character::complete::multispace0,
    sequence::delimited,
    IResult,
};

fn main() {
    let input = "  42  ";

    match number(input) {
        Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
        Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
    }
}

fn number(input: &str) -> IResult<&str, &str> {
    let (remaining, value) = delimited(
        multispace0,
        digit1,
        multispace0
    )(input)?;

    Ok((remaining, value))
}


さらに「Ok」部分を省略して、以下のように書くことができる。（結果は変わらず。）

use nom::{
    character::complete::digit1,
    character::complete::multispace0,
    sequence::delimited,
    IResult,
};

fn main() {
    let input = "  42  ";

    match number(input) {
        Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
        Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
    }
}

fn number(input: &str) -> IResult<&str, &str> {
    delimited(
        multispace0,
        digit1,
        multispace0
    )(input)
}


以下のとおり実行できる。

>cargo run
Input: "  42  ", Parsed: "42", Remaining: ""

基本的に、この形式で使われることになる。

■パーサコンピュータ nom（nomに付属する関数の挙動を確認）

Rust: nom によるパーサー実装 - MOXBOX
https://hazm.at/mox/lang/rust/nom/index.html

alpha1関数について確認する。
これは、1文字以上のアルファベット文字（a-zまたはA-Z）を検出するパーサー。
解析に成功すると、アルファベット文字の部分を返し、残りの文字列をタプルとして返す。

src/main.rs
use nom::character::complete::alpha1;
use nom::error::Error;

fn main() {
    let result = alpha1::<&str, Error<&str>>("hello123");
    println!("{:?}", result);
}


>cargo run
Ok(("123", "hello"))

alphanumeric1関数について確認する。
これは、1文字以上の英数字（アルファベットまたは数字）を検出するパーサー。
解析に成功すると、英数字の部分を返し、残りの文字列をタプルとして返す。

src/main.rs
use nom::character::complete::alphanumeric1;
use nom::error::Error;

fn main() {
    let result = alphanumeric1::<&str, Error<&str>>("hello123!");
    println!("{:?}", result);
}


>cargo run
Ok(("!", "hello123"))

char関数について確認する。
これは、特定の1文字を解析するパーサーを作成する。
今回の場合、char('a')は先頭の「a」を解析し、残りの文字列「bc」を返す。

src/main.rs
use nom::character::complete::char;
use nom::error::Error;

fn main() {
    let parse_a = char::<&str, Error<&str>>('a');
    let result = parse_a("abc");
    println!("{:?}", result);
}


>cargo run
Ok(("bc", 'a'))

multispace0関数について確認する。
これは、0文字以上の空白（スペース、タブ、改行）を検出するパーサー。
解析に成功すると、空白についての部分を返し、残りの文字列をタプルとして返す。

src/main.rs
use nom::character::complete::multispace0;
use nom::error::Error;

fn main() {
    let result = multispace0::<&str, Error<&str>>("  hello123");
    println!("{:?}", result);
}


>cargo run
Ok(("hello123", "  "))

delimited関数について確認する。
これは「開始部分」「メイン」「終了部分」を認識し、その「メイン」の内容を検出するパーサー。
カッコやスペースなどを無視して中間部分を抽出する処理を簡潔に書くことができる。
以下はカッコを無視して抽出する例。

src/main.rs
use nom::{
    bytes::complete::tag,
    character::complete::alphanumeric1,
    sequence::delimited,
    IResult,
};

fn main() {
    let input = "[hello123]";
    match parse_bracketed(input) {
        Ok((remaining, parsed)) => println!("Parsed: {:?}, Remaining: {:?}", parsed, remaining),
        Err(error) => println!("Error: {:?}", error),
    }
}

fn parse_bracketed(input: &str) -> IResult<&str, &str> {
    // 角括弧で囲まれた内容を抽出
    delimited(
        tag("["),         // 開始部分: "[" にマッチ
        alphanumeric1,    // メイン: 英数字にマッチ
        tag("]")          // 終了部分: "]" にマッチ
    )(input)
}


>cargo run
Parsed: "hello123", Remaining: ""

以下はスペースを無視して抽出する例。

src/main.rs
use nom::{
    character::complete::{multispace0, digit1},
    sequence::delimited,
    IResult,
};

fn main() {
    let input = "   123   ";
    match parse_number_with_spaces(input) {
        Ok((remaining, parsed)) => println!("Parsed: {:?}, Remaining: {:?}", parsed, remaining),
        Err(error) => println!("Error: {:?}", error),
    }
}

fn parse_number_with_spaces(input: &str) -> IResult<&str, &str> {
    delimited(
        multispace0,  // 前の空白を無視
        digit1,       // 数値部分を解析
        multispace0   // 後ろの空白を無視
    )(input)
}


>cargo run
Parsed: "123", Remaining: ""

■パーサコンピュータ nom（nomに付属する関数の挙動を確認した際の「::<T>」という書き方について）

パス演算子「::」の直後に型を指定すると、「この関数に対して型を明示的に指定して呼び出す」となる。
順を追って確認する。

以下は型を明示した関数の例。

// 大きい方の値を返す関数を定義
fn get_larger(a: i32, b: i32) -> i32 {
    if a > b {
        a
    } else {
        b
    }
}

fn main() {
    // 整数を渡して実行
    let larger_int = get_larger(10, 20);
    println!("Larger integer: {}", larger_int); // 20

    // 以下は型が異なるので実行できない
    //let larger_float = get_larger(1.5, 0.3);
    //println!("Larger float: {}", larger_float);
}


以下はジェネリクス型を使った関数の例。
このような関数がある場合に、型推論を使わないで呼び出し時に明示的に型を指定して実行できる。
（「PartialOrd」はトレイト境界（型の持つべき機能を明確にするための制約）で、Tが比較可能であることを保証するもの。
  これがあるおかげで、「a > b」のような比較演算ができる。
  このファイル内を「トレイト」で検索すると関連情報がある。）

// 大きい方の値を返す関数を定義
fn get_larger<T: PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn main() {
    // 整数を渡して実行
    let larger_int = get_larger(10, 20);
    println!("Larger integer: {}", larger_int); // 20

    // 浮動小数点数を渡して実行
    let larger_float = get_larger(1.5, 0.3);
    println!("Larger float: {}", larger_float); // 1.5

    // 型推論を使わないで呼び出し時に明示的に型を指定して実行
    let max_int = get_larger::<i32>(30, 50);
    let max_float = get_larger::<f64>(5.5, 3.2);
    println!("Larger integer: {}", max_int);    // 20
    println!("Larger float: {}", max_float);    // 5.5
}


なお「let result = alpha1::<&str, Error<&str>>("hello123");」のコードでは、型を指定する必要がある。
これを省略すると「cannot infer type of the type parameter `E` declared on the function `alpha1`」のエラーになる。
ただし通常「alt((alpha1, tag("_")))」のように使用されるため、そもそも型指定が問題になることは無いのだと思われる。

■パーサコンピュータ nom（recognize関数の挙動を確認）

recognize関数について確認する。
recognize関数を使わなければ、パースされた結果が構造化された状態で返される。
recognize関数を使うと、パースされた結果が元の文字列として返される。元の文字列として取得し、後で別の処理に使用することができる。

pair関数は2つのパーサーを順に実行し、両方が成功した場合にパースした部分を組み合わせて返す。
つまりalphanumeric1やdelimitedでのパース結果のように文字列が返されずに、タプルが返される。
他の関数と挙動を合わせるために、recognize関数で文字列として返すようにする…ということだと思われる。

以下はrecognize関数を使わない例。

use nom::{
    character::complete::{alpha1, digit1},
    sequence::pair,
    IResult,
};

fn main() {
    // サンプル入力
    let inputs = vec![
        "abc123",      // 有効な文字列: アルファベットはじまりのアルファベットと数字の組み合わせ
        "ab12cd34",    // 有効な文字列: アルファベットはじまりのアルファベットと数字の組み合わせ
        "456def",      // 数字はじまり
        "xyz",         // アルファベットのみ
        "789",         // 数字のみ
    ];

    // 各サンプル文字列に対してパーサーを実行
    for input in inputs {
        match parse_combined(input) {
            Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
            Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
        }
    }
}

// `recognize` を使わず、アルファベットと数字の組み合わせをパースし、構造を返す
fn parse_combined(input: &str) -> IResult<&str, (&str, &str)> {
    // `pair` によって、アルファベットと数字のペアを解析して返す
    pair(
        alpha1,    // 最初にアルファベットがある
        digit1     // その後に数字が続く
    )(input)
}


>cargo run
Input: "abc123", Parsed: ("abc", "123"), Remaining: ""
Input: "ab12cd34", Parsed: ("ab", "12"), Remaining: "cd34"
Input: "456def", Error: Error(Error { input: "456def", code: Alpha })
Input: "xyz", Error: Error(Error { input: "", code: Digit })
Input: "789", Error: Error(Error { input: "789", code: Alpha })

以下はrecognize関数を使った例。

use nom::{
    character::complete::{alpha1, digit1},
    sequence::pair,
    combinator::recognize,
    IResult,
};

fn main() {
    // サンプル入力
    let inputs = vec![
        "abc123",      // 有効な文字列: アルファベットはじまりのアルファベットと数字の組み合わせ
        "ab12cd34",    // 有効な文字列: アルファベットはじまりのアルファベットと数字の組み合わせ
        "456def",      // 数字はじまり
        "xyz",         // アルファベットのみ
        "789",         // 数字のみ
    ];

    // 各サンプル文字列に対してパーサーを実行
    for input in inputs {
        match parse_combined(input) {
            Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
            Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
        }
    }
}

// アルファベットと数字の組み合わせをパースし、その元の文字列全体を返す
fn parse_combined(input: &str) -> IResult<&str, &str> {
    // `recognize`を使って、パース成功部分の文字列全体を返す
    recognize(
        pair(
            alpha1,    // 最初にアルファベットがある
            digit1     // その後に数字が続く
        )
    )(input)
}


>cargo run
   Compiling example v0.1.0 (C:\Users\refirio\Rust\example)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.01s
     Running `target\debug\example.exe`
Input: "abc123", Parsed: "abc123", Remaining: ""
Input: "ab12cd34", Parsed: "ab12", Remaining: "cd34"
Input: "456def", Error: Error(Error { input: "456def", code: Alpha })
Input: "xyz", Error: Error(Error { input: "", code: Digit })
Input: "789", Error: Error(Error { input: "789", code: Alpha })

■パーサコンピュータ nom（identifier関数の挙動を確認）

identifier関数について確認する。
これは、識別子として有効な部分を解析するもの。
独自関数だが、単に「先頭の文字がアルファベットで、2文字目以降はアルファベットもしくは数字である」という判定をしているだけ。（アンダーバーも有効な文字とみなす。）

src/main.rs
use nom::{
    bytes::complete::tag,
    character::complete::{alpha1, alphanumeric1},
    combinator::recognize,
    multi::many0,
    sequence::pair,
    branch::alt,
    IResult,
};

fn main() {
    // サンプル文字列をテストする
    let test_strings = vec![
        "hello123",    // 有効な識別子
        "_variable",   // アンダースコアで始まる有効な識別子
        "123abc",      // 数字で始まる無効な識別子
        "a_b_c",       // 有効な識別子
        "var-1",       // 無効な識別子（ハイフンが含まれている）
        "func_name",   // 有効な識別子
    ];

    // 各テスト文字列について、identifier関数を使用して解析を行う
    for input in test_strings {
        match identifier(input) {
            Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
            Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
        }
    }
}

// 入力文字列を受け取り、識別子として有効な部分を解析する
fn identifier(input: &str) -> IResult<&str, &str> {
    recognize(                                      // 中にあるパーサーを実行し、パースした内容を返す
        pair(                                       // 2つのパーサーを順に実行し、両方が成功した場合にパースした部分を組み合わせて返す
            alt(                                    // いずれかのパーサーが成功するまで、順にパースを試みる
                (
                    alpha1,                         // 先頭から1文字以上のアルファベットを解析する
                    tag("_")                        // 指定された文字列を解析する
                )
            ),
            many0(                                  // 0回以上繰り返し使用できるパーサーを実行し、その結果をベクターとして返す
                alt(
                    (
                        alphanumeric1,              // 先頭から1文字以上のアルファベットまたは数字を解析する
                        tag("_")                    // 指定された文字列を解析する
                    )
                )
            ),
        )
    )(input)
}


>cargo run
Input: "hello123", Parsed: "hello123", Remaining: ""
Input: "_variable", Parsed: "_variable", Remaining: ""
Input: "123abc", Error: Error(Error { input: "123abc", code: Tag })
Input: "a_b_c", Parsed: "a_b_c", Remaining: ""
Input: "var-1", Parsed: "var", Remaining: "-1"
Input: "func_name", Parsed: "func_name", Remaining: ""

■パーサコンピュータ nom（number関数の挙動を確認）

number関数について確認する。
これは、識別子として認識された浮動小数点数をf64にパースして返す独自関数。

src/main.rs
use nom::{
    character::complete::multispace0,
    number::complete::recognize_float,
    sequence::delimited,
    IResult,
};

fn main() {
    // サンプル文字列をテストする
    let test_strings = vec![
        "123",            // 有効な整数
        "456.789",        // 有効な小数
        "  42.0  ",       // 前後にスペースがある有効な小数
        "-99",            // 負の整数
        "-3.14",          // 負の小数
        "abc",            // 無効な数値
    ];

    // 各テスト文字列について、number関数を使用して解析を行う
    for input in test_strings {
        match number(input) {
            Ok((remaining, parsed)) => println!("Input: {:?}, Parsed: {:?}, Remaining: {:?}", input, parsed, remaining),
            Err(error) => println!("Input: {:?}, Error: {:?}", input, error),
        }
    }
}

// 入力文字列を受け取り、識別子として認識された浮動小数点数をf64にパースして返す
fn number(input: &str) -> IResult<&str, f64> {
    let (remaining, value) = delimited(multispace0, recognize_float, multispace0)(input)?;
    let parsed_value: f64 = value.parse().map_err(|_| {
        nom::Err::Error(nom::error::Error {
            input,
            code: nom::error::ErrorKind::Digit,
        })
    })?;
    Ok((remaining, parsed_value))
}


>cargo run
Input: "123", Parsed: 123.0, Remaining: ""
Input: "456.789", Parsed: 456.789, Remaining: ""
Input: "  42.0  ", Parsed: 42.0, Remaining: ""
Input: "-99", Parsed: -99.0, Remaining: ""
Input: "-3.14", Parsed: -3.14, Remaining: ""
Input: "abc", Error: Error(Error { input: "abc", code: Char })

■パーサコンピュータ nom（map_errでのエラー処理部分を確認）

※nomとは直接関係ないが、number関数内で使われているmap_errの挙動について確認する。
※map_errの基本については、前述の「コンソールアプリケーション」内にある「エラーハンドリングの追加」を参照。

map_errを使わない場合、エラー処理は一例だが以下のようになる。
「input.parse::<i32>()」が失敗したとき、エラーメッセージを手動で処理している。

fn main() {
    //let input = "123";
    let input = "abc";
    match parse_number(input) {
        Ok(n) => println!("Parsed number: {}", n),
        Err(e) => println!("Error: {}", e),
    }
}

fn parse_number(input: &str) -> Result<i32, String> {
    match input.parse::<i32>() {
        Ok(n) => Ok(n),
        Err(_) => Err("Failed to parse the number".to_string()),
    }
}


map_errを使うと、以下のようにエラー処理を簡潔に書くことができる。
エラーハンドリングのコードが簡潔になり、Errの変換部分がより明確になる。

fn main() {
    //let input = "123";
    let input = "abc";
    match parse_number(input) {
        Ok(n) => println!("Parsed number: {}", n),
        Err(e) => println!("Error: {}", e),
    }
}

fn parse_number(input: &str) -> Result<i32, String> {
    //input.parse::<i32>().map_err(|_| "Failed to parse the number".to_string())
    input.parse::<i32>().map_err(
        |_| {
            "Failed to parse the number".to_string()
        }
    )
}


エラーは以下のようなものが返されることになる。
これにより、エラーが発生した場所（abc）とエラーの種類（nom::error::ErrorKind::Digit）が返される。
なおこのエラーは「数値として認識できなかった」というもの。

nom::Err::Error(nom::error::Error {
    input: "abc",
    code: nom::error::ErrorKind::Digit,
})
■パーサコンピュータ nom（expr関数の挙動を確認）

以下の関数を理解するため、個別に詳細を確認していく。

fn expr(i: &str) -> IResult<&str, Expression> {
    let (i, init) = term(i)?;

    fold_many0(
        pair(delimited(multispace0, char('+'), multispace0), term),
        move || init.clone(),
        |acc, (_op, val): (char, Expression)| {
            Expression::Add(Box::new(acc), Box::new(val))
        },
    )(i)
}


まずはクロージャでの所有権の移動について。

fn main() {
    let s1 = String::from("hello");
    let s2 = s1; // 所有権がs1からs2に移動

    // println!("{}", s1); // この行はエラーになる。s1の所有権はs2に移動しているため、s1はもう使用できない
    println!("{}", s2); // "hello" が出力される
}


クロージャを使った場合、所有権の移動は「参照」となる。
よってクロージャの中と外の両方で参照できる。

fn main() {
    let s1 = String::from("hello");

    let closure = || {
        println!("{}", s1); // クロージャ内で`s1`を使用
    };

    println!("{}", s1); // "hello" が出力される
    closure(); // クロージャ内で "hello" が出力される
}


moveを使うと、クロージャの中に所有権を移すことができる。
所有権を移す変数を指定する必要は無く、クロージャ内で使用される変数が自動的に対象となる。

fn main() {
    let s1 = String::from("hello");

    let closure = move || {
        println!("{}", s1); // クロージャ内で`s1`を使用
    };

    // println!("{}", s1); // この行はエラーになる。s1の所有権はクロージャに移動しているため
    closure(); // クロージャ内で "hello" が出力される
}


expr関数では、クロージャ内で独立して init を扱うためにmoveを指定している。
これにより、意図しない init の変更を防ぎ、変数を安全に扱うことができる。

次にmany0とfold_many0の違いについて。
many0はパース結果を単純にリストとして保持するが、
fold_many0はクロージャで任意のロジックを指定して保持できるもので、これにより再帰処理ができる。

以下のプログラムがあるとする。

use nom::character::complete::{digit1, multispace0};
use nom::sequence::delimited;
use nom::multi::many0;
use nom::IResult;

fn main() {
    let input = "10 20 30";
    let result = parse_numbers(input);
    println!("{:?}", result);
}

fn parse_numbers(input: &str) -> IResult<&str, Vec<&str>> {
    many0(
        delimited(multispace0, digit1, multispace0)
    )(input)
}


この場合、以下のように実行できる。

>cargo run
Ok(("", ["10", "20", "30"]))

以下のプログラムがあるとする。

use nom::character::complete::{digit1, multispace0};
use nom::sequence::delimited;
use nom::multi::fold_many0;
use nom::IResult;
use std::str::FromStr;

fn main() {
    let input = "10 20 30";
    let result = parse_sum(input);
    println!("{:?}", result);
}

fn parse_sum(input: &str) -> IResult<&str, i32> {
    fold_many0(
        delimited(multispace0, digit1, multispace0),    // 前後のスペースを無視して数値をパースする
        || {
            0                                   // 初期値は0（fold_many0の仕様により、クロージャで渡す必要がある）
        },
        |acc, item: &str| {                     // 変数「acc」に加算を行っていく。「acc」はaccumulator（累積変数）をもとにした命名で、「total」のような意味
            acc + i32::from_str(item).unwrap()  // 初期値の0に対して10・20・30が加算されていく
        },
    )(input)
}


この場合、以下のように実行できる。

>cargo run
Ok(("", 60))

■パーサコンピュータ nom（SQLの解析例）

RustのnomでCREATE TABLEをパースする #Rust - Qiita
https://qiita.com/aoyagikouhei/items/6013e24e686236f10e1b

上の記事では以下のSQLを

CREATE TABLE users (
    uuid UUID NOT NULL PRIMARY KEY
    ,name TEXT NOT NULL DEFAULT ''
)


以下のとおりパースしている。

Table {
    name: "users",
    columns: [
        TableColumn {
            name: "uuid",
            sql_type: "UUID",
            primary_key_flag: true,
            not_null_flag: true,
            default_value: None
        },
        TableColumn {
            name: "name",
            sql_type: "TEXT",
            primary_key_flag: false,
            not_null_flag: true,
            default_value: Some("")
        }
    ]
}


その他メモ。

Rustのパーサーコンビネーターnomを使ってPL/pgSQLをパースする #PostgreSQL - Qiita
https://qiita.com/aoyagikouhei/items/c9b066a3687f484dc22a

Rust でパーサコンビネータを作ってみる (前編)
https://zenn.dev/nojima/articles/05cb9ffa0f993b

Rust でパーサコンビネータを作ってみる (後編)
https://zenn.dev/nojima/articles/e597d22660205d■ASTインタプリタ

src/main.rs の内容を以下のようにする。

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{
        alpha1, alphanumeric1, char, multispace0,
    },
    combinator::recognize,
    multi::{fold_many0, many0},
    number::complete::recognize_float,
    sequence::{delimited, pair},
    IResult,
};

fn main() {
    fn ex_eval<'src>(
        input: &'src str,
    ) -> Result<f64, nom::Err<nom::error::Error<&'src str>>> {
        expr(input).map(|(_, e)| eval(e))
    }

    let input = "123";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "(123 + 456 ) + pi";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "10 + (100 + 1)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "((1 + 2) + (3 + 4)) + 5 + 6";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));
}

#[derive(Debug, PartialEq, Clone)]
enum Expression<'src> {
    Ident(&'src str),
    NumLiteral(f64),
    Add(Box<Expression<'src>>, Box<Expression<'src>>),
}

fn eval(expr: Expression) -> f64 {
    match expr {
        Expression::Ident("pi") => std::f64::consts::PI,
        Expression::Ident(id) => panic!("Unknown name {:?}", id),
        Expression::NumLiteral(n) => n,
        Expression::Add(lhs, rhs) => eval(*lhs) + eval(*rhs),
    }
}

fn term(i: &str) -> IResult<&str, Expression> {
    alt((number, ident, parens))(i)
}

fn ident(input: &str) -> IResult<&str, Expression> {
    let (r, res) = delimited(multispace0, identifier, multispace0)(input)?;
    Ok((r, Expression::Ident(res)))
}

fn identifier(input: &str) -> IResult<&str, &str> {
    recognize(pair(
        alt((alpha1, tag("_"))),
        many0(alt((alphanumeric1, tag("_")))),
    ))(input)
}

fn number(input: &str) -> IResult<&str, Expression> {
    let (r, v) = delimited(multispace0, recognize_float, multispace0)(input)?;
    Ok((
        r,
        Expression::NumLiteral(v.parse().map_err(
            |_| {
                nom::Err::Error(nom::error::Error {
                    input,
                    code: nom::error::ErrorKind::Digit,
                })
            },
        )?),
    ))
}

fn parens(i: &str) -> IResult<&str, Expression> {
    delimited(
        multispace0,
        delimited(tag("("), expr, tag(")")),
        multispace0
    )(i)
}

fn expr(i: &str) -> IResult<&str, Expression> {
    let (i, init) = term(i)?;

    fold_many0(
        pair(delimited(multispace0, char('+'), multispace0), term),
        move || init.clone(),
        |acc, (_op, val): (char, Expression)| {
            Expression::Add(Box::new(acc), Box::new(val))
        },
    )(i)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_number() {
        assert_eq!(expr("123"), Ok(("", Expression::NumLiteral(123.0))));
    }

    #[test]
    fn test_pi_ident() {
        assert_eq!(expr("pi"), Ok(("", Expression::Ident("pi"))));
    }

    #[test]
    fn test_ident() {
        assert_eq!(expr("hello"), Ok(("", Expression::Ident("hello"))));
    }
}


以下のように実行できる。

>cargo run
source: "123", parsed: Ok(123.0)
source: "(123 + 456 ) + pi", parsed: Ok(582.1415926535898)
source: "10 + (100 + 1)", parsed: Ok(111.0)
source: "((1 + 2) + (3 + 4)) + 5 + 6", parsed: Ok(21.0)

■ASTインタプリタ（計算の流れを確認）

以下の流れで処理されるみたい。

1. 計算したい式をex_evalに渡す。
2. exprによってExpressionの構造が構築され、構築に成功するとevalによって計算が行われる。
3. 加算が含まれていると、eval内で再帰的にevalが呼び出されるので、カッコが複数あっても計算が行われる。
   なお「2 + 3 + 4」のような式は「(2 + 3) + 4」のように解釈される。

例えば以下の計算があった場合、

    let input = "2 + 3";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));


実行結果は以下のようになる。

>cargo run
source: "2 + 3", parsed: Ok(5.0)

以下のように変更すると、

    let input = "2 + 3";
    println!("source: {:?}, parsed: {:?}", input, expr(input));


実行結果は以下のようになる。

>cargo run
source: "2 + 3", parsed: Ok(("", Add(NumLiteral(2.0), NumLiteral(3.0))))

■ASTインタプリタ（四則演算）

src/main.rs の内容を以下のようにする。

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{
        alpha1, alphanumeric1, char, multispace0,
    },
    combinator::recognize,
    error::ParseError,
    multi::{fold_many0, many0},
    number::complete::recognize_float,
    sequence::{delimited, pair},
    IResult, Parser,
};

fn main() {
    fn ex_eval<'src>(
        input: &'src str,
    ) -> Result<f64, nom::Err<nom::error::Error<&'src str>>> {
        expr(input).map(|(_, e)| eval(e))
    }

    let input = "123";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "2 + 3";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "5 - 2";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "2 * 3";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "6 / 2";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "2 * pi";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "(123 + 456 ) + pi";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "10 - (100 + 1)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "(3 + 7) / (2 + 3)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));
}

#[derive(Debug, PartialEq, Clone)]
enum Expression<'src> {
    Ident(&'src str),
    NumLiteral(f64),
    Add(Box<Expression<'src>>, Box<Expression<'src>>),
    Sub(Box<Expression<'src>>, Box<Expression<'src>>),
    Mul(Box<Expression<'src>>, Box<Expression<'src>>),
    Div(Box<Expression<'src>>, Box<Expression<'src>>),
}

fn eval(expr: Expression) -> f64 {
    match expr {
        Expression::Ident("pi") => std::f64::consts::PI,
        Expression::Ident(id) => panic!("Unknown name {:?}", id),
        Expression::NumLiteral(n) => n,
        Expression::Add(lhs, rhs) => eval(*lhs) + eval(*rhs),
        Expression::Sub(lhs, rhs) => eval(*lhs) - eval(*rhs),
        Expression::Mul(lhs, rhs) => eval(*lhs) * eval(*rhs),
        Expression::Div(lhs, rhs) => eval(*lhs) / eval(*rhs),
    }
}

fn space_delimited<'src, O, E>(
    f: impl Parser<&'src str, O, E>,
) -> impl FnMut(&'src str) -> IResult<&'src str, O, E>
where
    E: ParseError<&'src str>,
{
    delimited(multispace0, f, multispace0)
}

fn factor(i: &str) -> IResult<&str, Expression> {
    alt((number, ident, parens))(i)
}

fn ident(input: &str) -> IResult<&str, Expression> {
    let (r, res) = space_delimited(identifier)(input)?;
    Ok((r, Expression::Ident(res)))
}

fn identifier(input: &str) -> IResult<&str, &str> {
    recognize(pair(
        alt((alpha1, tag("_"))),
        many0(alt((alphanumeric1, tag("_")))),
    ))(input)
}

fn number(input: &str) -> IResult<&str, Expression> {
    let (r, v) = space_delimited(recognize_float)(input)?;
    Ok((
        r,
        Expression::NumLiteral(v.parse().map_err(
            |_| {
                nom::Err::Error(nom::error::Error {
                    input,
                    code: nom::error::ErrorKind::Digit,
                })
            },
        )?),
    ))
}

fn parens(i: &str) -> IResult<&str, Expression> {
    space_delimited(
        delimited(tag("("), expr, tag(")"))
    )(i)
}

fn term(i: &str) -> IResult<&str, Expression> {
    let (i, init) = factor(i)?;

    fold_many0(
        pair(space_delimited(alt((char('*'), char('/')))), factor),
        move || init.clone(),
        |acc, (op, val): (char, Expression)| {
            match op {
                '*' => Expression::Mul(Box::new(acc), Box::new(val)),
                '/' => Expression::Div(Box::new(acc), Box::new(val)),
                _ => panic!(
                    "Multiplicative expression should have '*' or '/' operator"
                ),
            }
        },
    )(i)
}

fn expr(i: &str) -> IResult<&str, Expression> {
    let (i, init) = term(i)?;

    fold_many0(
        pair(space_delimited(alt((char('+'), char('-')))), term),
        move || init.clone(),
        |acc, (op, val): (char, Expression)| match op {
            '+' => Expression::Add(Box::new(acc), Box::new(val)),
            '-' => Expression::Sub(Box::new(acc), Box::new(val)),
            _ => panic!(
                "Additive expression should have '+' or '-' operator"
            ),
        },
    )(i)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_number() {
        assert_eq!(expr("123"), Ok(("", Expression::NumLiteral(123.0))));
    }

    #[test]
    fn test_pi_ident() {
        assert_eq!(expr("pi"), Ok(("", Expression::Ident("pi"))));
    }

    #[test]
    fn test_ident() {
        assert_eq!(expr("hello"), Ok(("", Expression::Ident("hello"))));
    }
}


以下のように実行できる。

>cargo run
source: "123", parsed: Ok(123.0)
source: "2 + 3", parsed: Ok(5.0)
source: "5 - 2", parsed: Ok(3.0)
source: "2 * 3", parsed: Ok(6.0)
source: "6 / 2", parsed: Ok(3.0)
source: "2 * pi", parsed: Ok(6.283185307179586)
source: "(123 + 456 ) + pi", parsed: Ok(582.1415926535898)
source: "10 - (100 + 1)", parsed: Ok(-91.0)
source: "(3 + 7) / (2 + 3)", parsed: Ok(2.0)

■関数呼び出し

src/main.rs の内容を以下のようにする。

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{
        alpha1, alphanumeric1, char, multispace0,
    },
    combinator::{opt, recognize},
    error::ParseError,
    multi::{fold_many0, many0},
    number::complete::recognize_float,
    sequence::{delimited, pair},
    IResult, Parser,
};

fn main() {
    fn ex_eval<'src>(
        input: &'src str,
    ) -> Result<f64, nom::Err<nom::error::Error<&'src str>>> {
        expr(input).map(|(_, e)| eval(e))
    }

    let input = "123";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "2 + 3";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "5 - 2";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "2 * 3";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "6 / 2";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "2 * pi";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "(123 + 456 ) + pi";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "10 - (100 + 1)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "(3 + 7) / (2 + 3)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "sqrt(2) / 2";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "sin(pi / 4)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));

    let input = "atan2(1, 1)";
    println!("source: {:?}, parsed: {:?}", input, ex_eval(input));
}

#[derive(Debug, PartialEq, Clone)]
enum Expression<'src> {
    Ident(&'src str),
    NumLiteral(f64),
    FnInvoke(&'src str, Vec<Expression<'src>>),
    Add(Box<Expression<'src>>, Box<Expression<'src>>),
    Sub(Box<Expression<'src>>, Box<Expression<'src>>),
    Mul(Box<Expression<'src>>, Box<Expression<'src>>),
    Div(Box<Expression<'src>>, Box<Expression<'src>>),
}

fn unary_fn(
    f: fn(f64) -> f64,
) -> impl Fn(Vec<Expression>) -> f64 {
    move |args| {
        f(eval(
            args.into_iter().next().expect("function missing argument"),
        ))
    }
}

fn binary_fn(
    f: fn(f64, f64) -> f64,
) -> impl Fn(Vec<Expression>) -> f64 {
    move |args| {
        let mut args = args.into_iter();
        let lhs = eval(
            args.next().expect("function missing the first argument"),
        );
        let rhs = eval(
            args.next().expect("function missing the second argument"),
        );
        f(lhs, rhs)
    }
}

fn eval(expr: Expression) -> f64 {
    use Expression::*;
    match expr {
        Ident("pi") => std::f64::consts::PI,
        Ident(id) => panic!("Unknown name {:?}", id),
        NumLiteral(n) => n,
        FnInvoke("sqrt", args) => unary_fn(f64::sqrt)(args),
        FnInvoke("sin", args) => unary_fn(f64::sin)(args),
        FnInvoke("cos", args) => unary_fn(f64::cos)(args),
        FnInvoke("tan", args) => unary_fn(f64::tan)(args),
        FnInvoke("asin", args) => unary_fn(f64::asin)(args),
        FnInvoke("acos", args) => unary_fn(f64::acos)(args),
        FnInvoke("atan", args) => unary_fn(f64::atan)(args),
        FnInvoke("atan2", args) => binary_fn(f64::atan2)(args),
        FnInvoke("pow", args) => binary_fn(f64::powf)(args),
        FnInvoke("exp", args) => unary_fn(f64::exp)(args),
        FnInvoke("log", args) => binary_fn(f64::log)(args),
        FnInvoke("log10", args) => unary_fn(f64::log10)(args),
        FnInvoke(name, _) => {
            panic!("Unknown function {name:?}")
        },
        Add(lhs, rhs) => eval(*lhs) + eval(*rhs),
        Sub(lhs, rhs) => eval(*lhs) - eval(*rhs),
        Mul(lhs, rhs) => eval(*lhs) * eval(*rhs),
        Div(lhs, rhs) => eval(*lhs) / eval(*rhs),
    }
}

fn space_delimited<'src, O, E>(
    f: impl Parser<&'src str, O, E>,
) -> impl FnMut(&'src str) -> IResult<&'src str, O, E>
where
    E: ParseError<&'src str>,
{
    delimited(multispace0, f, multispace0)
}

fn factor(i: &str) -> IResult<&str, Expression> {
    alt((number, func_call, ident, parens))(i)
}

fn func_call(i: &str) -> IResult<&str, Expression> {
    let (r, ident) = space_delimited(identifier)(i)?;
    let (r, args) = space_delimited(delimited(
        tag("("),
        many0(delimited(
            multispace0,
            expr,
            space_delimited(opt(tag(","))),
        )),
        tag(")"),
    ))(r)?;
    Ok((r, Expression::FnInvoke(ident, args)))
}

fn ident(input: &str) -> IResult<&str, Expression> {
    let (r, res) = space_delimited(identifier)(input)?;
    Ok((r, Expression::Ident(res)))
}

fn identifier(input: &str) -> IResult<&str, &str> {
    recognize(pair(
        alt((alpha1, tag("_"))),
        many0(alt((alphanumeric1, tag("_")))),
    ))(input)
}

fn number(input: &str) -> IResult<&str, Expression> {
    let (r, v) = space_delimited(recognize_float)(input)?;
    Ok((
        r,
        Expression::NumLiteral(v.parse().map_err(
            |_| {
                nom::Err::Error(nom::error::Error {
                    input,
                    code: nom::error::ErrorKind::Digit,
                })
            },
        )?),
    ))
}

fn parens(i: &str) -> IResult<&str, Expression> {
    space_delimited(
        delimited(tag("("), expr, tag(")"))
    )(i)
}

fn term(i: &str) -> IResult<&str, Expression> {
    let (i, init) = factor(i)?;

    fold_many0(
        pair(space_delimited(alt((char('*'), char('/')))), factor),
        move || init.clone(),
        |acc, (op, val): (char, Expression)| {
            match op {
                '*' => Expression::Mul(Box::new(acc), Box::new(val)),
                '/' => Expression::Div(Box::new(acc), Box::new(val)),
                _ => panic!(
                    "Multiplicative expression should have '*' or '/' operator"
                ),
            }
        },
    )(i)
}

fn expr(i: &str) -> IResult<&str, Expression> {
    let (i, init) = term(i)?;

    fold_many0(
        pair(space_delimited(alt((char('+'), char('-')))), term),
        move || init.clone(),
        |acc, (op, val): (char, Expression)| match op {
            '+' => Expression::Add(Box::new(acc), Box::new(val)),
            '-' => Expression::Sub(Box::new(acc), Box::new(val)),
            _ => panic!(
                "Additive expression should have '+' or '-' operator"
            ),
        },
    )(i)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_number() {
        assert_eq!(expr("123"), Ok(("", Expression::NumLiteral(123.0))));
    }

    #[test]
    fn test_pi_ident() {
        assert_eq!(expr("pi"), Ok(("", Expression::Ident("pi"))));
    }

    #[test]
    fn test_ident() {
        assert_eq!(expr("hello"), Ok(("", Expression::Ident("hello"))));
    }
}


以下のように実行できる。

>cargo run
source: "123", parsed: Ok(123.0)
source: "2 + 3", parsed: Ok(5.0)
source: "5 - 2", parsed: Ok(3.0)
source: "2 * 3", parsed: Ok(6.0)
source: "6 / 2", parsed: Ok(3.0)
source: "2 * pi", parsed: Ok(6.283185307179586)
source: "(123 + 456 ) + pi", parsed: Ok(582.1415926535898)
source: "10 - (100 + 1)", parsed: Ok(-91.0)
source: "(3 + 7) / (2 + 3)", parsed: Ok(2.0)
source: "sqrt(2) / 2", parsed: Ok(0.7071067811865476)
source: "sin(pi / 4)", parsed: Ok(0.7071067811865476)
source: "atan2(1, 1)", parsed: Ok(0.7853981633974483)

>cargo run -- input.rscl

「unary_fn」「binary_fn」という関数を定義しているが、これは「引数が1つの関数」「引数が2つの関数」の意味。
バイナリデータを扱うための処理…というわけでは無い（なお「バイナリデータ」は「2進数のデータ」のこと。）

関数は引数の個数に応じて「unary」「binary」「ternary」などと呼ばれるらしい #PHP - Qiita
https://qiita.com/suin/items/0ccf115cc30d6e9d641a

arity: 最近知った英単語 | アルファのブログ
https://alpha3166.github.io/blog/20121111.html
Memo

Advertisement
