EFD-closure

[User's Manual]
[Code]
To convert an (extended) context-free grammar to one in which EFD-closure holds, we must partially evaluate those rules for which empty categories could be the first daughter over the available empty categories. If all daughters can be empty categories in some rule, then that rule may create new empty categories, over which rules must be partially evaluated again, and so on. The closure algorithm is presented in Figure 9.1 in pseudo-code and assumes the existence of six auxiliary lists:

• Es--a list of empty categories over which partial evaluation is to occur,
• Rs--a list of rules to be used in partial evaluation,
• NEs--new empty categories, created by partial evaluation (when all daughters have matched empty categories),
• NRs--new rules, created by partial evaluation (consisting of a rule to the leftmost daughter of which an empty category has applied, with only its non-leftmost daughters remaining),
• EAs--an accumulator of empty categories already partially evaluated once on Rs, and
• RAs--an accumulator of rules already used in partial evaluation once on Es.

Figure 9.1: The off-line EFD-closure algorithm

Each pass through the while-loop attempts to match the empty categories in Es against the leftmost daughter description of every rule in Rs. If new empty categories are created in the process (because some rule in Rs is unary and its daughter matches), they are also attempted--EAs holds the others until they are done. Every time a rule's leftmost daughter matches an empty category, this effectively creates a new rule consisting only of the non-leftmost daughters of the old rule. In a unification-based setting, these non-leftmost daughters could also have some of their variables instantiated to information from the matching empty category.

If the while-loop terminates (i.e., if there is a finite number of empty categories derivable), then the rules of Rs are stored in an accumulator, RAs until the new rules, NRs, have had a chance to match their leftmost daughters against all of the empty categories that Rs has. Partial evaluation with NRs may create new empty categories that Rs have never seen and therefore must be applied to. This is taken care of within the while-loop when RAs are added back to Rs for the second and subsequent passes through the loop.