tailieunhanh - Báo cáo khoa học: "SEMANIIC PARSING AS GRAPH LANGUAGE TRANSFORMATION A MULIIDIMENSIONAL APPROACH TO PARSING HIGHLY INFLECTIONAL LANGUAGES"

intermediate depencies between morphology, syntax and semantics. A strong, multidimensional formalism that can cope with d i f f e r e n t l e v e l s of language seems necessary. In t h i s chapter a graph grammar formalism based on the notions of r e l a t i o n a l graph grammars ( R a j l i c h 1975) and a t t r i b u t e d programmed graph grammars (Bunke 1982) is developed f o r parsing languages with configurational structure . | SEMANTIC PARSING AS GRAPH LANGUAGE TRANSFORMATION -A MULTIDIMENSIONAL APPROACH TO PARSING HIGHLY INFLECTIONAL LANGUAGES Eero Hyvonen Helsinki University of Technoloạy Digital Systems Laboratory otakaari SA 02150 Espoo 15 FINLAND ABSTRACT The structure of many languages with free word order and rich morphology like Finnish is rather configurational than linear. Although non-linear structures can be represented by linear formalisms it is often more natural to study multidimensional arrangement of symbols. Graph grammars are a multidimensional generalization of linear string grammars. In graph grammars string rewrite rules are generalized into graph rewrite rules. This paper presents a graph grammar formalism and parsing scheme for parsing languages with inherent configurational flavor. A small experimental Finnish parsing system has been implemented Hyvõnen 1983 . 1 A SIMPLE GRAPH GRAMMAR FORMALISM . WITH A CONTROL FACILITY In applying string grammars to parsing natural Finnish several problems arise in representing complex word structures argeements free word ordering discontinuity and intermediate depencies between morphology syntax and semantics. A strong multidimensional formalism that can cope with different levels of language seems necessary. In this chapter a graph grammar formalism based on the notions of relational graph grammars Rajlich 1975 and attributed programmed graph grammars Bunke 1982 is developed for parsing languages with configurational structure. Definition relational graph r-graph Let ARCS NODES and PROPS be finite sets of symbols. A relational graph r-graph RG is pair RG EDGES NP consisting of a set of edges EDGES- ARCSxNODESxNODES and a function IIP that associates each node in EDGES to a set of labeled property values IIP NODESxPROPS - PVALUES PVALUES is the set of possible node property values sets of symbols or They are represented as 1i Sts. Example Figure depicts the morphological r-graph representation of Finnish word ihmisten .