OT: Programming Language Creation Books

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

OT: Programming Language Creation Books

Matt Holmes
Hi everyone,
 
I have a really quick OT question for you guys. I really like Lua, I enjoy scripting in it, but being the curious fellow that I am, I force myself to learn how everything that I use works, thus, through my use of Lua I am attempting to learn how to write my own programming language, as sort of an "I knew I could actually do it" sort of situation. This language is not meant for distribution, and is simply to see if I can do it. I of course could just copy the entire Lua lexer/parser/generator/vm, but that would teach me nothing. Instead, I would like to know if any of you had any recommendations for good books to read to learn about writing a programming or scripting language.
 
I understand the lexing and parsing part of the process (I think at least, Lua is a LR(1) parser right? Left->right, one lookahead token? That is what I got from looking at the code and given my understanding of that kind of parser. Lua on the other hand doesn't seem to use the shift/reduce methodology, or I am just missing something entirely, but anyways, this is off on a tangent ;).
 
I really need a decent book on the parsing -> code generation -> VM part of it all, or at least some good resources on the net to read. Lua's style is fine, as is a register based VM setup. I am not out ot learn the way that EVERY language works, just why Lua works internally the way it does :) If there are any "Golden Books" of language creation (like The C++ Language is a "Golden Book" for any C++ programmer, because its kind of a de factor standard book to own), I would like to pick them up :)
 
Thanks in advance guys, and thanks for tolerating my odd ramblings :)
 
Matt "Kerion" Holmes
 
Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Erik Hougaard
----- Original Message -----
I really need a decent book on the parsing -> code generation -> VM part of
it all, or at least some good resources on the net to read. Lua's style is
fine, as is a register based VM setup. I am not out ot learn the way that
EVERY language works, just why Lua works internally the way it does :) If
there are any "Golden Books" of language creation (like The C++ Language is
a "Golden Book" for any C++ programmer, because its kind of a de factor
standard book to own), I would like to pick them up :)


The "Dragon Book" ISBN 0201100886 is *the* bible :-)

/Erik


Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Matt Holmes
Excellent, just clicked "Submit" on my Amazon order for that book ;) Thanks
much! :)

----- Original Message -----
From: "Erik Hougaard" <[hidden email]>
To: "Multiple recipients of list" <[hidden email]>
Sent: Friday, August 17, 2001 7:51 AM
Subject: Re: Programming Language Creation Books


> ----- Original Message -----
> I really need a decent book on the parsing -> code generation -> VM part
of
> it all, or at least some good resources on the net to read. Lua's style is
> fine, as is a register based VM setup. I am not out ot learn the way that
> EVERY language works, just why Lua works internally the way it does :) If
> there are any "Golden Books" of language creation (like The C++ Language
is
> a "Golden Book" for any C++ programmer, because its kind of a de factor
> standard book to own), I would like to pick them up :)
>
>
> The "Dragon Book" ISBN 0201100886 is *the* bible :-)
>
> /Erik
>


Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Reuben Thomas-4
> Excellent, just clicked "Submit" on my Amazon order for that book ;) Thanks
> much! :)

Another more modern book with a good reputation (and I've read some of it,
and agree with it on the strength of that) is "Modern compiler
implementation in ML" (there are versions in other languages) by Appel.

It has a few advantages over the Dragon book: the theory is presented more
accessibly, it's more up to date, and it has plenty of code implementing
mini-OO, functional and imperative languages.

On the down side, it's probably not as exhaustive, and it's rather less
rigorous. But I think the two complement each other well.

-- 
http://sc3d.org/rrt/
L'art des vers est de transformer en beautés les faiblesses (Aragon)


Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Matt Holmes
Thanks for the name of the book Reuben, but I have a question. Why did you
recommend the ML version, and not say, the C version (C being Lua's
implementation language)? I am just curious, because there are several
different "implementations" of the book, including a language independent
one.

Matt "Kerion" Holmes

----- Original Message -----
From: "Reuben Thomas" <[hidden email]>
To: "Multiple recipients of list" <[hidden email]>
Sent: Friday, August 17, 2001 8:07 AM
Subject: Re: Programming Language Creation Books


> > Excellent, just clicked "Submit" on my Amazon order for that book ;)
Thanks
> > much! :)
>
> Another more modern book with a good reputation (and I've read some of it,
> and agree with it on the strength of that) is "Modern compiler
> implementation in ML" (there are versions in other languages) by Appel.
>
> It has a few advantages over the Dragon book: the theory is presented more
> accessibly, it's more up to date, and it has plenty of code implementing
> mini-OO, functional and imperative languages.
>
> On the down side, it's probably not as exhaustive, and it's rather less
> rigorous. But I think the two complement each other well.
>
> --
> http://sc3d.org/rrt/
> L'art des vers est de transformer en beautés les faiblesses (Aragon)
>


