Donald E. Knuth
Donald Knuth's influence in computer science ranges from the mathematical
analysis of algorithms to the creation of the TEX and METAFONT systems
for desktop publishing. His award-winning textbooks have become classics
that are often credited for shaping the field; his scientific papers
are widely referenced and stand as milestones of development over a
wide range of topics. The present volume, which is the fifth in a series
of his collected works, deals with the languages that millions of
programmers use daily to communicate with computers.
Two dozen of Knuth's classic papers on the subject are collected in this
volume, brought up to date with supplementary material, and augmented by
a previously unpublished essay on language design. Of particular interest
are his fascinating and definitive survey of the twenty languages for
programming that preceded FORTRAN I, along with three of his fundamental
papers that each launched significant subfields of computer science: (1) The
theories of LL(k) and LR(k) parsing; (2) attribute grammars to define
the meaning of languages; (3) empirical studies of user programs and
profile-based optimization. Every chapter is self-contained and accessible
to computer programmers with varied backgrounds. Readers will be able to
participate vicariously in the creation of concepts that have now become
thoroughly integrated into modern software systems.
- 1. The early development of programming languages 1
- 2. Backus Normal Form versus Backus Naur Form 95
- 3. Teaching ALGOL 60 99
- 4. ALGOL 60 Confidential 103
- 5. SMALGOL-61 115
- 6. Man or boy? 123
- 7. A proposal for input-output conventions in ALGOL 60 127
- 8. The remaining trouble spots in ALGOL 60 155
- 9. SOL—A symbolic language for general purpose systems simulation 175
- 10. A formal definition of SOL 191
- 11. The science of programming languages 205
- 12. Programming languages for automata 237
- 13. A characterization of parenthesis languages 263
- 14. Top-down syntax analysis 285
- 15. On the translation of languages from left to right 327
- 16. Context-free multilanguages 361
- 17. Semantics of context-free languages 377
- 18. Examples of formal semantics 401
- 19. The genesis of attribute grammars 423
- 20. A history of writing compilers 439
- 21. Runcible—Algebraic translation on a limited computer 457
- 22. Computer-drawn flow charts 471
- 23. Notes on avoiding ‘go to’ statements 495
- 24. An empirical study of FORTRAN programs 507
- 25. Efficient coroutine generation of constrained Gray sequences 545
- 26. Index 575
8/1/2003