学習内容

・再帰を含む生成規則

前回との差分

前回

expr = mul("+" mul | "-" mul) *
mul = num("*" num | "-" num) *

今回

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr “)”　←new

なぜprimaryが必要なのか？
→より優先順位が高い()かっこを含む計算をするため

出力例

まずは()を使わない式をprimaryを使って表現してみる

例：2 * 4

[expr]
└── [mul]
    ├── [primary]
    │   └── [num] ── 2
    ├── "*"
    └── [primary]
        └── [num] ── 4

1 exprでmulを処理
2 mulでprimaryに基づいて2を表す
3 "*"をmulに追加
4 mulでprimaryに基づいて4を表す

例：1 + 2

[expr]
├── [mul]
│   └── [primary]
│       └── [num] ── 1
├── "+"
└── [mul]
    └── [primary]
        └── [num] ── 2

1 exprでmulを処理してprimaryに基づいて1を表す
2 exprに"+"を追加
3 exprでmulを処理してprimaryに基づいて2を表す

例：(1 + 2)

[expr]
└── [mul]
    └── [primary]
        └── "("
            ├── [expr]
            │   ├── [mul]
            │   │   └── [primary]
            │   │       └── [num] ── 1
            │   ├── "+"
            │   └── [mul]
            │       └── [primary]
            │           └── [num] ── 2
            └── ")"

1 exprでmulを処理してprimaryに基づいて"("を表す
2 かっこ内のexprで再起的に処理をしていく
3 primaryに基づいて")"が発見される

例：2 + (1 + 3 * 4)

[expr]
├── [mul]
│   └── [primary]
│       └── [num] ── 2
├── "+"
└── [mul]
    └── [primary]
        └── "("
            ├── [expr]
            │   ├── [mul]
            │   │   └── [primary]
            │   │       └── [num] ── 1
            │   ├── "+"
            │   └── [mul]
            │       ├── [primary]
            │       │   └── [num] ── 3
            │       ├── "*"
            │       └── [primary]
            │           └── [num] ── 4
            └── ")"

所感

定義がしっかり理解できれば解析はやりやすい