Unix考古记：一个“遗失”的shell

　　谨以此文纪念伟大的计算机科学巨匠Ken Thompson和Dennis Ritchie，并同时向其他所有为Unix发展做出贡献的黑客致敬。

历史的尘埃

　　Unix作为一个举世闻名的操作系统已有40余年的历史，围绕着这个古老的操作系统的发展又衍生出了一系列外围软件生态群，其中一个非常重要的组件就是shell。它是操作系统最外层的接口，负责直接面向用户交互并提供内核服务，包括命令行接口(CLI)或图形界面接口(GUI)两种形式。以CLI为例，它提供一套命令规范，是一种解释性语言，将用户输入经过解释器(interpreter)输出使其转化成真正的系统调用，实现人机交互的功能。

　　和操作系统一样，shell也经历了一个漫长的演变史。如今大部分资料讲述最古老的shell都是从1977年的Bourne Shell说起的，它最初移植到Unix V7上，被追认整个shell家族成员的鼻祖，后来的种群都是从其身上分支出来的。

　　对于1977年之前的历史很多资料大多一笔带过或略过不提。事实上，第一个移植到Unix上的shell却不是Steve Bourne写的，早在1975年5月，贝尔实验室就对外发布了第一个广泛传播的Unix版本——Unix V6（之前开发的版本只供内部研究之用），其根目录下的/bin/sh是第一个Unix自带的shell，由Ken Thompson写的，因此也被称为Thompson Shell。甚至，更早可以追溯到1971年的时候，Thompson Shell就作为一个独立于内核的应用程序而实现了，只不过从1975年正式问世到1977年被取代，短短两年的寿命使得它很少为大多数人所认识。

　　关于Thompson Shell被取代的原因在后文中会给出说明，这里着重介绍一下该shell本身的一些技术细节。坦白讲，关于Thompson Shell的资料有点稀缺，但至少还能从网上找到源代码和在线文档。Thompson Shell本身是由一个不足900行代码的解释器和一些外部命令工具组件(utilities)构成，用K&R C写成，下面给出各个组件的相关源码和文档链接。

• 解释器sh：解析各种shell命令，包括内置命令和外部命令；源码sh.c；安装路径/bin/sh；手册sh(1)。

• 内置命令手册包括chdir(1)，login(1)，newgrp(1)，shift(1)，wait(1)。

下面是外部命令：

• exit命令：退出一个文件；源码exit.c；安装路径/bin/exit；手册exit(1)。

• goto命令：在一个文件内跳转shell控制流程；源码goto.c；安装路径/bin/goto；手册goto(1)。

• if命令：条件判断表达式，是test命令的前身；源码if.c；安装路径/bin/if), 手册if(1)。

• glob命令：扩展命令参数通配符；源码glob.c；安装路径/etc/glob；手册glob(8)。

命令结构和规范

　　尽管后来遭“埋汰”，Thompson Shell仍有着不容否认的历史地位，其最大的价值在于它奠定了shell命令语言结构和规范的基础，而且其解释器具有跨平台的可移植性，并影响到了后来包括Bourne Shell在内的各种脚本语言设计实现。下面我们就以其中5个特性重温一些大家已经耳熟能详的命令规范，你也可以通过sh(1)手册查看原始资料。

• 过滤器/管道线(filter/pipeline)。这绝对是要载入Unix史册的发明，创立者是Douglas McIlroy，Thompson Shell引入并实现了这个伟大的概念——一个或多个命令组成一根过滤器的链条，由’|'或’^'符号分隔。除最后一个命令之外，每个命令的标准输出都被作为下一个命令的标准输入。这样每个命令都作为一个独立的进程来运行，并通过管道与邻近的进程相连接。圆括弧内的命令序列整体上可以替代单个命令作为过滤器实现，比如用户可以输入”(A;B)|C”。

• 命令序列和后台进程。分号’;'指示多个命令序列化执行。’&’符号指示该命令在后台异步执行，使得前面的管道线不必等待其终止，仅仅报告一个进程id，这样用户以后可以通过kill命令与它通信。有益于进程管理。

