Go to Qiita Advent Calendar Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TechSavvy_24in株式会社ユビキタスAI

Rust言語のChumskyでパーサ入門 2

Posted at

前回の続き

前回に引き続きchumskyをいろいろと試します。
今回は、ariadneでエラー表示を試したいと思いますが、その前に前回は大事なことを忘れていました。
それは、 ASTを評価する評価器(eval)を実装し、パースした結果から計算結果を表示することです。

evalの実装

というわけで、evalを実装していきます。
match式で以下の様に処理を分岐し、再帰的に評価するだけで簡単に実装できます。

  • Num() : ASTが数値の場合に、その数値を返す
  • Op() : opの計算対象を再度eval()で評価し、再帰します
fn eval(ast:&Expr) -> i64 {
    match ast {
        Expr::Num(n) => *n,
        Expr::Op(expr1, op, expr2) => {
            let p1 = eval(expr1);
            let p2 = eval(expr2);
            let fop = match op {
                Op::Add => |x:i64, y:i64| -> i64 {x + y},
                Op::Sub => |x:i64, y:i64| -> i64 {x - y},
                Op::Mul => |x:i64, y:i64| -> i64 {x * y},
                Op::Div => |x:i64, y:i64| -> i64 {x / y},
            };
            fop(p1, p2)
        },
    }
}

テストも追加します。

#[cfg(test)]
mod tests {
    use chumsky::prelude::*;
    use super::*;
    #[test]
    fn test_calc() {
        let parser = parser();
        
        let input = "10 + 2 * 3";
        let expect = 10 + 2 * 3;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);

        let input = "(10 + 2) * 3";
        let expect = (10 + 2) * 3;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);

        let input = "10 / 2 - 5 * 2 + 100";
        let expect = 10 / 2 - 5 * 2 + 100;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);
    }
}

テスト結果

$ cargo test
   Compiling chumsky-sample v0.1.0 (/home/test/rust/chumsky-sample)
    Finished `test` profile [unoptimized + debuginfo] target(s) in 0.74s
     Running unittests src/main.rs (target/debug/deps/chumsky_sample-557406b9f4a066aa)

running 1 test
test tests::test_calc ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

ariadneでエラー表示

ariadne自体は単体でも使用できるエラー表示ライブラリとなっていますが、作者がchumskyと同じこともあり簡単に連携できるようになっています。

chumskyでパースした結果、Result型がErrの場合、エラー箇所などの情報がベクターで保存されています。
このエラーの型はパーサの作成時の型となっています。

  • パーサの型指定
fn parser<'a>() -> impl Parser<'a, &'a str, Expr, extra::Err<Simple<'a, char>>> {
  • エラー表示関数の呼び出し
    let input = "10 + 2 * 3"; // 10 + (2 * 3) = 16
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Parsed AST: {:?}\nResult: {}\n", ast, eval(&ast)),
        Err(errors) => error_print(input, errors),
    }
  • エラー表示関数

Report::build でエラーレポートを作成します。
今回はextra::Err<Simple<...>>エラー型を使用しており、パース中にエラーの種類などを指定していないのでエラー表示側ではエラーの種類の特定はできていません。
もっと複雑なエラー表示を行いたい場合にはextra::Err<Rich<...>>を使用する必要がります。

e.span().into_range() でエラー箇所のレンジが取得でき e.found() でエラー箇所のトークンが取得できます。トークンが取得できない場合は入力の終端のエラーとなります。

fn error_print(source: &str, errors: Vec<Simple<'_, char>>) {
    let src_id = "test";
    for e in errors {
        Report::build(ReportKind::Error, (src_id, e.span().into_range()))
            .with_message("parse error")
            .with_label(
                Label::new((src_id, e.span().into_range()))
                    .with_message(
                        match e.found() {
                            Some(c) => format!("unexpected token: {}", c),
                            None => format!("end of input"),
                        }
                     )
                    .with_color(Color::Red),
            )
            .finish()
            .eprint((src_id, Source::from(source)))
            .unwrap();
    }
}
  • コードの出力例
