再帰下降構文解析法(recursive descent parsing)

program    := stmt*             // programとはstmtの0回以上の繰り返しである。
stmt       := expr ";"         // stmtはexprに;を加えたものである。
expr       := assign            // exprはassign である。
assign     := equality ("=" assign)?
equality   := relational ("==" relational | "!=" relational)*
relational := add ("<" add | "<=" add | ">" add | ">=" add)*
add        := mul ("+" mul | "-" mul)*
mul        := unary ("*" unary | "/" unary)*
unary      := ("+" | "-")? primary
primary    := num | ident | "(" expr ")"

コンパイラに新しい文法が加わった。4つめあたりから複雑だ。

assign := equality("=" assign)?

assignとはequalityか、あるいはequality=assignである。これはいわゆる代入式の定義だろうか。

equality := relational ("==" relational | "!=" relational)*

equalityはrelationalに0回以上の==relationalか!=relationalをくわえたものである。これは恒等式の定義か。

relational := add ("<" add | "<=" add | ">" add | ">=" add)*

relationalはaddに0回以上の以下のものをどれかを付け加えたものである。add , >=add これは比較演算式か。

あとは既存のものと同じだが、最後のprimaryが、

primary    := num | ident | "(" expr ")"

numかidentか(expr)のどれかであると拡張されている。identは識別子のことだろうか。identとnumは終端記号なのだろう。そのうち文字列もここに加わりそうだ。


なんとなく読み解けはするが、この生成規則はどうやって設計するのだろうか。調べてみると演算子の優先度は下に行くほど高くなっている。3つめのexpr=assignというのは謎だ。これ必要ある?ある対象がexprならば、それらはすべて例外なくassignであるが、逆は成立しない、つまりassignではあるけどexprではない対象が存在しうるということだろうか。論理的にはそうなるが。

これらはなにかしらすべて式の定義をしているという理解でいいのだろうか。