Semantic Parsing as Graph Language Transformation - A Multidimensional Approach to Parsing Highly Inflectional Languages

Eero HyvonenACL 1984

TL;DR

This paper introduces a novel graph grammar formalism for parsing highly inflectional languages, like Finnish, which exhibit complex word order and morphology. By treating parsing as a multidimensional transformation between graph representations of different linguistic levels (morphological to semantic), it offers a more natural and powerful way to handle linguistic phenomena that are difficult for traditional string-based parsers.

What Problem Does This Paper Address?

Parsing natural languages, especially those with "free" word order and rich morphology like Finnish, presents significant challenges for traditional linear, string-based parsing methods. These languages often have complex agreement, discontinuities, and dependencies that are not easily captured by sequential rules. Representing and processing these multidimensional linguistic structures efficiently is a key problem. The authors argue that existing formalisms struggle to represent the configurational nature of these languages, necessitating a more flexible, multidimensional approach.

Methods

The core of the paper is the introduction of a graph grammar formalism based on relational graph grammars and attributed programmed graph grammars.

  • Relational Graphs (r-graphs): These are used to represent linguistic structures. An r-graph consists of nodes (representing linguistic units) and edges (representing relationships between them). Nodes can have labeled properties (e.g., grammatical case, number, semantic category).
  • R-productions: These are graph rewrite rules that define how r-graphs can be transformed. They consist of a left-hand side (LHS) and a right-hand side (RHS), both of which are r-graphs. An r-production is applicable if the LHS can be found within a larger r-graph.
  • Direct r-derivation: This is the algorithm for applying an r-production to transform an r-graph. It involves removing the LHS and replacing it with the RHS, while carefully managing node properties.
  • Controlled R-graph Grammars (CRGs): To manage the parsing process, the authors introduce CRGs. These consist of a control graph (c-graph) and an r-graph grammar (RGG). The c-graph acts as an interpreter, guiding the application of r-productions (which represent direct r-derivations) to transform the input morphological representation into a semantic representation. The control graph is constructed dynamically based on the input sentence.
  • Parsing Scheme: The overall parsing scheme is presented as a multidimensional transformation between graph languages. The input is a set of morphological representations (as r-graphs), and the output is a set of semantic representations (also as r-graphs). This transformation is guided by an agenda of prioritized c-graphs.

Datasets

Not discussed in the paper. The paper describes an experimental Finnish parsing system with a small lexicon (150 entries) and a limited number of productions and c-graphs, but does not detail specific datasets used for training or evaluation.

Key Insights and Ideas

  • Multidimensionality is Key: The paper strongly advocates for multidimensional representations (graphs) over linear ones (strings) for parsing complex languages. This allows for a more natural capture of configurational and morphological phenomena.
  • Parsing as Transformation: Viewing parsing not as building a tree from a string, but as a "meaning preserving" transformation between different levels of linguistic representation (morphological to semantic) using graph grammars.
  • Dynamic Control: The use of controlled r-graph grammars, where the control flow is dynamically constructed based on the input sentence, allows for flexible and context-dependent parsing.
  • Linguistic Description: The graph grammar formalism can serve as both a computational parsing mechanism and a descriptive linguistic tool, capturing syntactico-semantic features of word categories.

Key Results

The paper presents a formalism and a parsing scheme, along with an experimental implementation for Finnish.

  • Formalism: A well-defined graph grammar formalism (r-graphs, r-productions, CRGs) is developed.
  • Algorithm: An algorithm for direct r-derivation is provided, with an analysis of its time complexity (expected O(n), worst-case O(n^2)).
  • Experimental System: A small experimental Finnish parser was implemented, demonstrating the feasibility of the approach. However, no quantitative performance metrics (e.g., accuracy, speed) are reported for this system.

Limitations and Future Work

  • Experimental Scale: The authors acknowledge that their experimental parser for Finnish is "linguistically quite naive" and needs to be modelled with a larger subset of Finnish to be properly evaluated.
  • Generalization: Future work includes generalizing the formalism to hierarchic graphs to handle large graph structures more easily and allow for different interpretations of identical structures in different contexts.
  • Control Structure: Developing a more elaborate coroutine-based control structure for interpreting c-graphs is also planned.
  • Evaluation: A more thorough evaluation of the approach is needed, likely with larger datasets and more comprehensive linguistic coverage.

Summary updated

BibTeX
@inproceedings{hyvonen1984semantic,
  author = {Eero Hyvonen},
  title = {{Semantic Parsing as Graph Language Transformation - A Multidimensional Approach to Parsing Highly Inflectional Languages}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1984},
}
Figure