Towards reversible grammars

An interesting goal for this thesis might have been to devise an interpreter for reversible grammars. This interpreter should indeed compute the relation r for any given r-reversible grammar. However, it is not clear that such an interpreter actually can be built. Even though for each of the r-reversible grammars, programs can be built that compute r, it is not clear that a universal program can be built that accomplishes that task for any given grammar. In other words, even though the p-parsing problem (this notion will be defined in chapter 2) is solvable, by definition, for a fixed reversible grammar, it is not clear that the universal p-parsing problem for reversible grammars is solvable.

The goal of this thesis is more modest. Most attention in the next chapters will be devoted to the development of parsing and generation techniques which improve upon existing techniques with respect to the following two, related, dimensions:

• Applicability. The parsing and generation techniques are applicable for a larger class of constraint-based grammars than some other techniques. Furthermore, this extended domain of applicability is motivated from a linguistic perspective. Thus, the proposed techniques are applicable for constraint-based grammars such as these are actually written by (computational) linguists.
• Linguistic Deduction. The parsing and generation techniques follow certain linguistic principles. That is, the techniques are motivated from a linguistic perspective. It is hoped that such linguistically motivated techniques improve upon the efficiency as compared with other deduction methods.

Chapter 3 discusses methods for (grammatical) generation on the basis of constraint-based grammars. A method for generation, called `semantic-head-driven' generation, is introduced and compared with some `top-down' generation techniques, as for example proposed by [108] and [17], and with the chart-based technique of [83]. With respect to the dimensions mentioned above, semantic-head-driven generation is motivated because:

• Applicability. Certain linguistically motivated left-recursive analyses are problematic for the approaches of [108] en [17], but are handled without problems in a semantic-head-driven generator. Furthermore, certain analyses of idiomatic constructions are impossible in Shieber's chart-based generator. These analyses pose no problem for semantic-head-driven generation.
• Linguistic Deduction. The semantic-head-driven generation strategy defines a mixed bottom-up and top-down search procedure. The search is guided by the input semantic structure through the use of the notion `semantic-head of a construction'. Furthermore, the search is guided as much as possible by the information available in lexical entries. This implies that the algorithm is most useful for constraint-based grammars based on lexicalistic linguistic theories with a constraint-based semantics, such as UCG and HPSG.

Chapter 4 is devoted to parsing. A method for parsing, called `head-corner' parsing is introduced. Again, this method is compared with competing approaches to parsing along the dimensions of applicability and linguistic deduction:

• Head-corner parsing is applicable for constraint-based grammars in which operations on strings are restricted to be non-erasing and non-copying. One such operation is concatenation, but there are many others. For that reason head-corner parsing is applicable for a strict superset of concatenative constraint-based grammars, whereas most other algorithms are applicable only for concatenative grammars. As an example it is shown how head-corner parsing can be employed to parse lexicalized and constraint-based versions of Tree Adjoining Grammars.
• The order of processing in the head-corner parsing is bidirectionally in two senses. Firstly, the parsing proceeds head-driven, rather than from left-to-right. This implies that powerful top-down predictions are possible based on the usual percolation of syntactic features between the mother and the (syntactic) head of a construction. In many linguistic theories much syntactic information is encoded in the lexicon. As the head-corner parser has an important flow of bottom-up information, this lexical information is used to further reduce the size of the search space. The combination of these two properties furthermore ensures that, once the head of a construction is known, the parser also knows what other phrases it should expect, using the subcategorization specifications of that head.