Books on interpreter construction

Can you recommend some books which teach how to write interpreters?

 

Log in or Sign up to hide all adverts.

I think you'd mean books on particular scripting languages that use interpreters like PHP, Perl for CGI, or Javascript, JScript*, VBScript* (*Internet Explorer only)

 

Log in or Sign up to hide all adverts.

No actually i meant books which teach you how to write interpreters. Can you recommend some? It would be highly appreciated.

 

Log in or Sign up to hide all adverts.

I doubt there are actually any books on writing interpreters. Quite simply though you'd learn a language like C++ to write either an Application (client) that serves as an interpreter or you'd write a server interpreter. Both are fairly different in construction as it's dependent on how the script is streamed to the interpreter to begin with.

(Basically the simple server interpreter method is just by writing a humble parser. Where your Parser takes an input and returns an "interpretation".)

In both cases (Server/Client) creating an interpreter is going to have a bastardised language of it's own. Obviously some of the keywords or methods that exist already in the programming language you use are going to cause restrictions. In some cases of interpreters rather than actually restricting they just turn to straight forwards usage of what's already available in that language. (i.e. Regex [Regular Expressions])

This can of course be a flaw in programming an interpreter because it leaves your interpreter open to exploitation based upon the initial programming language, so it's always a good programming strategy to sanitise your parsers and try to steer clear of using the language directly.

I'd suggest checking out www.w3.org Within it is a list of various online markup languages that have been created over the years. For instance VRML (Virtual Reality Markup Lanugage). It never really took off, however for you to view any objects created in this markup language you usually have to load a "Plugin", the Plugin's are written to interpret the language and parse them as visable objects.

I guess from that you can deduce that if you are looking to write interpreters you might want to go to www.mozilla.org and look at their Plugin development section, there you should find a forum for people that are building plugins that will be better suited to aiding you find out what you want to know about writing an interpreter.

 

What's a server interpreter? And how do i construct a "humble parser"? And what do you mean by "streamed"?

 

When I say Server interpreter I mean "Serverside" or which basically means the server does the work. For instance A simple PHP script could be written to calculate a mathematical problem and return an answer. The program would be executed on the server and the results would be return and then sent to the browser.

If it had been a client interpreter, the calculation could be written in Javascript, which would mean the whole code would be read by your browser before returning the answer.

A parser is simply a function in a programming language that is written to take an input and return an output. i.e.

Code:

<SCRIPT LANGUAGE="Javascript">
function parserTest(x){
var z= x+3;
return z;
}

document.write([COLOR="Blue"]parserTest(4)[/COLOR]);
</SCRIPT>

This example is just a simple "un-sanitized" Javascript parser that would run in most web browsers if embedded into HTML. All it does is take the number 4 from parserTest(4) and add 3 to it.

When a parser is used to interpret it can be used to take an input and convert it to an output, the output could be weighed against values or filtered against certain components. This is why it's called a Parser, interpreter's usually are written to convert humanised programming code (Script) into runtime machine code.

I said "Streamed" because I didn't want to over complex further by explaining the different "data handlers" that exist. Basically programming languages can be made to access data from multiple sources in the instance of a website you are dealing with a RAW HTML compliant feed that sends a page of data. Not all of this page is humanly understandable, some of it is meant for browsers to identify how to handle the data (if it's going to be a HTML page or need a plugin for a particular application to view the data), some of it is meant for formatting (like headers, links, images URLS etc) and then of course the plaintext information.

You can see for yourself how it looks by getting yourself a TELNET client and typing in a IP or Domain address (If the client allows Domain lookups), set it to port 80 and type GET /index.html (This won't of course work if the page doesn't exist, or your are attempting to connect to a server that doesn't exist on that port, or if they are using a different protocol. Also make sure you have local echo rigged up, or you can't see what your typing.)

As I was mentioning about Data handlers for instance this website uses some that connect to a MySQL database. There might even be instances where files are accessed to read or store data.

