At the last regular London Ruby User Group meetup, James Coglan gave a talk on how to implement a Scheme interpreter in 15 minutes. He recorded a video of the coding in progress beforehand so he could focus on the narration so unfortunately the video (available in a higher resolution here from Vimeo) is without sound. There is, however, a ZIP file of HTML slides available to help you follow along.
Naturally, building an arbitrary interpreter from scratch without having a design in mind in 15 minutes is impossible (except for the most trivial of cases) but James' demo is nonetheless impressive. James' knowledge and examples are built upon his work on Heist, a Ruby-powered Scheme interpreter that has somewhat more functionality than the 15 minute version.
The parsing is taken care of primarily by Treetop, a syntactic analysis / parser creation DSL for Ruby. Without Treetop this would be a three hour demo rather than a 15 minute one, so if you haven't checked out Treetop yet, please do - it deserves a lot more praise than I've seen it get so far.
Also worth seeing.. Beginning iPhone Programming Workshop For Rubyists. A companion class to the FutureRuby conference. Toronto, July 9-10,