2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@dqkqd(Khanh)

Rustで演算子順位構文解析法（Prattパーサ）の実装

2
Posted at

はじめに

演算子順位構文解析法（Prattパーサ）は手書きのパーサであり、算術式の解析に用いられることが多く、rust-analyzer やZig にも採用されています。今回、1 + 2 * (3 + 4) - 5のような簡単な算術式のプログラミング言語のPrattパーサを実装していきます！

パーサって何？

パーサの目的はトークンの列を構文木に変換することです。各トークンを取り出し、どのような式が来るかを予測します(再帰下降パーサって言います)。例えば、printトークンを見た場合、print(<何>)のような式だと判断して構文木を構築します。

image.png

以下はprint("Hello World")の解析のサンプルコードです。単に左から右へと順に進みながらトークンを取り出します。

const TOKENS: [&'static str; 4] = [
  "print", "(", r#""Hello World""#, ")"
];

fn parse_print(tokenizer: &mut Tokenizer) -> PrintExpr {
  expect_token(tokenizer, "print");
  expect_token(tokenizer, "(");
  let string = tokenizer.next().unwrap();
  expect_token(tokenizer, ")");
  PrintExpr(string.to_string())
}

しかし、この方法は算術式とは相性がよくありません。主な理由は２つあります。

結合規則の問題

パーサは1 + 2 * 3の中で2を見たとき、2がどの演算子と結び付くべきか判断する必要があります。私達から見ると、*だと分かり、以下のような構文木になりますが、

image.png

パーサはそんなことを知りません！+や*を単なるトークンとして扱います。左から右へと順に進むので、2に到達した時点ではまだ*を見ていません。

image.png

前置演算子と中置演算子の問題

算術式において、トークンはその位置によって異なる意味を持ちます。例えば-が次のような演算子に解析されることもあります。

  • マイナス演算子（前置演算子）：-1
  • 減算演算子（中置演算子）：1 - 2

パーサは同じトークンでもどのような演算子として扱うのか判断しないといけません。

Prattパーサ

Prattパーサは以上の問題を解決できます。トークンではなく演算子に注目して、解析します。たとえば、-1の-と1-2の-が異なるものとして扱います。

では、実際にPrattパーサを実装してみましょう！

事前準備のコード

トークナイザ (Tokenizer)

トークンがどこかで生成される必要があるので、Tokenizerを実装します。私達のプログラミング言語は簡単な算術式で、数字、+、-、*、括弧しかないため、以下のTokenのEnumを定義します。

#[derive(Debug, Copy, Clone)]
enum Token {
  Number(u32),
  Add,
  Sub,
  Mul,
  LParen,
  RParen,
}

簡単なTokenizerで十分なので、[0-9]+|[+\-*()]のregexを使います。次のトークンを取り出す関数（next）と、取り出さずに現在のトークンを確認できる関数（peek）が必要なので、Peekable<Iterator>を利用します。

+ type Tokenizer = std::iter::Peekable<std::vec::IntoIter<Token>>;

fn tokenizer(program: &str) -> Tokenizer {
+  let re = Regex::new(r"[0-9]+|[+\-*()]").unwrap();
  // ...
+  tokens.into_iter().peekable()
}
全体のコード 
use regex::Regex;

type Tokenizer = std::iter::Peekable<std::vec::IntoIter<Token>>;

fn tokenizer(program: &str) -> Tokenizer {
  let re = Regex::new(r"[0-9]+|[+\-*()]").unwrap();
  let tokens: Vec<Token> = re
    .find_iter(program)
    .map(|m| match m.as_str() {
      "+" => Token::Add,
      "-" => Token::Sub,
      "*" => Token::Mul,
      "(" => Token::LParen,
      ")" => Token::RParen,
      s => match s.parse::<u32>() {
        Ok(value) => Token::Number(value),
        Err(_) => panic!("無効なトークン {}", s),
      },
    })
    .collect();
  tokens.into_iter().peekable()
}

(3 + 4)の場合は以下のトークンに分割されます。

LParen, Number(3), Add, Number(4), RParen

算術式

