把特征结构与合一运算结合到Earley算法中的目的有两个：第一，使用特征结构，从而为剖析的组成成分提供更丰富的表达方式；第二，阻止成分进入破坏合一约束的非良构成分的线图中。只要最小限度地改变原来的Earley算法，就可以达到这样的目的。

第一个改变是改变在原来的代码中使用的各种表达方法。Earley算法在运算时要使用一套无装饰的上下文无关语法规则，来填充一种称为线图的数据结构，这种线图由状态的集合组成。在剖析的终点，构成线图的状态可以表示对于输入的一切可能的剖析结果。因此，我们要进行的改变首先从改变上下文无关语法规则和线图中的状态开始。

在改变规则时，除了它们当前的成分之外，还包括从它们的合一约束推导出的特征结构。更具体地说，我们将使用由规则列出的约束来建立特征结构，把特征结构表示为DAG，以便在剖析过程中与规则一起使用它们。

我们来研究如下的带有合一约束的上下文无关规则：

S → NP VP

=

把这些约束转变为特征结构，得到如下的结构：

在这个推导中，我们首先对上下文无关规则中的每个部分创建顶层特征，在这个例子中，这些顶层特征是S，NP和VP；使用这样的方法，把各种不同的约束结合到一个单独的结构中。然后，顺着约束中的路径等式，进一步再把各种成分加到这个结构中。注意，这只是一种纯粹的表记法的变换，DAG和约束等式中包含的信息都是完全一样的。但是，把各种约束捆绑到一个单独的特征结构中，这样的形式就可以直接放到合一算法中。

第二个改变是改变用于表示Earley算法中局部剖析的状态。原来的状态包括所用的上下文无关规则、表示规则已经完成部分的点的位置、状态的开始和终止位置以及表示状态中已完成子部分的其他状态的一个表。现在再加上一个附加的区域，这个区域包含表示与状态相应的特征结构的DAG。注意，当一个规则首次被PREDICTOR用来建立一个状态时，与状态相联系的DAG将由规则中检索出来的DAG组成。例如，当PREDICTOR使用上面的S规则而进入到线图中的一个状态时，上面给出DAG将是初始的DAG。我们把状态表示如下，其中DAG表示上面给出的特征结构：

S → •NP VP, [0,0], [], Dag

给出了这些新增加的表示之后，就可以来改变算法本身了。在行动方面的最重要的改变是：当通过扩充现有状态建立一个新状态时，在COMPLETER程序中发生了变化。我们知道，当一个完成的成分加到线图中时，就要调用COMPLETER。COMPLETER的任务是发现并扩充线图中现有状态，这个状态正在查找与新完成的成分相容的成分。因此，COMPLETER是一种结合两个状态中的信息建立新状态的功能，它要使用合一的操作。

更具体地说，COMPLETER通过发现现有状态的方式，把一个新的状态加到线图中，并把现有状态中的“.”由新的完成状态向前推进。当直接在“.”后面的成分的范畴与新完成的成分的范畴相匹配时，就可以把“.”向前推进。为了便于使用特征结构，我们可以改变这样的做法，而把与新的完成状态相联系的特征结构与被推进的特征结构中的适当部分进行合一。如果这样的合一取得成功，那么新状态的DAG就接受合一后的结构，并进入线图中。如果合一失败，则没有新的状态进入线图中。COMPLETER的这种改变情况如图2所示。

图2 修改Earley算法使之包括合一运算