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

• DTYP（节点类型）：每个节点都有唯一的类型，又分为四种——TCOM（简单命令）、TPAR（复合命令）、TFIL（过滤器/管道线）、TLST（命令序列）。

• DLEF（左子树节点）：相当于链表指针，根据DTYP定义有所不同。如过滤器类型左子树节点为前一个命令的输出重定向文件，右子树节点为后一个命令的输入重定向文件。

• DRIG（右子树节点）：同上。

• D{敏感词}（节点属性）：这是个标志位(flag)，决定该节点包含命令的属性以及以什么样的状态执行。

• DSPR（子命令）：两重含义，对于简单命令，该字段为空；对于复合命令，该字段指向子语法树节点。

• DCOM（命令字符）：引用命令字符序列。

　　语法树节点生成顺序根据token列表中每个元素的优先级(priority)而定，首先遍历整个列表，找到优先级最高的token作为根节点，再分别生成左右子树，这是一种最简单的自顶向下(top-down)解决方案。各个token优先级视DTYP字段而定

　　语法树的构建过程中还使用了一种基于“有限状态机(finite-state machine)”的动态规划算法，其实现是将整个逻辑流程划分为四个状态：syntax、syn1、syn2、syn3，对应于上面token优先级，程序在每个状态下都生成一个相应类型的节点，同时还生成四种策略，以决议下一步将转移到何种状态（根据优先级搜索对应的token）。这个四种策略分别是

• 生成左子树：左边token列表递进到下层状态。

• 生成右子树：右边token列表并回溯到上层状态或递归调用。

• 找不到对应token：保持原有token列表递进到下层状态。

• 生成节点：直接返回节点。

　　当我们遍历完整个token列表后，程序总是能返回最初的调用点，即根节点上，从而生成一棵完整的语法树。这种算法的好处是程序员不必关注具体实现的每个细枝末节，只要关注相应的状态并制定对应的转移策略即可。还值得一提的是每个转移策略都是发生在赋值语句或返回语句上，并使用函数实参保存临时变量，这样就避免了调用次数过多导致堆栈溢出。

　　依旧举两个个例子，比如命令”A & ; B | C”对应的语法树

命令”(A ; B) | C”对应的语法树：