• I/O重定向。它利用了Unix设计上的一个重要特性——一切皆文件，用三个符号表示：”重定向输出，如果文件不存在则创建它，如果文件存在则截断它；’>>’追加模式重定向输出，如果文件不存在则创建它，如果文件存在则追加输出至末尾处。

• 通配符扩展(globbing)。通配符的概念源自于正则表达式，使得解释器智能地处理用户不完全输入，比如记不清文件名、一次性输入多个文件等。’?'匹配任意单一字符；’*'匹配任意字符串（包括空串）；成对’['和']‘定义了字符集合一个类，可匹配方括号内任意成员，用’-'两端可指定一系列连续字符匹配范围。

• 参数传递。这里主要引入了位置参数和选项参数的概念：’$n’指示shell调用的第n个参数替代；还定义了两个选项参数’-t’和’-c’，前者用于交互，导致shell从标准输入中读入一行作为用户执行的系统命令，后者指示shell将附带的下一个参数作为命令执行（可正确处理换行符），是对’-t’的补充，特别是调用者已经读取了命令其中某些字符的情况下。如果不带选项参数则直接读取文件名

解释器的原理与实现

　　接下来马上要进入核心部分了，为了搞懂shell解释器原理，我们要对其整个工作流程做个描述（这里给出一份带注解的sh.c源码剖析）。读过《编译原理》的同学知道，解释器的实现跟编译器差不多，只不过省略了生成目标代码这一步，直接将用户输入（shell命令）转化成输出（系统调用）。软件前端是一致的，包括预处理、词法扫描、语法分析和语义分析，最后还要附加一个进程管理。当然相较于现代编译器，Thompson Shell解释器在算法和规模上都要简单得多，不过原理上是相通的，何况年代上要比Lex & Yacc还要早。麻雀虽小，五脏俱全，对于初学者来说，从Thompson Shell去入手编译原理或许不失为一种好选择。

预处理(preprocessor)

　　同C预处理器需要事先将源代码中包含的宏和头文件展开一样，Thompson Shell首先需要处理命令中的选项参数和位置参数。选项参数有两种’-t’和’-c’，决定了shell从标准输入还是参数缓存中读取字符（见sh(1)）。此外字符序列中还要处理反斜杠’\’，判断是转义字符还是行接续符，前者对下一个字符设置引用标识，表明做普通字符处理，后者将紧邻其后换行符过滤掉。

　　位置参数是美元符号’$’打头的，后带一个数字，如’$n’，预处理器对shell命令参数从头开始计数，返回数字n指定的参数位置。如果遇上double’$$’，则表示当前的进程标识，调用getpid()获取。

　　注意到预处理器需要一次读取多个字符，这样就会多读一个不必要的字符。对此解释器提供了一种预读(peek)方式，即每次从输入流读取一个字符时，放入一个预读缓存里（只有一个int大小的堆栈），也叫回退(push back)。此后先从预读缓存中读取，如果缓存被读完，则从输入流中读取。

词法扫描(lexical scanning)

　　经过预处理后的字符序列将被切割成为一系列词法记号(token)，安置在token列表中，扫描器将对以下几类字符做如下处理。

• 空格和tab：简单过滤。

• 引号：需要成对出现，字符本身被过滤，一对引号之间所有字符都被设置引用标识，作为一个token。

• 元字符：如’&’，’|'等，字符本身作为一个单独token。

• 其他字符：一律填充token，直到碰上以上字符分隔为止。

　　举一个例子，当我们输入命令”(ls; cat tail) >junk”，那么token列表映像将是这样的：

语法分析(syntax parser)

　　语法分析就是将token列表中的元素作为表达式(expression)并以节点为单位构建语法树，简单命令是一个表达式，而复合命令以及命令序列是多个表达式的组合。Thompson Shell中以简单数组作为语法树的容器，实际上这是结构体的一种变形，只不过每个成员字段大小都一样（都是sizeof int）而已。一个语法树节点最多有6个字段（大小根据类型可变），分别是