ステップ3：式と再帰

再帰的な文法を構築し、式解析のための演算子の優先順位を処理します。

課題

2*(3+4)のような式を解析するには以下が必要です：

  1. 再帰 - 式は他の式を含むことができる
  2. 優先順位 - 乗算は加算より強く結合する
  3. 結合性 - 2+3+4は(2+3)+4としてグループ化されるべき

Xarpegは再帰のためのref { }と、演算子の優先順位のためのleftAssociative/rightAssociativeヘルパーを提供します。

式パーサの例

以下は、再帰と優先順位を持つ完全な算術式パーサです：

import io.github.mirrgieriana.xarpeg.*
import io.github.mirrgieriana.xarpeg.parsers.*

val expr: Parser<Int> = object {
    val number = +Regex("[0-9]+") map { it.value.toInt() } named "number"
    val paren: Parser<Int> = -'(' * ref { root } * -')'
    val factor = number + paren
    val mul = leftAssociative(factor, -'*') { a, _, b -> a * b }
    val add = leftAssociative(mul, -'+') { a, _, b -> a + b }
    val root = add
}.root

fun main() {
    check(expr.parseAll("2*(3+4)").getOrThrow() == 14)
    check(expr.parseAll("5+3*2").getOrThrow() == 11)
}

コードの理解

ref { }による前方参照

parenパーサは、後で定義されるrootを参照する必要があります。前方参照を作成するにはref { }を使用します（例：val paren: Parser<Int> = -'(' * ref { root } * -')'）。

重要： refを使用するプロパティには、型解決のために明示的な型宣言（Parser<Int>）が必要です。

演算子の優先順位

パーサを最高優先順位から最低優先順位まで階層化します：

各レベルは前のレベルの上に構築され、正しい優先順位を保証します：

結合性ヘルパー

leftAssociative(term, operator) { left, op, right -> result }は左結合演算子チェーンを構築します。

これは明示的な再帰なしで2+3+4+5のような式を((2+3)+4)+5として処理します。

パラメータ：

同様に、rightAssociativeは右からグループ化します：2^3^4 → 2^(3^4)。

by lazyを避ける

再帰パーサにby lazyを使用しないでください—無限再帰を引き起こします。ref { }メカニズムはすでに遅延評価を処理しています。

by lazyは、再帰とは無関係なまれな初期化エラーの最後の手段としてのみ使用してください。

複数の優先順位レベル

より多くの演算子のためにパターンを拡張します：

import io.github.mirrgieriana.xarpeg.*
import io.github.mirrgieriana.xarpeg.parsers.*

val expr: Parser<Int> = object {
    val number = +Regex("[0-9]+") map { it.value.toInt() } named "number"
    val paren: Parser<Int> = -'(' * ref { root } * -')'

    val factor = number + paren
    val power = rightAssociative(factor, -'^') { a, _, b ->
        var result = 1
        repeat(b) { result *= a }
        result
    }
    val mulOp = (+'*' map { '*' }) + (+'/' map { '/' })
    val mul = leftAssociative(power, mulOp) { a, op, b ->
        if (op == '*') a * b else a / b
    }
    val addOp = (+'+' map { '+' }) + (+'-' map { '-' })
    val add = leftAssociative(mul, addOp) { a, op, b ->
        if (op == '+') a + b else a - b
    }
    val root = add
}.root

fun main() {
    check(expr.parseAll("2^3^2").getOrThrow() == 512)  // 右結合：2^(3^2)
    check(expr.parseAll("10-3-2").getOrThrow() == 5)   // 左結合：(10-3)-2
}

単項演算子

前処理で前置/後置演算子を処理します：

import io.github.mirrgieriana.xarpeg.*
import io.github.mirrgieriana.xarpeg.parsers.*

val expr: Parser<Int> = object {
    val number = +Regex("[0-9]+") map { it.value.toInt() } named "number"
    val paren: Parser<Int> = -'(' * ref { root } * -')'

    // 単項マイナス
    val unary: Parser<Int> = (-'-' * ref { unary } map { -it }) + number + paren

    val mul = leftAssociative(unary, -'*') { a, _, b -> a * b }
    val add = leftAssociative(mul, -'+') { a, _, b -> a + b }
    val root = add
}.root

fun main() {
    check(expr.parseAll("-5+3").getOrThrow() == -2)
    check(expr.parseAll("-(2+3)").getOrThrow() == -5)
}

重要なポイント

次のステップ

パーサがエラー、キャッシング、デバッグ情報をどのように処理するかを学びます。

→ ステップ4：実行時の動作