By Terence John Parr
A few years ago, I implemented a programming language called NewtonScript, the application development language for the Newton(R) operating system. You may not have heard of NewtonScript, but you’ve probably heard of the tool I used to implement it: a crusty old thing called YACC.
YACC--like the C language, Huffman coding, and the QWERTY keyboard--is an example of a standard engineering tool that is standard because it was the first "80% solution". YACC opened up parsing to the average programmer. Writing a parser for a "little language" using YACC was vastly simpler than writing one by hand, which made YACC quite successful. In fact, it was so successful, progress on alternative parsing tools just about stopped.
Not everybody adopted YACC, of course. There were those who needed something better. A lot of serious compiler hackers stuck with hand-coded LL parsers, to get maximum power and flexibility. In many cases, they had to, because languages got more and more complicated--LALR just wasn’t good enough without lots of weird hacks. Of course, these people had to forego the advantages of using a parser generator.
So if your language is simple, you use YACC. If your language is too complex, or if you want good error recovery, or if performance is critical, you write a parser from scratch. This has been the status quo for about 20 years.
Terence Parr and PCCTS have the potential to jolt us out of this situation. First, Terence pursued and formalized a new parsing strategy, called predicated LL(k), that combines the robustness and intelligibility of LL with the generality of LALR. Second, he implemented a parser generator, called ANTLR, that makes this power easy to use. Even the dedicated hand-coders may change their minds after a close look at this stuff. Finally, for those situations where you need to traverse a parse tree (and who doesn't?), SORCERER applies the ANTLR philosophy to that problem.
The result is a tool set that I think deserves to take over from YACC and LEX as the default answer to any parsing problem. And as Terence and others point out, a lot of problems are parsing problems.
Finally, let me mention that PCCTS is a tool with a face. Although it’s in the public domain, it’s actively supported by the tireless Terence Parr, as well as the large and helpful community of users who hang out on comp.compilers.tools.pccts. This book will help the PCCTS community to grow and prosper, so that one day predicated LL(k) will rule, YACC will be relegated to the history books, and Terence will finally achieve his goal of world domination.
Finally, let me mention that PCCTS is a tool with a face. Although it’s in the public domain, it’s actively supported by the tireless Terence Parr, as well as the large and helpful community of users who hang out on comp.compilers.tools.pccts. This book will help the PCCTS community to grow and prosper, so that one day predicated LL(k) will rule, YACC will be relegated to the history books, and Terence will finally achieve his goal of world domination.