Reply | Threaded
Open this post in threaded view
|

RE: Programming Language Creation Books

Ryan Bright
In reply to this post by Matt Holmes
> From: [hidden email]
> Hi everyone,
Hello.

> I understand the lexing and parsing part of the process (I think
> at least, Lua is a LR(1) parser right? Left->right, one lookahead
> token?
First of all, you generally wouldn't describe a parser as being LR(1).  The
terms LL, SLR, LR, and LALR are used describe grammars, which, in turn,
define languages.  A parser accepts a string and then determines whether
that string is in the a given language.

I'm no expert on Lua, but it looks like it uses a pretty straight forward
top-down, predictive parsing method (as most hand-written parsers do).  This
method will accept LL grammars (ie, Left-to-right scan, Left-most
derivation), but not LR (Left-to-right scan, Right-most derivation).  LL is
a subset of LR.

> That is what I got from looking at the code and given my
> understanding of that kind of parser. Lua on the other hand
> doesn't seem to use the shift/reduce methodology, or I am just
> missing something entirely, but anyways, this is off on a tangent ;).
Shift/reduce is related to bottom-up parsing methods.  These methods are
usually more powerful (in terms of dealing with a wider range of grammars,
usually LR(1) or LALR(1)), and can be found implemented in most
compiler-compilers, like Yacc or Bison.  I believe Lua recently switched
from using a Yacc definition to a hand-crafted parser in the interests of
compilation speed.

> I really need a decent book on the parsing -> code generation ->
> VM part of it all, or at least some good resources on the net to
> read.
Other than the VM part, the definitive work is The Dragon Book, or Aho,
Sethi, and Ullman's Compilers: Principles, Techniques, and Tools.  I've
found it to be indispensible.  Check out the comp.compilers FAQ for more
book reviews:
	http://compilers.iecc.com/faq.txt

If you're interested in a Hand-Written Parsers for Dummies type of approach,
however, Jack Crenshaw's Let's Build a Compiler is a fairly popular series,
but unfinished:
	http://compilers.iecc.com/crenshaw/

> Thanks in advance guys, and thanks for tolerating my odd ramblings :)
No problem.  Good luck.

--
Ryan Bright



Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Brian Mitchell-2
In reply to this post by Reuben Thomas-4
There is also an updated book by the authors of the dragon book called
compilers principles, techniques, and tools. It is quite exhaustive.


On Fri, 17 Aug 2001, Reuben Thomas wrote:

> > Excellent, just clicked "Submit" on my Amazon order for that book ;) Thanks
> > much! :)
>
> Another more modern book with a good reputation (and I've read some of it,
> and agree with it on the strength of that) is "Modern compiler
> implementation in ML" (there are versions in other languages) by Appel.
>
> It has a few advantages over the Dragon book: the theory is presented more
> accessibly, it's more up to date, and it has plenty of code implementing
> mini-OO, functional and imperative languages.
>
> On the down side, it's probably not as exhaustive, and it's rather less
> rigorous. But I think the two complement each other well.
>
> --
> http://sc3d.org/rrt/
> L'art des vers est de transformer en beaut├ęs les faiblesses (Aragon)
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Reuben Thomas-4
In reply to this post by Matt Holmes
> Thanks for the name of the book Reuben, but I have a question. Why did you
> recommend the ML version, and not say, the C version (C being Lua's
> implementation language)? I am just curious, because there are several
> different "implementations" of the book, including a language independent
> one.

I didn't mean to recommend one over another. I was given the ML version, and
indeed I chose that one, because ML is to me, the easiest language to read
of those in which the book has been written. Consulting the list in the
book, it seems to be available in C, Java and ML. I certainly wouldn't want
it in C (and I write more C than either of the above); Java and ML are
probably about equally legible, according to taste. My tastes are more
functional, hence ML. If there had been a Haskell version, I'd've asked for
that.

-- 
http://sc3d.org/rrt/
Reality is what refuses to disappear when you stop believing in it (Dick)


Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Reuben Thomas-4
In reply to this post by Brian Mitchell-2
> There is also an updated book by the authors of the dragon book called
> compilers principles, techniques, and tools. It is quite exhaustive.

