導出

1. 3の倍数である2進数を生成するCFG を使って、10010(2)=16+2=18(10)を導出する。

   M => M₀ => M₀0 => M₁10 => M₂010 => M₁0010 => 10010

2. 次のようなBNFで書かれた「式」の定義を考える。

   <式> ::= <式> + <項> | <項>

   <項> ::= <項> * <係数> | <係数>

   <係数> ::= ( <式> ) | 名標

   例えば ある式、名標*(名標+名標) は次のように導出できる。

   式 => 項 => 項*式 => 項*項 => 項*係数 => 項*(式) => 項*(式+項) => 項*(式+係数) => 項*(式+名標) => 項*(項+名標) => 項*(係数+名標) => 項*(名標+名標) => 係数*(名標+名標) => 名標*(名標+名標)

構文木