Want to get started - would like to write a simple interpreter

[Carl D. Cravens]

I'm 28, have been programming since I was 14, am in the tail end of my
junior year as a CS major... but I've never really encountered the
material necessary to learning how to write my own interpreter or
compiler. (A class I'm taking now is about 'generic' theory of how
programming languages work, and though it's applicable here, it
doesn't have any practical, hands-on stuff.)

I want to write an interpreter for a very simple language. (A personal
project that you might find silly if I actually told you what it was
for.) If I wanted to write just a compiler, I'd buy the dragon book
(despite it's hefty price), but I'm not sure how useful this'd be.
I've got a book called WRITING INTERACTIVE COMPILERS AND INTERPRETERS,
by P. Brown (1979) but it's nearly all theory with no practical
examples. (I don't want an interactive interpreter... this is kind of
a scripting language.)

Can anyone give me some pointers on where to find the kind of
information I want? Will a book on compilers help me to write an
interpreter? (There are tons of interpreters out there... why does
there seem to be so little literature?)

Thanks in advance.
[Compilers and interpreters have a lot in common, so compiler books will help,
but you're right, there's surprisingly little written on interpreter building.
-John]

--
Send compilers articles to comp...@iecc.com,
meta-mail to compiler...@iecc.com.

[A Johnstone]

Carl D. Cravens (rave...@southwind.net) wrote:
: I want to write an interpreter for a very simple language.

The RDP distribution includes a simple language called mini-plus which
is written as a set of pretty simple semantic actions embedded in a
grammar. You might find the manual a useful tutorial in the writing of
interpreters.

RDP version 1.5 is presently in beta release. You might prefer the
stable 1.4 version. Look at

http://www.dcs.rhbnc.ac.uk/la/la.html

or go the archive at

ftp://ftp.dcs.rhbnc.ac.uk/pub/rdp/

Adrian

--
Dr Adrian Johnstone, Dean of the Science Faculty, Dept of Computer Science,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email: adr...@dcs.rhbnc.ac.uk Tel: +44 (0)1784 443425 Fax: +44 (0)1784 443420

[Norman Hilton]

: I want to write an interpreter for a very simple language.

: Can anyone give me some pointers on where to find the kind of
: information I want?

Try "Constructing Language Processors For Little Languages" by Randy
M. Kaplan, published by John Wiley and Sons Inc., ISBN 0-471-59754-6.

I have it but have not read it yet.

Norm (nor...@kbss.bt.co.uk)

[Carl D. Cravens]

>: I want to write an interpreter for a very simple language.

Thanks to everyone who's given me helpful pointers.

For those who might keep track of this info, I found to articles with
source code on compilers in Dr. Dobb's Journal. (On CD-ROM.)

May 89, C PROGRAMMING column, the S-Interpreter : implements a sub-set
of C as a scripting language for a terminal program.

Aug 89, a Little-C interpreter by Herb Schildt : a different sub-set of
C. (I can't get this one to run right... I thought it was a problem
with a extern declaration of a struct being weirdly different from the
original, but although changing that got it through the compile, it
still just freezes up on execution.)

There are probably more on on the CD, but I've not looked any further
yet.

--
Carl (rave...@southwind.net)

[Francis Burton]

In <96-1...@comp.compilers> Norman Hilton <nor...@kbss.bt.co.uk> writes:
>: I want to write an interpreter for a very simple language.

>: Can anyone give me some pointers on where to find the kind of
>: information I want?
>Try "Constructing Language Processors For Little Languages" by Randy
>M. Kaplan, published by John Wiley and Sons Inc., ISBN 0-471-59754-6.
>I have it but have not read it yet.

I bought this book on the basis of a recommendation I saw on Usenet
(probably comp.compilers) and a review at
http://frey.newcastle.edu.au/~acjbooks/Reviews/b675.r.nro and frankly
I was a little disappointed. I felt it didn't go deeply into the
subject at all, saying very little about the different ways of
handling flow control in interpreters (something which I had grappled
with myself in constructing my own "little language"). The book
suffered from the common fault of presenting too much code and too
little discursive material, at least in the chapters about the image
manipulation language. The code (disk not included) would have been
more useful if it had been tailored less to the specific application,
i.e. if a more general interpreter framework (with flow control!) had
been presented. However, I appreciate the author's choice was for
sound didactic reasons, and overall I think the book is a reasonable
introductory-level text.

If you really want to learn about elegance and power in the design of
little languages, take a look at the papers published about Lua
(metapage at http://csg.uwaterloo.ca/~lhf/lua/ ) and study the source
code. Neat!

Francis

[Paul Wilson]

Carl D. Cravens <rave...@southwind.net> wrote:
>I'm 28, have been programming since I was 14, am in the tail end of my
>junior year as a CS major... but I've never really encountered the
>material necessary to learning how to write my own interpreter or
>compiler. (A class I'm taking now is about 'generic' theory of how
>programming languages work, and though it's applicable here, it
>doesn't have any practical, hands-on stuff.)

You might have a look at my course notes/book-in-progress/html doc,
An Introduction to Scheme and its Implementation, available from

http://www.cs.utexas.edu/users/oops.

(NOTE: start with the html document, not the ASCII course notes, most
of which have been incorporated into the html document in improved
form.)

I take a fairly traditional approach to presenting a Scheme interpreter
and compiler, in Scheme. Like Abelson and Sussman's _Structure_and_
_Interpretation_of_Computer_Programs_, I introduce the language
and then an interpreter and then a compiler, although not in distinct
phases. (Each is used to reinforce the understanding of the other.)

You might also look at Friedman et al.'s _Essentials_of_Programming_
_Languages_.

Advantages of my book are:

1. I give a pretty thorough introduction to the Scheme language
so you'll know what it is you're interpreting,

2. I have a bunch of pictures that show the crucial data structures
and how they evolve,

3. It's a browsable html document, so you can cut code examples out
and paste them into an interpreter to run them.

4. For the moment, at least, it's free.

Disadvantage:

1. it's not quite finished (but people have found it usable and
helpful in its current form).

In general, the Scheme literature is pretty good at explaining
interpreters and compilers.

You find out pretty quickly that it's easy to write a toy interpreter
for Scheme, and that a simple compiler isn't much harder.

Also, my web site has a bunch of other papers on language implementation,
including a couple of surveys on garbage collectors, and a survey on
memory allocators.

--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wil...@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)

[John Carter]

On Fri, 1 Nov 1996, Carl D. Cravens wrote:

> I want to write an interpreter for a very simple language. (A personal
> project that you might find silly if I actually told you what it was
> for.) If I wanted to write just a compiler, I'd buy the dragon book

> Can anyone give me some pointers on where to find the kind of

> information I want? Will a book on compilers help me to write an
> interpreter?

I have recently completed just such an exercise. My advice is browse
the Dragon book or any book from the library that will give you the
idea of what a parser generator does. Push it into the cupboard and
download BISON and FLEX from FSF. (Comes along standard with Linux and
DJGPP)

Write a couple of play-play parsers. (I slammed a wee pin with a
sledgehammer, I used FLEX & BISON to parse a weird old mainframe style
report into nice simple x,y columns for a colleague. AWK would have
done the job but I wouldn't have learnt as much :-))

The main trick is to compile to some sort of byte code. This frees you
from the stark screaming horrors of dealing with real
assembler. (Fine, I can hack assembler if I have to, but if you just
writing an interpretor without any loud yelling speed constraints for
pity sake keep away from real assembler.)

It also frees you to choose where to put features. I have features in
my byte code you will never see in real assembler in a million years.

Make your bytecode a code for an imaginary stack machine. Like a HP
calculator.

That's my 2c worth.

PS: Does anybody have any other worthy design principles for byte
codes. I personally would love to hear them. So much of a
compiler-to-byte code + interpretor can be simplified by a good design
of byte code.

John Carter EMail: e...@dwaf-hri.pwv.gov.za
Telephone : 27-12-808-0374x194 Fax:- 27-12-808-0338

[Kim G. Frei]

On Fri, 1 Nov 1996, Carl D. Cravens wrote:
> I want to write an interpreter for a very simple language. (A personal
> project that you might find silly if I actually told you what it was

> for.) If I wanted to write just a compiler, I'd buy the dragon book ...

John Carter wrote:
>The main trick is to compile to some sort of byte code. This frees you
>from the stark screaming horrors of dealing with real
>assembler. (Fine, I can hack assembler if I have to, but if you just
>writing an interpretor without any loud yelling speed constraints for
>pity sake keep away from real assembler.)

Come to think of it, "The Unix Programming Environment" by Pike and
Kernighan has a nice example on an interpreter built along these
lines. There is a nice introduction on yacc/lex and a complete walk
through as the language evolves (starting out with basic expression
parsing then adding variables and at last functions).

-kim
--
----------------------------------------------------------------
Kim Frei Tel: +45 45 99 95 99 AVS/UNIRAS A/S
ki...@avs.uniras.dk Fax: +45 45 99 95 00 Blokken 15
DK-3460 Birkerod
Denmark

[John Lilley]

>On Fri, 1 Nov 1996, Carl D. Cravens wrote:
> I want to write an interpreter for a very simple language. (A personal
> project that you might find silly if I actually told you what it was
> for.) If I wanted to write just a compiler, I'd buy the dragon book ...

While you're at it, check out PCCTS, which generates LL(k)
recursive-descent parsers. In theory it is not as powerful as LALR(k)
generators, but in practice it *usually* makes up for it with
predicates. Plus, recursive-descent is SOOOO easy to debug. You can
start at http://www.empathy.com/pccts, which will piont you back to
the Parr Research PCCTS page and other places.

john lilley

[Ivan Kellenberger]

in order to build up a LL(1) parser, the most simple parser, check out
the books about builing up a compiler of Niklaus Wirth e.g.
Theory and Techniques of Compiler Construction. Addison-Wesley, Reading,
April 1996.
He dscribes how to design a compiler from scratch.

http://www-cs.inf.ethz.ch/Wirth/Wirth.html

hope dis helps
ivan