Graph Grammar Approach to Natural Language Parsing and Understanding

AffiTRAC';'

String grammars have been found in many ways inadequate for parsing inflectional languages with "free" word order . 'I'o overcome these problems we have replaced linear string grammars and tree transformations by their multidimensional ~neralization , graph grammars. In our approach parsing i.s seen as a ~ransformation between two graph languages , namely the sets of QOrphological and semantic representations of natural language sentences . An experimental Finnish question- answering system SUVI based on graph grammars has been implemented. In SUVI the role of individual words is active . Each word is associated to a syntactico-seuanoic constituent type that is represented ~ a transition network - like graph whose transitions correspond to transformations in the derivation graph. Parsing is performed by interpreting the constituent type graphs corresponding to the words of the current sentence.

WHY GRAPH GRAMMARS ?

In parsing highly inflectional languages with loose syntax by string grammars several problems arise with the formalism:

1. Morphological structures cannot be adequately represented by trees and string grammars .
2. Many relations between words and constituents are difficult to express qy trees and string rewrite rules. For example, case, person, and number agreements are widely used.
3. Relatively free word and constituent ordering found in inflectional languages leads to large and complex grammars with string grammars that are based on linear ordering of ~bols .
4. Discontinuous constituents occur often in inflectional languages .
5. The levels of morphology, syntax and semantics are quite intermingled in inflectional languages . For example, in Finnish the correlation between morphological and semantic cases is essential.

To solve these problems a stronger, multidimensional formalism that can cope with different levels of ~ seems necessary. In this paper we suggest graph grammars / 1, 2, 3/

GRAPH GRAMMAR APPROACH TO NATURAL LANGUAGE PARSING AND UNDERSTANDING

Eero Hyvonen

Digital Syste~s Laboratory Helsinki University of Technology 02150 Espoo 15, Finland

for the purpose . Besides their high generative power graph grammars offer an illustrative formal tool for modelling language understanding processes.

2 A. GRAPH GIW1MAR FORMALIS~1 FOR NATURAL LANGUAGE PROCESSING

Algebraic graph grammars (AGG) /4/ can be considered a multidimensional generalization of l inear string grammars. In AGG's the catenation of strings is replaced qy the more versatile notion of "gluing" graphs together . String productions are generalized into graph productions which explicitly express structural transformations in the derivation graph. Applying a graph production means that a subgraph corresponding to the left hand side of the production is replaced by its right hand side in the derivation graph. However, additional "application conditions" must hold to quarantee that arcs with no source or goal node will not arise and that the result of the derivation is well- defined . Analogously to the string case a graph language is defined as the set of all terminally colored graphs derivable froQ an initial start graph by some sequence of productions of the grammar .

The formalism of this paper /1/ contrasts the basic notions of AGG's in three major ways :

• Grammatical derivation sequences are given explicitly by transition network -like "control graphs" whose transitions correspond to transformations in the derivation graph (cf . the
• notion of "programmed graph grammars" /6/) .
• -Application conditions in our grammars are trivially true due to some restrictions and modifications to AGG's. The resulting formalism is argued to be intuitive, semantically plausible, and computationally efficient.
• Nodes and arcs in the graphs are associated to a set of properties that can be modified as a side effect of dir~ct derivations (cf. the notion of "attributed graph grammars" /7 /) .

In our experimental question-answering system SUVI nodes have three properties : EXT (extension) is the set of all objects in the real world knowledge base the node currently refers to; QUANT is the quantifier of the extension; CAT is the syntactico-semantic type or category of the node. Arcs have no properties. Essentially, the derivation graph is a set of relations between quantified extensional sets of grammatical and real world objects belonging to different syntactico-semantic categories.

3 A GRAPH GRANHAR BASED SENAN~IC PARSER

Figure depicts the function and structure of our SWI-system.

,----,

I

First words and idioms are delinearized by the morphological analyzer into small frame-like word graphs representing morphological word forms. Initial node properties (EXT, QUANT, and CAT) are associated to the nodes. For example, the singular partitive noun "ohjelmaa" (a program) would refer existentially to a program in the set of all programs while the nominative plural form "ohjelmat" (the programs) refers to all programs.