パーサの入力はトークンで定義されましたが、出力（構文木）がまだ定義されていません。先ほどの木を見ると、葉ノードは数字で、内部ノードは式で表します。

image.png

この木を表現するには、異なる種類のノードを持つ Enum がちょうどいいです。

use std::fmt;

enum Expr {
  Literal(u32),
  BinaryAdd { lhs: Box<Expr>, rhs: Box<Expr> }, // lhs + rhs
  BinarySub { lhs: Box<Expr>, rhs: Box<Expr> }, // lhs - rhs
  BinaryMul { lhs: Box<Expr>, rhs: Box<Expr> }, // lhs * rhs
}

デバッグするために、式は表示可能で、かつ評価できる必要があります。

  • 表示について、ポーランド記法を使って、Displayを実装します

    impl fmt::Display for Expr {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    match self {
      Expr::Literal(value) => write!(f, "{}", value),
      Expr::BinaryAdd { lhs, rhs } => write!(f, "(+ {lhs} {rhs})"),
      Expr::BinarySub { lhs, rhs } => write!(f, "(- {lhs} {rhs})"),
      Expr::BinaryMul { lhs, rhs } => write!(f, "(* {lhs} {rhs})"),
    }
  }
}

  • 評価のため、再帰的にトラバースすれば十分です

    fn eval(expr: &Expr) -> i64 {
  match expr {
    Expr::Literal(value) => *value as i64,
    Expr::BinaryAdd { lhs, rhs } => eval(lhs) + eval(rhs),
    Expr::BinarySub { lhs, rhs } => eval(lhs) - eval(rhs),
    Expr::BinaryMul { lhs, rhs } => eval(lhs) * eval(rhs),
  }
}

たとえば、1 + (2 * 3)の式は

  • 構文木：

    BinaryAdd {
    lhs: Literal(1),
    rhs: BinaryMul {
        lhs: Literal(2),
        rhs: Literal(3),
    },
}

  • ポーランド記法： (+ 1 (* 2 3))

  • 評価：7

パーサのエントリーポイント

ソースコードから構文木に変換する関数が必要です。これはPrattパーサのアルゴリズムを実装する関数です。

fn parse(program: &str) -> Expr {
  let mut tokenizer = tokenizer(program);
  expr(&mut tokenizer)
}

fn expr(tokenizer: &mut Tokenizer) -> Expr {
  todo!()
}

実装が正しいか確認するため、テスト関数にも追加します。

mod test {
  use super::*;

  fn test_parse(program: &str, expected_display: &str, expected_eval: i64) {
    let expr = parse(program);
    assert_eq!(expr.to_string(), expected_display);
    assert_eq!(eval(&expr), expected_eval);
  }

  // 以下はテストケース
}

事前準備が完了しました！

数値リテラル式

一番簡単な数値リテラル式から実装します。Tokenizerからトークンを取り出して（next）、Expr::Literalとして返します。

fn literal(tokenizer: &mut Tokenizer) -> Expr {
  match tokenizer.next() {
    Some(Token::Number(value)) => Expr::Literal(value),
    token => panic!("無効なトークン {:?}", token),
  }
}

exprも編集して、テストケースを追加します。

fn expr(tokenizer: &mut Tokenizer) -> Expr {
- todo!()
+ literal(tokenizer)
}

mod test {
// ...

+ #[test]
+ fn literal() {
+   test_parse("123", "123", 123)
+ }
}

running 1 test
test literal ... ok

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

二項演算式

次はlhs <op> rhs形の二項演算式です。lhs・<op>・rhsを取り出す必要があります。

fn binary(...) -> Expr {
+ let lhs = todo!("左辺を取り出す");
+ let op = todo!("演算子を取り出す");
+ let rhs = todo!("右辺を取り出す");
  match op {
    Token::Add => Expr::BinaryAdd { lhs: Box::new(lhs), rhs: Box::new(rhs) },
    Token::Sub => Expr::BinarySub { lhs: Box::new(lhs), rhs: Box::new(rhs) },
    Token::Mul => Expr::BinaryMul { lhs: Box::new(lhs), rhs: Box::new(rhs) },
    _ => panic!("無効な演算子 {:?}", op),
  }
}

