parsing - プログラミング言語の文法

Question

コンパイラのコースワークでこの質問がありますが、どのようにアプローチすればよいのかよくわかりません。ルーブリックで与えられたものよりも良いヒントを教えてもらえますか？

次の文法で生成されたすべてのバイナリ文字列の値が3で割り切れる値であることを示します。

ヒント：解析ツリーのノードの数値に誘導を使用します。

num -> 11 | 1001 | num 0 | num num

Answer 1

以下に 2 つのヒントを示します。

1. バイナリ表現に 0 を追加することは、2 を掛けることと同じです。

2. バイナリ表現をそれ自体に追加することは、2^N + 1 による乗算と同じです。