The upper graph of figure 2 illustrates part of a derivation graph that contains the morphological structure of three successive Finnish words "kaikki suuret ohjelmasi" (all big programs-of-yours). The last word "ohjelmasi" is morphologically ambiguous but can be represented by a single word graph by setting non-unary extensions to nodes expressing the case and number. These extensions will later be automatically focused in clause context by direct derivations demanding congruences between words and constituents. Entries and word forms having different meaning or syntactico-semantic properties are considered lexically ambiguous. They are represented qy a set of alternative word graphs.

The goal of the parser is to generate from each morphological representation of the sentence corresponding hierarchical semantic case structure. The parser has three major dynamic data structures (fig. 1): the derivation graph, the stack of word graphs (WG-STACK), and the stack of transition network -like control graphs (c-graphs) with priorities (CG-STACK). After morphological analysis CG-STACK consists of the control graphs corresponding to t he . constituent types of the individual words in the sentence and a set of sentence-independent transformational graphs. Arcs in c-graphs usually correspond to direct derivations in the derivation graph but can perform other operations, too, like pushing new c-graphs into the CG-STACK to be interpreted later. By this way, for example, nouns analyse their post-attributes and verbs their deep case constituents.

(Node properties as above)

Figure 2. Part of a derivation qraph b~fore and after direct derivation 1\0J-ATTR.

Parsing begins by interpreting the first c-graph in the CG-STACK. The constituent type c-graphs are defined in such a way that all word graphs from the WG-STACK will eventually be glued into the derivation graph and corresponding a-graphs interpreted. ~ the transformational c-graphs passive clauses and yes/no-questions are transformed into simple active declaratives. In the end CG-STACK and WG-STACK are empty and the derivation graph constitutes a labelled tree of semantic case propositions.

G-graphs are illustrative descriptions of syntactico-semantic constituent types. For example, figure 3 tells that in an NP-HUJ'.1AN constituent genetive, pronoun, and adjective attributes with a quantifier may precede the main word in the combinations expressed by the graph. Attributes can be already parsed lower level constituents as well as single words, because these both are represented in a compatible way.

In nodes with a dot inside backtracking is allowed if some of the out-going arcs marked by a question mark have first been chosen . ~ this way locally ambiguous qrntactic structures are analysed .

Production ADJ-ATTR in figure 4 illustrates the structure and meaning of the adjective attribute construction in Finnish (cf. linear production AdjP+NP- >NP) . Uncolored nodes in the left hand side match any node with no side effect . ~he interpretation of the production is that if there is an adjective followed by a noun in the same case and number in the sentence the noun and the adjective (their extensions) are assumed to be in semantic Kind-relation with each other in the knowledge base . Figure 2 illustrates the application of ADJ-ATTR production in a derivation graph . The case and number of the noun "PRCGR." are well-defined after the derivation due to the congruence demand of the adjective attribute construction .

At the highest level of constituent generation in a clause i .e . when interpreting the o-graph with the lowest priority in the CG-STACK -­ senantic deep case relations are generated between the predicate verb and its deep case constituents. Figure 5 illustrates a production for generating the AG-case. Node <NOUN-Hlll"!. > matches nodes with CAT=NOUN-HUMAN and NOM,PART matches nodes expressing nominative or partitive case. Arc <,> matches both <- and >-arcs.

Figure 6 depicts the resulting semantic representation for the question

"Kuka laboratorian luennoitsijoista on luennoinut jonkun seminaarimaisen kurssin tietojenkasittelyteoriasta qrksylla 1981 ?" (Which lecturer of the laboratory has lectured some seminar-type course on computer science in the autumn 1981 ? ) ·

Dotted lines representations of the clause . by corresponding encircle the semantic case of the three major constituents The case structures are generated constituent type o-graphs.

After parsing RESPOND-GENERATOR computes the extensions of the constituents in the clause context . ~his is obtained by recursively demanding that the semantic cases between the constituent nodes in the derivation graph hold for their extensions in the knowledge base . The final extension of the MAIN-CLAUSE-node corresponding to tl1e predicate of the sentence is a set of propositional deep case structures in the knowledge base that satisfy the semantic conditions expressed by the derivation graph. ~ comparing these propositions with respect to the quantified extensions of the deep case constituent nodes it is possible to generate answers to different kind of questions and requests .

As a whole, the idea of our graph grammar parser is to construct a sentence-dependent graph grammar and apply it to the morphological representation(s) of the current sentence . The control mechanism to find the correct derivation sequence(s) to corresponding semantic case structure(s) is essentially defined by the constituent types of individual words. Parsing is seen as a meaning preserving transformation between two graph languages -- i . e. the sets of morphological and semantic representations of sentences. These graph languages correspond to two representational levels of the natural language to be parsed .