Tokenizerからどのタイミングでトークンを取り出すかによって、binaryの実装は異なります。以下で各選択肢を見ましょう（現在の位置は|で表します）。

  • lhs <op> rhs |：すべて取り出しました。binaryの実装はExpr::Binaryを単純に返すので、あまり役に立ちません

    +fn binary(lhs: Expr, op: Token, rhs: Expr) -> Expr {
- let lhs = todo!("左辺を取り出す");
- let op = todo!("演算子を取り出す");
- let rhs = todo!("右辺を取り出す");
  match op {
  // ...
}

  • lhs <op> | rhs：lhs と <op>を取り出しました。残りはrhsです。exprを使って取り出します

    +fn binary(tokenizer: &mut Tokenizer, lhs: Expr, op: Token) -> Expr {
- let lhs = todo!("左辺を取り出す");
- let op = todo!("演算子を取り出す");
- let rhs = todo!("右辺を取り出す");
+ let rhs = expr(tokenizer);
  match op {
  // ...
}

  • lhs | <op> rhs：<op>とrhsを取り出す必要があります

    +fn binary(tokenizer: &mut Tokenizer, lhs: Expr) -> Expr {
- let lhs = todo!("左辺を取り出す");
- let op = todo!("演算子を取り出す");
- let rhs = todo!("右辺を取り出す");
+ let op = tokenizer.next().unwrap();
+ let rhs = expr(tokenizer);
  match op {
  // ...
}

  • | lhs <op> rhs：何も取り出していません。数値リテラル式と同様に、すべての被演算子と演算子をパースしないといけません。上と同じにすれば、<op>とrhsが問題ないですが。lhsがかなりやっかいです。exprを使ったら無限再帰になりますし、literalを使ったら、lhsが数字（Expr::Literal）になっちゃっています（lhsがExpr::Binaryであるかもしれません）

上記の選択肢から２番目と３番目は良いです。binary関数の中で可能な限り解析すべきなので、３番目のlhs | <op> rhsを選びます。

fn binary(tokenizer: &mut Tokenizer, lhs: Expr) -> Expr {
  let op = tokenizer.next().expect("missing op for binary expression");
  let rhs = expr(tokenizer);
  match op {
    Token::Add => Expr::BinaryAdd { lhs: Box::new(lhs), rhs: Box::new(rhs) },
    Token::Sub => Expr::BinarySub { lhs: Box::new(lhs), rhs: Box::new(rhs) },
    Token::Mul => Expr::BinaryMul { lhs: Box::new(lhs), rhs: Box::new(rhs) },
    _ => panic!("無効な演算子 {:?}", op),
  }
}

binaryを使ってexprを編集します。まずはlhsをパースして、残りがあればbinaryでパースします。

fn expr(tokenizer: &mut Tokenizer) -> Expr {
- literal(tokenizer)
+ let lhs = literal(tokenizer);
+ if tokenizer.peek().is_none() {
+   return lhs;
+ };
+ binary(tokenizer, lhs)
}

テストケースを追加します。

#[test]
fn binary_add() {
  test_parse("1 + 2", "(+ 1 2)", 3)
}

#[test]
fn binary_sub() {
  test_parse("1 - 2", "(- 1 2)", -1)
}

#[test]
fn binary_mul() {
  test_parse("2 * 3", "(* 2 3)", 6)
}

running 4 tests
test test::literal ... ok
test test::binary_add ... ok
test test::binary_sub ... ok
test test::binary_mul ... ok

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

演算子順位

現在の実装は右に深い構文木を解析して結合規則の問題を引き起こします。たとえば、1 + 2 * 3 + 4を(+ 1 (* 2 (+ 3 4)))の構文木に解析します。これは2 * 3より3 + 4を先に評価する誤った構文木です。

image.png

Prattパーサは各演算子に優先順位 (Binding Power) を登録します。より高い優先度を持つ演算子が式に結び付きます。たとえば、+と*が10と20の優先度とすれば、3が+ではなく*に結び付きます。

image.png

以下は優先順位を登録した演算子の正しい構文木です。

image.png

正しい構文木の解析

上記の構文木を見ると、子ノードはより高い優先度を持ちます。なぜなら、より高い優先度の演算子は先に評価されて、葉ノードの近くになります。
image.png

正しい構文木を解析するため、演算子の優先度を確認しなければなりません。

  • 現在のノードより高い優先度の演算子が現れたら、子ノードとして追加します
  • そうでなければ、より低い優先度の祖先ノードを探し、そこに追加します

少しわかりにくいと思うので、図で構文木の解析を説明します。

  • 最初は優先度の0を持つノードを追加します
    image.png

  • 次の２つのトークンを取り出して、1を+に結び付けて、+の右に進みます
    　image.png

  • 次の２つのトークンを取り出して、*が+より優先度が高いので、2を*に結び付けて、*の右に進みます
    　image.png

  • 次の２つのトークンを取り出して、3を*に結び付けます
    image.png

  • +はどうしますか？+は*より優先度が低いので、より低い優先度を持つ祖先ノードを探し、そこに新しい子ノードとして追加して右に進みます
    image.png

  • 最後のトークンを取り出して、+に結び付けます
    image.png

演算子順位の実装

まずは優先順位（Binding Power）のテーブルを追加します。+と-は10にして、*は20にします。

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct BindingPower(pub u8);

fn binding_power(token: &Token) -> BindingPower {
  match token {
+    Token::Add | Token::Sub => BindingPower(10),
+    Token::Mul => BindingPower(20),
    _ => panic!("トークンは優先順位を登録されていない {:?}", token),
  }
}

現在のノードの優先度を考慮するため、exprにmin_power変数を追加します。

-fn expr(tokenizer: &mut Tokenizer) -> Expr {
+fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
  // ...
}

より高い優先度の演算子が現れたら、右に子ノードを追加して、進みます。そうでなければ、現在のノードを返します。

fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
  // ...
+ let bp = binding_power(op);
+ if bp <= min_power {
+   return lhs;
+ }
+ binary(tokenizer, lhs, bp)
}
全体のコード 
fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
  let lhs = literal(tokenizer);
  let Some(op) = tokenizer.peek() else {
    return lhs;
  };
  let bp = binding_power(op);
  if bp <= min_power {
    return lhs;
  }
  binary(tokenizer, lhs, bp)
}

値ノードの優先度を0に設定します。これは0より高い優先度の演算子はパースするという意味です。

fn parse(program: &str) -> Expr {
  let mut tokenizer = tokenizer(program);
-  expr(&mut tokenizer)
+  expr(&mut tokenizer, BindingPower(0))
}

テストを追加しますが、２つのケースのうち１つが失敗しました。

#[test]
fn binary_mul_add() {
  test_parse("2 * 3 + 4", "(+ (* 2 3) 4)", 10)
}

#[test]
fn binary_add_mul() {
+  test_parse("2 + 3 * 4", "(+ 2 (* 3 4))", 14)
}

thread 'test::binary_mul_add' (42) panicked at src/main.rs:112:5:
assertion `left == right` failed
+ left: "(* 2 3)"
+ right: "(+ (* 2 3) 4)"
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

エラーを見ると、2 * 3 + 4が (* 2 3) の構文木に解析されます。+まで解析しないまま返した状態です。

fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
  // ...
  let bp = binding_power(op);
+ if bp <= min_power {
+   return lhs;
+ }
  binary(tokenizer, lhs, bp)
}

