next up previous contents
Next: Parsing Complexity Up: Bottom-up Parsing Previous: The Algorithm   Contents


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:

Figure 9.1: The off-line EFD-closure algorithm
\begin{figure}\centering\begin{verbatim}Initialise Es to empty cats of grammar...
... := []; RAs := Rs;
Rs := NRs; NRs := [];
go to loop\end{verbatim} \end{figure}

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.


next up previous contents
Next: Parsing Complexity Up: Bottom-up Parsing Previous: The Algorithm   Contents
TRALE Reference Manual