Input: "10 + * 2"
Error: parse error
   ╭─[ test:1:6 ]
   │
 1 │ 10 + * 2
   │      ┬
   │      ╰── unexpected token: *
───╯

コード全体

上記のコードの全体部分をのせておきます。

use chumsky::prelude::*;
use ariadne::{Color, Label, Report, ReportKind, Source};

#[derive(Debug, PartialEq, Clone)]
enum Op {
    Add,
    Sub,
    Mul,
    Div,
}

#[derive(Debug, PartialEq, Clone)]
enum Expr {
    Num(i64),
    Op(Box<Expr>, Op, Box<Expr>),
}

fn parser<'a>() -> impl Parser<'a, &'a str, Expr, extra::Err<Simple<'a, char>>> {
    // 整数をパースするパーサ
    let num = just('-')
        .or_not()
        .then(text::int(10))
        .to_slice()
        .padded()
        .map(|s: &str| Expr::Num(s.parse().unwrap()));

    // 括弧をパースするパーサを遅延評価で定義
    let expr = recursive(|expr| {
        // 最も単純な項（整数または括弧で囲まれた式）
        let term = num.or(expr.delimited_by(just('('), just(')'))).padded();

        // 乗除算のパーサ
        let factor = term.clone().foldl(
            just('*')
                .to(Op::Mul)
                .or(just('/').to(Op::Div))
                .then(term)
                .repeated(),
            |lhs, (op, rhs)| Expr::Op(Box::new(lhs), op, Box::new(rhs)),
        );

        // 加減算のパーサ
        factor.clone().foldl(
            just('+')
                .to(Op::Add)
                .or(just('-').to(Op::Sub))
                .then(factor)
                .repeated(),
            |lhs, (op, rhs)| Expr::Op(Box::new(lhs), op, Box::new(rhs)),
        )
    });

    expr.then_ignore(end())
}

fn eval(ast:&Expr) -> i64 {
    match ast {
        Expr::Num(n) => *n,
        Expr::Op(expr1, op, expr2) => {
            let p1 = eval(expr1);
            let p2 = eval(expr2);
            let fop = match op {
                Op::Add => |x:i64, y:i64| -> i64 {x + y},
                Op::Sub => |x:i64, y:i64| -> i64 {x - y},
                Op::Mul => |x:i64, y:i64| -> i64 {x * y},
                Op::Div => |x:i64, y:i64| -> i64 {x / y},
            };
            fop(p1, p2)
        },
    }
}

fn error_print(source: &str, errors: Vec<Simple<'_, char>>) {
    let src_id = "test";
    for e in errors {
        Report::build(ReportKind::Error, (src_id, e.span().into_range()))
            .with_message("parse error")
            .with_label(
                Label::new((src_id, e.span().into_range()))
                    .with_message(
                        match e.found() {
                            Some(c) => format!("unexpected token: {}", c),
                            None => format!("end of input"),
                        }
                     )
                    .with_color(Color::Red),
            )
            .finish()
            .eprint((src_id, Source::from(source)))
            .unwrap();
    }
}