対策として、ループにして、より高い優先度の演算子がなくなるまで繰り返します。

fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
  let mut lhs = literal(tokenizer);
+ loop {
    let Some(op) = tokenizer.peek() else {
      break;
    };
    let bp = binding_power(op);
    if bp <= min_power {
      break;
    }
    lhs = binary(tokenizer, lhs, bp)
+ }
  lhs
}

より高い優先度の演算子しか使っていないので、lhsを取って新しいExpr::Binaryノードを追加して、進みます。

fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
+ let mut lhs = literal(tokenizer);
  loop {
    let Some(op) = tokenizer.peek() else {
      break;
    };
    let bp = binding_power(op);
    if bp <= min_power {
      break;
    }
+   lhs = binary(tokenizer, lhs, bp)
  }
  lhs
}

テストケースがすべて成功しました。

running 6 tests
test test::binary_add ... ok
test test::binary_add_mul ... ok
test test::binary_mul_add ... ok
test test::binary_mul ... ok
test test::binary_sub ... ok
test test::literal ... ok

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

前置演算子と中置演算子

残りの問題は前置演算子と中置演算子の問題です。

前置と中置の用語に移行

前置演算子と中置演算子を見ると：

  • 前置演算子は右辺しか必要ありません：<op> rhs。これは数値リテラル式と同じです。
  • 中置演算子は左辺と右辺が必要です：lhs <op> rhs。これは二項演算式です。

