Parsing is defined as a specific call to
the main procedure PROCESS, by specifying a concrete value for
the global variable . We will use the path PHON DL
. The parser is then just a call to PROCESS.
When called with a goal Goal it simply returns the result of the procedure PROCESS. For example (using the grammar in A, for parsing the string ``weil peter heute lügen erzählt'' the input for the parser is
and the created start item is
Figure 4.8 shows a trace of the parsing process. The trace does not give a full example run, because we only considered those steps in the proof which contribute to the resulting derivation shown in figure 4.9. P stands for prediction, S for scanning and C for completion. The arrows basically represent the flow of information. The notation (i), where i is an integer denotes the computation step, e.g., (1) is the first step and (13) the last one. For simplicity, we have only expressed the phrasal backbone and the input string (also simplified). Although the subcategorization rule has been predicted two times, this prediction has been done on different string positions. However, this rule will only be predicted one time at the same string position. Thus left-recursion is no problem. Note that we only show the successful steps.
Figure 4.8: A trace of parsing the string ``weil peter heute lügen
erzählt.'' For explanations of the symbols used see text.
Figure 4.9: The derivation tree of the example sentence. The labels of the
node refer to the names of the rules of the grammar in Appendix A.
The generation instance GENERATE differs only with respect to the specified value for , and that the goal specifies the semantic form for which the program should generate corresponding strings. Thus, the generation instance is as follows:
As an example consider generation from the start item
Figure 4.10 shows a trace of the generation instance. Instead of directly using the feature structure representation of the semantic input we simply use the tree-like list-notation ``weil(heute(erzählen(peter,lügen)))''. We furthermore made use of the same abbreviations as in the parsing trace of figure 4.8. Note that in step (6) there is already a scanning step possible. The lexical entry can complete the subcategorization rule and the new item (a reduced copy) is used for scanning the next possible entry (step (7)). After completion of the rule, this reduced passive item can be used to complete the predicted subcategorization rule. Thus, although the subcategorization rule has only be predicted one time, it has been used by the completor two times. Thus non-termination because of prediction of infinite long subcategorization lists is avoided.
The derivation of the anlaysis of this semantic input is shown is figure 4.11 tree a. The other two derivations are also possible for this input, but we have not specified the traces here. However, when these two other alternatives are generated precomputed substrings will be reused.
Figure 4.10: A trace of generating from
``weil(heute(erzaehlen(peter,luegen)))''.
For explanations of the symbols used see text.
Figure 4.11: All possible derivation trees admitted by the grammar for
the generation example.