[plt-scheme] Re: from hell to paradise

hendrik at topoi.pooq.com wrote:

> Perhaps I shouldn't have said you need to know both the LR and the 
> recursive descent methods.  It is not true any more.  You certainly did 
> need to know both in the 70's and 80's, when I did most of my compiler
> writing (Algol 68 and C++ in case you're interested).

I think that we still have a lot of cases where Lex/YACC-style tools are 
used, and we should probably explain them somewhere in the curriculum. 
But there are alternatives -- ANTLR, packrat parsers, and parser 
generators, for example -- that also deserve attention.

> But I maintain that they are different algorithms.  Performing 
> program transformations on an algorithm, especially ones as 
> nontrivial as you describe, really does transform it into a different 
> algorithm.

They are different algorithms. But presenting them in a unifying 
framework means they are not separate mysteries any more. We do this 
with other "umbrellas" -- depth-first search, or dynamic programming. 
It's clear to me that umbrella should be functional for parsing. I don't 
think anyone presents quicksort as an iterative algorithm with an 
explicit stack any more, do they? Not without discussing the recursive 
version first. Why are we still doing this for parsing?

In the second-year course at my institution that covers such matters, I 
don't think the phrase "recursive descent" is used. They see LL(1) and 
LL(k) algorithms with while loops and tables. That is because the course 
was designed for Java programmers whose understanding of recursion was 
limited to nonexistent. We are no longer using Java, and I hope a more 
functional approach will be possible -- though I have colleagues who 
begrudgingly let us use Scheme in first year, but believe that it should 
not be allowed to taint anything after that. --PR