literalとbinaryを消して、新しい前置と中置の用語に移行しましょう。

fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
- let mut lhs = literal(tokenizer);
+  let mut lhs = prefix(tokenizer);
  // ...
-   lhs = binary(tokenizer, lhs, bp);
+    lhs = infix(tokenizer, lhs, bp);
  // ...
}

-fn literal(tokenizer: &mut Tokenizer) -> Expr {
+fn prefix(tokenizer: &mut Tokenizer) -> Expr {
  // ...
}

-fn binary(tokenizer: &mut Tokenizer, lhs: Expr, min_power: BindingPower) -> Expr {
+fn infix(tokenizer: &mut Tokenizer, lhs: Expr, min_power: BindingPower) -> Expr {
  // ...
}

マイナス式

先ほど説明したようにPrattパーサは同じトークンの前置演算子と中置演算子を異なるものとして扱います。-の中置演算子はExpr::BinarySubで実装しましたので、-の前置演算子（マイナス演算子）を実装します。- innerの形の新しいExpr::Minusを追加します。

enum Expr {
  // ...
+ Minus(Box<Expr>),
}

impl fmt::Display for Expr {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    match self {
      // ...
+     Expr::Minus(expr) => write!(f, "-{expr}"),
    }
  }
}

fn eval(expr: &Expr) -> i64 {
  match expr {
    // ...
+   Expr::Minus(expr) => -eval(expr),
  }
}

Expr::Minusは前置演算子を使うので、prefix中で実装します。exprで内部演算式をパースしてから、Expr::Minusとして返します。

fn prefix(tokenizer: &mut Tokenizer) -> Expr {
  match tokenizer.next() {
    Some(Token::Number(value)) => Expr::Literal(value),
+   Some(Token::Sub) => {
+     let expr = expr(tokenizer, binding_power(&Token::Sub));
+     Expr::Minus(Box::new(expr))
+   }
    token => panic!("bad token {:?}", token),
  }
}

テストケースを追加しましたが、失敗しました。

#[test]
fn prefix_minus() {
  test_parse("-2", "-2", -2)
}

#[test]
fn prefix_minus_mul() {
+ test_parse("-2 * 3", "(* -2 3)", -6)
}

thread 'test::prefix_minus_mul' (46) panicked at src/main.rs:122:5:
assertion `left == right` failed
+ left: "-(* 2 3)"
+ right: "(* -2 3)"
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

失敗したケースは -2 * 3です。構文木を見ると、2 * 3 が -2 より先に評価されます。つまり、* はマイナス演算子（-）より優先度が高いです。これは違います！

image.png

- の前置演算子と中置演算子を同じ優先順位（10）を設定してしまったため、どちらも*の優先度より低くなっています。

fn prefix(tokenizer: &mut Tokenizer) -> Expr {
  // ...
    Some(Token::Sub) => {
+     let expr = expr(tokenizer, binding_power(&Token::Sub));
      Expr::Minus(Box::new(expr))
    }
  // ...
}

対策として、前置演算子と中置演算子の優先順位を別々に定義しなければなりません。ただよく見てみると、今まで使っているbinding_power自体が中置演算子の優先度です。新しいinfix_powerに移行しましょう。

-fn binding_power(token: &Token) -> BindingPower {
+fn infix_power(token: &Token) -> BindingPower {
  // ...
}

// ...

fn expr(tokenizer: &mut Tokenizer, min_power: BindingPower) -> Expr {
  // ...
-    let bp = binding_power(op);
+    let bp = infix_power(op);
  // ...
}

次は前置演算子の優先順位を登録します。マイナス演算子の優先度が一番高い値なので、30に設定します。

+fn prefix_power(token: &Token) -> BindingPower {
+ match token {
+   Token::Sub => BindingPower(30),
+   _ => panic!("前置トークンは優先順位を登録されていない {:?}", token),
+ }
+}

// ...

fn prefix(tokenizer: &mut Tokenizer) -> Expr {
  // ...
    Some(Token::Sub) => {
+     let expr = expr(tokenizer, prefix_power(&Token::Sub));
      Expr::Minus(Box::new(expr))
    }
  // ...
}

テストケースが成功しました。

running 8 tests
test test::binary_add_mul ... ok
test test::binary_add ... ok
test test::binary_mul ... ok
test test::binary_mul_add ... ok
test test::binary_sub ... ok
test test::literal ... ok
test test::prefix_minus_mul ... ok
test test::prefix_minus ... ok

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

括弧付き式

最後に括弧付き式（(1 + 2)）を実装しましょう。

enum Expr {
  // ...
+ Paren(Box<Expr>),
}

impl fmt::Display for Expr {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    match self {
      // ...
+     Expr::Paren(expr) => write!(f, "({expr})"),
    }
  }
}

fn eval(expr: &Expr) -> i64 {
  match expr {
    // ...
+   Expr::Paren(expr) => eval(expr),
  }
}

優先順位

  • (は前置演算子として扱います。内部の式が優先的に解析されるため、ここでは一番低い優先度を設定します
  • )は式の終わりを示す「区切り」として扱います。中置演算子の判断ループを止めるため、これも一番低い優先度を設定します
fn prefix_power(token: &Token) -> BindingPower {
  match token {
    Token::Sub => BindingPower(30),
+   Token::LParen => BindingPower(1),
    _ => panic!("前置トークンは優先順位を登録されていない {:?}", token),
  }
}

fn infix_power(token: &Token) -> BindingPower {
  match token {
    Token::Add | Token::Sub => BindingPower(10),
    Token::Mul => BindingPower(20),
+   Token::RParen => BindingPower(1),
    _ => panic!("中置トークンは優先順位を登録されていない {:?}", token),
  }
}

prefix中で実装します。内部算術式を解析してから、)を取り出す必要があります。

