next up previous
Next: Unification with Disjunctive Up: Reducing Complexity in A Previous: Reducing Complexity in A


Systemic grammar has been used in several text generation systems, such as PENMAN (Mann and Matthiessen 1985), PROTEUS (Davey, 1978), SLANG (Patten, 1986), GENESYS (Fawcett and Tucker 1990) and HORACE (Cross, 1991). Systemics has proved useful in generation for several reasons: the orientation of Systemics towards representing language as a system of choices, the strongly semantic nature of the grammar, and the extensive body of systemic work linking discourse patterns and grammatical realisation (e.g., Halliday, 1985; Halliday and Hasan, 1976; Martin, 1992).

Parsing with systemic grammar has not, however, been as successful. To date, there have been six parsing systems using systemic grammar: Winograd (1972), McCord (1977), Cummings and Regina (1985), Kasper (1988a, 1988b, 1989), O'Donoghue (1991a, 1991b) and Bateman et al. (1992). However, each of these systems has been limited in some way, either resorting to a simplified formalism (Winograd, Cummings, McCord), or augmenting the systemic analysis by initial segmentation of the text using another grammar formalism (Kasper: Phrase Structure Grammar; Bateman et al.: Head-driven Phrase Structure Grammar; O'Donoghue: his `Vertical Strip Grammar' (VSG)). There has not so far been a parser that parses using the full systemic formalism, without help from another formalism.

The reasons for this failure relate to those reasons which favour generation. Firstly, the orientation of systemic grammar towards choice means that the grammar is organised into a form full of disjunctions, which leads to complexity problems in parsing. Secondly, the strongly semantic content of systemic grammars (including roles such as Actor, Process and Circumstance in the grammar) leads to a structural richness which adds to the logical complexity of the task.

One result of the work in Systemic generation has been the availability of a large computational generation grammar using the systemic formalism -- the Nigel grammar (Matthiessen and Mann, 1985, Matthiessen and Bateman, 1992). As this resource is available, it is desirable to use it for parsing. However, complexity problems have so far made this impossible, except by pre-parsing with another formalism.

In the last few years, we have developed a parser for Systemic grammar, particularly for use with the Nigel grammar. The parser handles the full Systemic formalism, and does not depend on another formalism for segmentation. The parser uses a bottom-up, breadth-first algorithm. A chart is used to handle some of the non-determinism.

This paper focuses on some methods we have used in the parser to reduce the complexity problems associated with using the Nigel grammar. In particular, we focus on the means used to make disjunctive unification more efficient.

Section 2 discusses the problem of disjunctive expansion, and some means of making it more efficient at a general level. Before becoming more specific, the Systemic formalism is introduced (section 3). Section 4 explores one method of avoiding complexity -- reducing the size of the disjunctive description by working with sub-descriptions rather than the whole description. Section 5 presents three ways of making expansion, when necessary, more efficient. We conclude the paper with a brief summarisation of our work.

next up previous
Next: Unification with Disjunctive Up: Reducing Complexity in A Previous: Reducing Complexity in A

Mick O'Donnell
Fri Jan 26 19:21:43 GMT 1996