The recursive parser thing is definitely the best way to go about the symbolic differentiator. An initial expansion simulates the sum and product rules (along with rules for sin, cos, natural logs, etc.), while the recursive nature simulates the chain rule.
Now, if you really want to blow your mind, write a symbolic integator

I''ll let you off and assume the starting condition is (0,0). Muhaha!
Good luck. If anything, this should be a fun and educational endeavor.