5 THE ADVANTAGES OF THE GRAPH GRAMMAR PARSER

In this piper gralJI! grammars have been introduced into the field of natural language processing. As a conclusion, let us list what we consider important points from theoretical and practical point of view in our graph grammar approach:

• 1 ) Expressive power. Using graph grammars any kind of labelled relations can be represented and processed, not only sequential and hierarchic ones. The same formalism can be used uniformly at different levels of language.
• Designer f riendliness . Graphical drawings support design process in the same way as blue prints in oany fields of engineering and offer the basis for documentation. The conversion from pictures to data structures is straight forward.
• Uniformity. Graphs can be used to express different kinds of procedural and declarative knowledge like o-graphs and semantic networks .
• Extendability and modifiability. In SUVI constituent models can be designed and modified modularily by o-graph descriptions . We have asked the question 'What is in the word ?' a bit in the same spi rit as in /8 , 9/ . A major point in which our parser contrasts the "word expert" parsers is that its function is specified by explicit syntactic(o- semantic) models of constituents .
• Computational efficiency. Specialized CG-STACK's are created dynamically for individual sentences . Only relevant language knowledge is used during parsing. We argue that productions and grammars of our type can be designed to be efficient /5/ .

Due to these issues the graph grammar approach seems promising in handling the problems 1-5 of parsing inflectional language as listed in sect ion 1 :

1. Complex morphological structures and many ambiguities can be expressed intuitively by word graphs .
2. Figures 5 and 6 illustrate rewrite rules containing multiple congruences between two words or constituents.
3. The production of figure 6 shows a way of representing free constituent order; the agent noun phrase can be situated either before or after the predicate .
4. Problems of representing discontinuous constituents can be approached with productions in which congruences, category types etc. properties are demanded in stead of sequential relations. We r~ve used this kind of productions in analysing allied verb forms.
5. Morphological, syntactic, and semantic categories and relations are used in JErallel in a single production (fig. 5 and 6) . However, SUVI identifies the difference between structurally and semantically (domain- dependently) incorrect sentences since domain-dependent criteria have not been used to quide JErsing.

Graphical representations have traditionally been used to illustrate different kinds of linguistic and computational phenomena. Our intuition is that they should be used not only as illustrations but as a discipline and a tool in designing and implementing models on these phenomena.

6 ACKNOWLEDGEMENTS

Thanks to the personnel of Digital Systems Laboratory and Jouko Seppanen for fruitful discussions and proof reading earlier versions of this paper . Finnish Academy and the Finnish Cultural Foundation have supported our work financially.

7 REFERENCES

• / 1/ Hyvonen E.: A Graph Grammar Formalism and Procedural Production Description System for Natural Language Processing. Helsinki University of Technology, Digital Systems Laboratory, report B25.

/2/ Claus V., Ehrig H., and Rozenberg G. (Eds) : Graph Grammars and Their Aplication to Computer Science and Biology. !~cture Notes in Computer Science 73, Springer-Verlag 1979.

/3/ Nagl, M.: Graph- grammatiken , Friedr. Verlag et Sohn, Braunschweig, 1979.

/4/ Ehrig H.: Introduction to the Al&ebraic Theory of Graph Grammars. Article in /2/, pp. 1-69.

/5/ Hyvonen E.: Graph Grammar Approach to Parsing and Understanding Inflectional Languages. A forthcoming dissertation , Helsinki University of Technology , Digital Systems Laboratory.

/6/ Bunke H.: Programmed Graph Grammars . Article in /2/, pp. 155-166. ·

/7/ Bunke li . : Attributed Programmed Graph Grammars and Their Application to Schematic Diagram Interpretation. IEEE '..'ransactions of Pattern Analysis and Machine Intelligence. Vol PArU-4 , No 6 , 1982 .

/8/ Rieger C., SmallS .: Parsin~ and Comprehending with Word Experts \A Theory and Its Realization) . Report TR-1 039, University of Maryland, Comp . Sci . Dept ., 1981.

/9/ Riesbeck C.: Computational Understanding: Analysis of Sentences and Context . Ph .D Thesis, Comp. Sci. Dept ., Stanford University, 1974.