Since this is really a second edition of the first Dragon book, and also has
a dragon on the front, and was published in 1986 (i.e. long ago enough that
most people don't worry about the difference), I think this is what most
people now mean by "the Dragon book".

-- 
http://sc3d.org/rrt/
Reality is what refuses to disappear when you stop believing in it (Dick)


Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

John D. Ramsdell-3
In reply to this post by Ryan Bright
"Ryan Bright" <[hidden email]> writes:

> I'm no expert on Lua, but it looks like it uses a pretty straight
> forward top-down, predictive parsing method (as most hand-written
> parsers do).  This method will accept LL grammars (ie, Left-to-right
> scan, Left-most derivation), but not LR (Left-to-right scan,
> Right-most derivation).

I recently posted to this list a grammar for Lua that is LALR(1),
which I know to be true because Bison accepts it.  I used the
precedence feature, so it is not strictly LALR(1) as written, but one
can easily transform it into a grammar that is.  I'll share the Bison
source if you really want to verify this fact.  I assume the LALR(1)
grammar defines the same language as accepted by the parser in the Lua
4.1 alpha release because no one has contradicted this assertion.

The Lua 4.1 alpha parser is a recursive decent parser of the form that
is often used to recognize languages defined by LL(1) grammars,
however, it is still not clear to me that there exists an LL(1)
grammar for Lua.  If you study the parser, you will find it makes
syntactic decisions for assignment and call statements by inspecting
the result of parsing a simpleexp.  This syntactic decision has no
obvious reflection in an LL(1) grammar.  I confess that once I found
an LALR(1) grammar, I have not made much of an effort to produce an
LL(1) grammar.  For the purposes of documentation, the LALR(1) grammar
is fine.

I would very much like to see an LL(1) for the Lua language.  
Please share one if you can generate one.

John

Reply | Threaded
Open this post in threaded view
|

Re: Programming Language Creation Books

Chris Tavares
In reply to this post by Erik Hougaard
>
> The "Dragon Book" ISBN 0201100886 is *the* bible :-)
>

And, like most bibles, is *extremely* difficult to figure out without
a priest (i.e. college professor) interpreting it for you. I took a
compiler class recently, and we used this as a textbook. It was, for
the most part, incomprehensible (the book, not the class).

A good place to start would be "Constructing Language Processors for
Little Languages" by Randy M. Kaplan, ISBN: 0471597538. It covers the
basics of lexing and parsing very, very well, and also discusses the
issues behind language design in the process. The author unfortunately
gives little attention to the runtime aspects of language construction
(for example, there's no discussion on how to execute a loop) but the
material that is there is MUCH more approachable than the dragon book.

-Chris

P.S. If this message comes out in all sorts of weird HTML, I
apologize. I *think* I've got it set to plain text, but who knows what
Outlook will really do?



Reply | Threaded
Open this post in threaded view
|

RE: Programming Language Creation Books

brucedickey
In reply to this post by Erik Hougaard
I agree that the dragon book is quite opaque.

An excellent book is Allan Holub's "Compiler Design in C". Besides theory,
this book presents practical implementation details that many other books
leave as an exercise for the reader. I highly recommend it. Also makes
excellent ballast for non-CS types. See Holub's site: http://www.holub.com.

A good online theory book is "Parsing Techniques - A Practical Guide" by
Dick Grune and Ceriel J.H. Jacobs at http://www.cs.vu.nl/~dick/PTAPG.html.

I like Finkel's "Advanced Programming Language Design". It covers design
aspects of many types of languages. Online at
http://cseng.aw.com/book/related/0,3833,0805311912+20,00.html.

There is "Compilers and Compiler Generators an introduction with C++" by
P.D. Terry, Rhodes University, 1996 
online at http://scifac.ru.ac.za/compilers/. I have not read it.

Bruce


> -----Original Message-----
> From: Chris Tavares [[hidden email]]
> Sent: Friday, August 17, 2001 11:42 AM
> To: Multiple recipients of list
> Subject: Re: Programming Language Creation Books
> 
> 
> >
> > The "Dragon Book" ISBN 0201100886 is *the* bible :-)
> >
> 
> And, like most bibles, is *extremely* difficult to figure out without
> a priest (i.e. college professor) interpreting it for you. I took a
> compiler class recently, and we used this as a textbook. It was, for
> the most part, incomprehensible (the book, not the class).
> 
> A good place to start would be "Constructing Language Processors for
> Little Languages" by Randy M. Kaplan, ISBN: 0471597538. It covers the
> basics of lexing and parsing very, very well, and also discusses the
> issues behind language design in the process. The author unfortunately
> gives little attention to the runtime aspects of language construction
> (for example, there's no discussion on how to execute a loop) but the
> material that is there is MUCH more approachable than the dragon book.
> 
> -Chris
> 
> P.S. If this message comes out in all sorts of weird HTML, I
> apologize. I *think* I've got it set to plain text, but who knows what
> Outlook will really do?
> 
>