Beautiful Code [138]
[*] Pratt's paper is available at http://portal.acm.org/citation.cfm?id=512931; more information about Pratt himself can be found at http://boole.stanford.edu/pratt.html.
[] For a description of Floyd, see "Robert W Floyd, In Memoriam," Donald E. Knuth, http://sigact.acm.org/floyd
It might seem odd that such an obviously utopian approach to compiler construction is completely neglected today. Why is this the case? Pratt suggested in the paper that preoccupation with BNF grammars and their various offspring, along with their related automata and theorems, have precluded development in directions that are not visibly in the domain of automata theory.
Another explanation is that his technique is most effective when used in a dynamic, functional programming language. Its use in a static, procedural language would be considerably more difficult. In his paper, Pratt used LISP and almost effortlessly built parse trees from streams of tokens.
But parsing techniques are not greatly valued in the LISP community, which celebrates the Spartan denial of syntax. There have been many attempts since LISP's creation to give the language a rich, ALGOL-like syntax, including:
Pratt's CGOL
http://zane.brouhaha.com/~healyzh/doc/cgol.doc.txt
LISP 2
http://community.computerhistory.org/scc/projects/LISP/index.html#LISP_2_
MLISP
ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/68/92/CS-TR-68-92.pdf
Dylan
http://www.opendylan.org
Interlisp's Clisp
http://community.computerhistory.org/scc/projects/LISP/interlisp/Teitelman-3IJCAI.pdf
McCarthy's original M-expressions
http://www-formal.stanford.edu/jmc/history/lisp/lisp.html
All failed to find acceptance. The functional programming community found the correspondence between programs and data to be much more valuable than expressive syntax. But the mainstream programming community likes its syntax, so LISP has never been accepted by the mainstream. Pratt's technique befits a dynamic language, but dynamic language communities historically have had no use for the syntax that Pratt's technique realizes.
9.1. JavaScript
The situation changed with the advent of JavaScript. JavaScript is a dynamic, functional language, but in a syntactic sense, it is obviously a member of the C family. JavaScript is a dynamic language with a community that likes syntax. In addition, JavaScript is object oriented. Pratt's 1973 paper anticipated object orientation but lacked an expressive notation for it. JavaScript has an expressive object notation. Thus, JavaScript is an ideal language for exploiting Pratt's technique. I will show that we can quickly and inexpensively produce parsers in JavaScript.
We don't have time in this short chapter to deal with the whole JavaScript language, and perhaps we wouldn't want to because the language is a mess. But it has some brilliant stuff in it, which is worthy of your consideration. We will build a parser that can process Simplified JavaScript, and we will write that parser in Simplified JavaScript. Simplified JavaScript is just the good stuff, including:
Functions as first-class objects
Functions are lambdas with lexical scoping.
Dynamic objects with prototypal inheritance
Objects are class-free. We can add a new member to any object by ordinary assignment. An object can inherit members from another object.
Object literals and array literals.
This is a very convenient notation for creating new objects and arrays. JavaScript literals were the inspiration for the JSON data interchange (http://www.JSON.org) format.
We will take advantage of JavaScript's prototypal nature to make token objects that inherit from symbols, and symbols that inherit from an original