fn prefix(tokenizer: &mut Tokenizer) -> Expr {
  match tokenizer.next() {
    // ...
+    Some(Token::LParen) => {
+     let expr = expr(tokenizer, prefix_power(&Token::LParen));
+     let expr = Expr::Paren(Box::new(expr));
+     let Some(Token::RParen) = tokenizer.next() else {
+       panic!("期待トークン Token::RParen");
+     };
+     expr
+   }
    token => panic!("無効なトークン {:?}", token),
  }
}

テストケースを追加します。すべてが成功しました。

#[test]
fn paren() {
  test_parse("(2)", "(2)", 2)
}

#[test]
fn paren_complex() {
  test_parse("2 * (3 + 4) - (5 + 6)", "(- (* 2 ((+ 3 4))) ((+ 5 6)))", 3)
}

#[test]
fn paren_nested() {
  test_parse(
    "2 * (3 + 4 * ((5 + 6)))",
    "(* 2 ((+ 3 (* 4 (((+ 5 6)))))))",
    94,
  )
}

running 11 tests
test test::paren ... ok
test test::literal ... ok
test test::paren_complex ... ok
test test::binary_sub ... ok
test test::binary_mul_add ... ok
test test::binary_add_mul ... ok
test test::prefix_minus ... ok
test test::binary_add ... ok
test test::binary_mul ... ok
test test::prefix_minus_mul ... ok
test test::paren_nested ... ok

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

まとめ

Prattパーサの実装は完了しました。同じアイディアで除算演算子（8 / 2）やべき乗演算子（5 ^ 2）などの演算子にも追加することができます。

2
2
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
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?