You'd learn about data handlers with any language.

I'd suggest learning a language rather than asking about interpreters, you can find out about interpreters later. It's up to you if you want to learn how to build applications that run on your computer (C++/C#/Python/Java) or if you want to learn how to user CGI (Common Gateway Interface) Languages that currently do the work for most websites (Perl/PHP/C). There are other older languages that you could probably start with like Basic, Visual Basic and Pascal, although I know for a fact that the local university has moved to go with Java in recent years. (Mainly due to licensing of programming lanugage environments)

 

You dont require C++ to learn how to write a simple parser. You can do it in pretty much any decent OO language out there. Off course that includes Java, Ruby. I dont know (but you CAN TRY) Haskell, OCaml as well.


Rick

 

And btw, read Books that explain Push Down Automaton and related concepts. That would help you get the basics. Then there are books that explain, bottom up parsing etc. Once you know the techniques, use your imagination to do the rest.

This book is decent :
http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1214152571&sr=1-1

Rick

 

Thanks a lot for the reply Rick and Stryder. Do you know any books who teach how to write parsers specifically? Are there any?

 

I would suggest reading a book on formal languages and grammars. When you learn what regular, context-free, and context-sensitive languages are, you will learn about the "finite automata" that recognize those languages. When you know how to construct on paper, a pushdown automaton, for example, you will realize that if you have a context-sensitive grammar, you just need to program a software state machine and a stack to do your interpreting.

So get a book on formal languages, and the whole concept of parsing should become pretty clear.

Being able to parse effectively is the first step. Then you have to actually act on the code. Probably the easiest way is to make two passes through the script you're interpreting, and build a symbol table the first time through.

I don't know what level of knowledge you have now, but writing an interpreter is probably going to require some knowledge of data structures, and especially trees.

EDIT: Oh, I guess Rick already mentioned finite automata.

 

What is a pass? The dictionary defines pass as a single complete cycle of operations, as by a machine or computer program. What does it mean?

 

Here you go dude, i found a decent book (or so i think):

http://www.amazon.com/Writing-Compilers-Interpreters-Ronald-Mak/dp/0471113530

Rick

 

But what is it as pass through a script?

 

If your interpreter works in 2 passes it might do the following: read through the file you want to interpret, and do some sort of preliminary analysis on it (so your interpreter has a way of remembering variable names, etc). That's the first pass (because the parser passes through the code). Then read through the file again (second pass) and start executing.

That's just an example though. That may or may not be a good way to do it, I didn't really put much thought into it just yet.

It will become clear as you read more about it.

 

Another example would be an Encryption script or Compression script. Either one could have multiple passes made on a file before reaching a particular level of Encryption or optimum level of Compression.

 

But why is it required to make two passes through the script i'm interpreting? And what is preliminary analysis?

 

It's not necessarily required. It's probably easier though. You'll find that as you are parsing, you have to know certain things about what comes later in the script. The only way to do that is to parse through it twice.

By primary analysis I meant gather all the information you will need in order to execute it. For example (not necessarily a complete example, just a conceptual one): you might need to parse the code once and build a table with all the variable names in it. Then when you actual interpret the script, the interpreter will have a way of keeping track of each variable and its value.

Don't take what I'm saying too literally, because it's more of just a conceptual explanation. If you haven't found a book yet, that's probably the best place to start. I can try to look for one if you still haven't found one.

 

But what is a variable and what is the value of the variable?

While there are many books on compilers, programming languages and quite a few books on formal languages and automata, there are only 3 books i could find on interpreters and parsers (this, this and this).

 

Are you able to understand Java code? If so, PM me because I still have one of my school projects where I had to write an interpreter for a very simple scripting language.

I could send you a copy of the code if it would help, and I could annotate it better and help you understand what it does.

 

dude ... care to send me a cc ?

Please Register or Log in to view the hidden image!

Rick