Message-ID: <20030905234354.24976.qmail@plover.com> Subject: Chapter VII in progress, Chapter IX almost done Organization: Plover Systems Date: Fri, 05 Sep 2003 19:38:50 -0400 From: Mark Jason Dominus If you forgot what this list is about, or you don't know why you're getting this message, please see http://perl.plover.com/book/ To unsubscribe, send a blank message to mjd-book-unsubscribe@plover.com. ---------------------------------------------------------------- It's been a long time since I sent an update, so I thought I'd report in. The summer was very busy for me (I gave classes and talks in six countries) so I didn't make much progress on the book. Now that I'm at home again, things are moving along. Chapter VII was supposed to be about "Higher-order functions: merging, filtering, and reducing", and Chapter VIII about "Higher-order functions: composition". I decided a while back to turn these into a single chapter. That single chapter caused me a lot of trouble. I finally realized that my problem with it was that I wasn't sure what to say, because, unlike with the other chapters, I didn't really have a single practical point I was driving at. So I decided to put the chapter aside for a while. I thought perhaps if I could see what sorts of applications came up later in the book, I would have a better idea of what I would need to talk about in VII. So VII remains in a somewhat incomplete state, about 21 pages long, which is why I haven't sent it out on this mailing list as I thought I would. I started on Chapter IX instead, and it's going along very well. It's about parsing techniques, and I think it's really excellent. There's a detailed discussion of lexing. One missing feature in Perl is that the $/ variable must be a plain string; it can't be a regex. In the lexing section, I show how to fix this; it's surprisingly tricky. Chapter IX will also have a thorough discussion of recursive descent parsing, including techniques for making recursive descent parsing work even in the cases that it traditionally doesn't handle well. For example, if you give Damian Conway's "Parse::RecDescent" module the following input: use Parse::RecDescent; my $g = Parse::RecDescent->new(qq{rule: rule subrule | "bar" subrule: "foo"}); it will fail: ERROR: Rule "rule" is left-recursive. The problem is that when a recursive-descent parser tries to parse a 'rule', it sees that a 'rule' can consist of another 'rule' followed by a 'subrule', and it responds by calling the parser for 'rule' recursively. This puts it into an infinite recursion. Examples of parsers I'm planning to show in IX include arithmetic expressions, regexes, and database queries. I'll attach the regex parser to the string generator of VI, and get a function which, given any regex, efficiently generates a list of all the strings that it will match. I'll attach the database query parser to the database query system that I've developed in IV and VII to build a full query system. I think I might want to take an excursion into code generation. The obvious example is to compile arithmetic expressions into some sort of code, but I think it might be more interesting to demonstrate a database query optimizer. I might also implement a program that generates a parser, given a grammar for that parser; then I'll use the parser generator to generate the parser for itself. I considered showing how to build a bottom-up parser (a la Yacc) but it will probably involve more computer theory than I'm willing to put in. Also I told my editor that I'll be done with IX by Tuesday. Thanks to all of you for your patience and interest. I expect to finish the book by the end of the year. I'll send another report when IX is ready.