CSLI Publications logo
new books
knuth books
for authors
CSLI Publications
Selected Papers on Computer Languages cover

Selected Papers on Computer Languages

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


ISBN (Paperback): 1575863820 (9781575863825)
ISBN (Cloth): 1575863812 (9781575863818)

Prof. Knuth's page on this book including table of contents and errata

Add to Cart
View Cart

Check Out

Distributed by the
University of
Chicago Press

pubs @ csli.stanford.edu