他们早期在算法设计和分析技术方面的合作,为这一时期出现的计算机科学理论核心贡献了重要的方法。这些算法工作侧重于处理图、字符串和序列的基本方法,与他们对编程语言的研究紧密结合在一起。他们与约翰-霍普克罗夫特(John Hopcroft)合作的奠基之作《计算机算法的设计与分析》(The Design and Analysis of Computer Algorithms)于 1974 年出版,该书不仅为数十年来标准计算机科学课程中的算法教学,而且为展示和分析研究界开发的新算法创建了概念框架。除了纳入自己的成果,该书还将一系列不同的算法编入一套通用设计方法,包括分而治之、递归、动态编程和其他早已进入计算机科学家标准工具箱的方法。
阿霍在处理形式语言方面的深厚知识使他能够为这些工具中最重要的几个做出贡献。阿霍开发了一些算法,可以高效地查找与以正则表达式表示的简单规则相匹配的文本字符串。这些算法被集成到 Unix 工具 egrep 中,后来又被集成到词法分析器 lex 中,成为一系列工具的一部分,使编译器的开发变得更快、更容易。另一款名为 fgrep 的工具通过生成特殊用途的自动机,能够在一次通过输入时搜索多个关键字,从而以极快的速度搜索输入的关键字。这依赖于 Aho-Corasick 算法,该算法最初是由 Margaret J. Corasick 为一个书目项目发明的[5]。
Yacc 是 Yet Another Compiler 编译器的缩写,由 Steve Johnson 编写,用于实现 Aho 和 Ullman 研究的 LR(k) 解析技术。它根据待识别语言的语法描述自动生成解析器代码。阿霍回忆说,它的诞生是对使用人工技术为 C 语言开发解析器这一令人沮丧的经历的回应,而 C 语言是 Unix 项目的另一个产物:"我有一块......很大的硬纸板,我通常在看电视的时候在上面进行项目集的构建,因为这是一项琐碎而又令人头疼的工作....。我把这块纸板交给史蒂夫-约翰逊(Steve Johnson),然后史蒂夫会把它编码到他的计算机程序中。过了一段时间,他开始对我感到沮丧,因为我无法做到百分之百的正确,于是他写了一个程序,将这种解析器构建技术自动化。就这样,Yacc 工具诞生了"[6]。