唐纳德·克努特的其它贡献

此外，高德纳还有许多“小创造”。计算机科学技术中两个最基本的概念：“算法”(Algorithm)和“数据结构”(Data Structure)就是高德纳于29岁时提出来的。1973年他首创双向链表。在编译器设计方面，著名的LR(k)文法也是高德纳在对自左至右、自底向上的移进一归约分析进行了深刻剖析的基础上，经过高度概括和集中以后发明的，它表示具有从左(L)到右(R)的分析而向前看k个符号，以确定所要进行的归约和应用何种语法解释。LR(k)文法的识别效率高，在从左至右扫描输入串时，就能发现其中的语法错误，并能准确地指出出错位置，因此被广泛应用。此外，利用LR(众)文法还能正确区分像Flying planes is fun和Flying planes can crash这类句子(前一个句子“开飞机很有趣”中flying是动名词，而后一个句子“飞行中的飞机可能出事”中Flying是现在分词当形容词)。以著名的巴克斯—诺尔范式为基础的“属性文法”(attribute grammar)也是高德纳首先提出来的。属性文法在普通的上下文无关文法(context-free grammar)的基础上，对每一个终结点或非终结点加上一些属性，和对这些属性进行估值的语义规则集，从而形成一种新的、有更强表达与描述能力的文法。其中属性是由的有序偶对组成的。属性的内容则可包括模式标识符表等。
在算法方面，有他和他的学生共同设计的诸如Knuth-Bendix算法和Knuth-Morris-Pratt算法，前者是为了考察数学公理及其推论是否“完全”而构造标准重写规则集(rewriting rule set)的算法，曾成功地用它解决了群论中的等式的证明问题，是定理机器证明的一个范例。后者是在文本中查找字符串的简单而高效的算法。此外，高德纳还设计与实现过最早的随机数发生器(random number generator)。