On Mar 29, 12:33 pm, glen herrmannsfeldt <g...@[EMAIL PROTECTED]
>
wrote:
> In my post I had a reference to the wikipedia article referencing
> Richard Bellman and his development of dynamic programming. But how
> many people read Bellman's paper and started implementing such
> algorithms in the 1950's?
A few. My recollection of Bellman was from Knuth, Art of Programming,
Volume 1, Notes on the Exercises, page xvii. The copyright is 1968.
Another example of dynamic programming, perhaps more directly relevant
to compilers, is the CYK parsing algorithm, from 1965, see
http://en.wikipedia.org/wiki/CYK_algorithm
> Computer science conferences on pattern matching algorithms are
> dominated by papers on biological applications, and rarely do
> you see applications to compilers.
The days I work for Google, and we do a little pattern matching too.
But I guess I don't think of dynamic programming as restricted to
pattern matching. The examples from my grad school algorithms book
(Aho, Hopcroft, and Ullman, 1974) focus on finding the product of many
matrices. And there's Aho and Johnson's paper on optimal evaluation
of expressions, from 1975. (The work you cited from LCC descends from
Aho and Johnson). And there's the BURS theory, a big favorite of
mine. Plenty of good compiler stuff!
Preston
|
