In this step, we construct a global interaction finite-state automaton (global finite-state automaton) encoding all possible sequences of lexical rule application, taking into account only the information specified in the lexical rules themselves. This step of the algorithm has three components. We first calculate and assert the follows relation. The follows relation associates each lexical rule with the list of lexical rules that can apply to the output of the first. We calculate the follows relation by test-unifying the output specifications of one rule with the input specifications of all lexical rules, and associating the first lexical rule id with a list of ids where unification succeeded.8.3
Based on the follows relation, we build a finite-state automaton with lexical rule identifiers labelling the arcs. Arcs corresponding to each lexical rule originate at the start state, and for any state, the lexical rule labelling the arc terminating at that state determines the arcs that will originate there, according to the follows relation. In the case that a lexical rule may apply to its own output, we include an arc whose start state and end state are the same, and flag the existence of a cycle in the representation of the arc. Every state is ultimately intended to be a final state, though this is not encoded in the representation at this stage of the compilation process.
The final component of this step involves the propogation of specifications. That is, we prune unusable arcs based on the actual unification of output and input specifications along each of the paths through the automaton.
We use arc(Arc_Label,Rule_Label,Prefix_List,Follow_List,Cycle_Flag) to build the automaton because there exists a convenient relationship between this representation and the follows relation definitions. Specifically, given the Rule_Label argument for a particular arc, we can find the follows/2 clause which has that Rule_Label as its first argument. We can then directly incorporate the follows list from the follows/2 clause as the fourth argument in arc/5, and then recursively work through that list to assert arc/5 clauses for each member. However, for the stage of processing that involves actual unification of feature structures along all paths, we associate feature structures with particular states, and store this information in a table. At this point, it becomes more convenient to work with a state-based representation of the automaton. Therefore, we translate from the arc representation given above to arc(StateIn_Label,StateOut_Label,Rule_Label,Cycle_Flag). The automaton that serves as input to step three is defined via arc/4.