fn main() {
    let parser = parser();

    // 実行例1: 優先順位が考慮される
    let input = "10 + 2 * 3"; // 10 + (2 * 3) = 16
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Parsed AST: {:?}\nResult: {}\n", ast, eval(&ast)),
        Err(errors) => error_print(input, errors),
    }

    // 実行例2: 括弧の処理
    let input = "(10 + 2) * 3"; // 12 * 3 = 36
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Parsed AST: {:?}\nResult: {}\n", ast, eval(&ast)),
        Err(errors) => error_print(input, errors),
    }

    // 実行例3: 複雑な式
    let input = "10 / 2 - 5 * 2 + 100"; // (10 / 2) - (5 * 2) + 100 = 5 - 10 + 100 = 95
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Parsed AST: {:?}\nResult: {}\n", ast, eval(&ast)),
        Err(errors) => error_print(input, errors),
    }

    // 実行例4: 無効な式
    let input = "10 + * 2";
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Parsed AST: {:?}\nResult: {}\n", ast, eval(&ast)),
        Err(errors) => error_print(input, errors),
    }

    // 実行例5: 無効な式 - 閉じ括弧なし
    let input = "10 * (5 + 2";
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Input: \"{}\"\nParsed AST: {:?}\n", input, ast),
        Err(errors) => error_print(input, errors),
    }

    // 実行例6: 無効な式 - 開き括弧なし
    let input = "10 * 5) + 2";
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Input: \"{}\"\nParsed AST: {:?}\n", input, ast),
        Err(errors) => error_print(input, errors),
    }

    // 実行例7: 無効な式 - 実数未対応 
    let input = "10 * 5.2";
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Input: \"{}\"\nParsed AST: {:?}\n", input, ast),
        Err(errors) => error_print(input, errors),
    }

    // 実行例8: 無効な式 - 複数エラー
    let input = "10 * 5 ) / - 2.2";
    println!("Input: \"{}\"", input);
    match parser.parse(input).into_result() {
        Ok(ast) => println!("Input: \"{}\"\nParsed AST: {:?}\n", input, ast),
        Err(errors) => error_print(input, errors),
    }
}

#[cfg(test)]
mod tests {
    use chumsky::prelude::*;
    use super::*;
    #[test]
    fn test_calc() {
        let parser = parser();

        let input = "10 + 2 * 3";
        let expect = 10 + 2 * 3;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);

        let input = "(10 + 2) * 3";
        let expect = (10 + 2) * 3;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);

        let input = "10 / 2 - 5 * 2 + 100";
        let expect = 10 / 2 - 5 * 2 + 100;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);

        let input = "(1) + (2) / 2 - 5 * 2 + 100";
        let expect = (1) + (2) / 2 - 5 * 2 + 100;
        let ast = parser.parse(input).into_result().unwrap();
        assert_eq!(eval(&ast), expect);
    }
}

cargo runの出力

Input: "10 + 2 * 3"
Parsed AST: Op(Num(10), Add, Op(Num(2), Mul, Num(3)))
Result: 16

Input: "(10 + 2) * 3"
Parsed AST: Op(Op(Num(10), Add, Num(2)), Mul, Num(3))
Result: 36

Input: "10 / 2 - 5 * 2 + 100"
Parsed AST: Op(Op(Op(Num(10), Div, Num(2)), Sub, Op(Num(5), Mul, Num(2))), Add, Num(100))
Result: 95

Input: "10 + * 2"
Error: parse error
   ╭─[ test:1:6 ]
   │
 1 │ 10 + * 2
   │      ┬
   │      ╰── unexpected token: *
───╯
Input: "(1) + (2) / 2 - 5 * 2 + 100"
Parsed AST: Op(Op(Op(Num(1), Add, Op(Num(2), Div, Num(2))), Sub, Op(Num(5), Mul, Num(2))), Add, Num(100))

Input: "10 * (5 + 2"
Error: parse error
   ╭─[ test:1:12 ]
   │
 1 │ 10 * (5 + 2
   │            │
   │            ╰─ end of input
───╯
Input: "10 * 5) + 2"
Error: parse error
   ╭─[ test:1:7 ]
   │
 1 │ 10 * 5) + 2
   │       ┬
   │       ╰── unexpected token: )
───╯
Input: "10 * 5.2"
Error: parse error
   ╭─[ test:1:7 ]
   │
 1 │ 10 * 5.2
   │       ┬
   │       ╰── unexpected token: .
───╯
Input: "10 * 5 ) / - 2.2"
Error: parse error
   ╭─[ test:1:8 ]
   │
 1 │ 10 * 5 ) / - 2.2
   │        ┬
   │        ╰── unexpected token: )
───╯

最後に

簡単にariadneを使用したエラー表示を行うことができました。
しかし、実用するには、エラーの種類表示やリカバリー処理、複数エラーの対応など、まだまだ難しい部分があります。もっと豊富で典型的なパースの例があれば、より理解しやすいと思うところです。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?