Subj : Re: How-to on writing an interpreter?
To   : comp.programming
From : Phlip
Date : Sat Jul 16 2005 05:05 am

C. Rebert wrote:

> I'm trying to implement an interpreter for a programming language, but
> so far haven't been able to find any good materials on how to write a
> simple stack-based interpreter. I would appreciate it if someone could
> point me to some resources on writing such an interpreter. I'd be open
> to buying such materials, as long as they aren't ludicrously expensive.

Industrial-strength parsers come from parser generators like Lex and Yacc.
Learn them and live them; they have a thriving corpus and community. They
are hard to learn (only two new languages, then you gotta link to their
output), but such parser generators provide the blazing speed that modern
compiling requires. All else I recall to Google are ANTLR & Bison. There are
more, and all are variously productized and priced.

The other end of parsing is DIY. You can easy write a parser using
Test-Driven Development by writing tests for each feature and passing each
test by writing the feature, then refactoring it towards the recursive
descent parser pattern. Here are two projects where I belted out a
just-good-enough recursive descent parser in a couple hours:

    http://c2.com/cgi/wiki?MsWindowsResourceLint
    http://www.xpsd.org/cgi-bin/wiki?RecursiveDescentParserCpp

TDD makes just-good-enough safe because when you need more features the
tests make them easier to add.

A third alternative is to use an OO language with sufficient power and
syntactic subtlety that you can write your language by specializing a subset
of that language. I did this for LSystems, a fractal generating technique
whose parsers traditionally were primitive, by writing each action as a Ruby
method which adds an object to a list (following the Interpreter Design
Pattern). That lead to this:

    http://flea.sourceforge.net/

-- 
  Phlip
  http://www.c2.com/cgi/wiki?ZeekLand

.