CODEWITHSUNDEEP
parsingcompiler-constructionbinary-treegrammar
Sorin Cioban
Sorin Cioban

Reputation: 2225

Programming language grammar

I have this question in a Compilers coursework but I don't really know how to approach it. Could anyone please give me a better hint than what was given in the rubric?

Show that all binary strings generated by the following grammar have values divisible by 3.

Hint: use induction on the numerical values for nodes in the parse tree.

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

Upvotes: 2

Views: 621

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272497

Here are two hints:

  1. Appending a 0 to a binary representation is equivalent to multiplication by 2.

  2. Appending a binary representation to itself is equivalent to multiplication by 2^N + 1.

Upvotes: 10

Related Questions