A Process-Activation Based Parsing Algorithm for the Development of Natural Language Grammars

Massimo MarinoCOLING 1988

TL;DR

This paper introduces SAIL, a novel system for developing Natural Language Grammars that treats grammar rules as active processes. It proposes a "Complex Grammar Units" (CGU) formalism and a process-activation parsing algorithm, enabling efficient, parallel syntactic and semantic analysis and flexible handling of linguistic dependencies.

What Problem Does This Paper Address?

Developing robust natural language processing (NLP) systems requires sophisticated grammars and parsers. Existing approaches often struggle with efficiently handling complex linguistic phenomena like long-distance dependencies and context-sensitivity, while also integrating semantic processing seamlessly with syntax. The authors aim to address these challenges by proposing a new framework that views grammar rules as dynamic processes, allowing for more flexible and efficient parsing.

Methods

The core of SAIL is its Complex Grammar Units (CGU) formalism and its process-activation based parsing algorithm.

  • Complex Grammar Units (CGU): This formalism defines grammar rules with distinct syntactic and semantic components, allowing for parallel processing. Each rule can include tests (applicability checks), actions (feature manipulation), and recovery actions (fallback mechanisms).
  • Process-Activation Parsing Algorithm: Instead of traditional static rule application, SAIL treats grammar rules as processes that can be activated or inactivated. The parser acts as a processor, managing a queue of "application specifications" (ASs) representing rules ready to be executed. This allows for:
  • Dynamic Rule Activation/Deactivation: Rules can be enabled or disabled during parsing, enabling context-sensitive behavior.
  • Message Passing: An asynchronous communication mechanism allows rules to exchange information, facilitating long-distance dependency resolution without explicit matching.
  • Not Operative (NOP) Rules: Special rule types allow for feature manipulation or contextual analysis without building new parse tree nodes, useful for debugging and specific linguistic analyses.
  • Layered Rule System: The system supports different layers of rules (e.g., for external interfaces, applications, debuggers) processed by the same parser.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Grammar Rules as Processes: Viewing grammar rules as active, stateful processes (activated/inactivated) rather than static entities is a key innovation. This allows for dynamic control over rule application, crucial for context-sensitive languages.
  • Parallel Syntactic and Semantic Processing: The CGU formalism inherently supports running syntactic and semantic analyses concurrently within the same rule, leading to potentially more efficient and integrated processing.
  • Message Passing for Dependencies: The introduction of a message-passing mechanism, distinct from pattern matching, offers a flexible and efficient way to handle long-distance dependencies and inter-rule communication. This avoids the computational overhead of extensive graph searches.
  • Contextual Rules via Activation and NOPs: The paper demonstrates how context-sensitive behavior can be achieved by combining rule activation/deactivation with specialized NOP rules, allowing for context determination and subsequent rule application.
  • Unified Parsing Framework: SAIL's design allows a single parser to handle various grammar formalisms and different layers of rules, making it a versatile tool for grammar development.

Key Results

The paper presents a conceptual framework and an example demonstrating its capabilities.

  • Example: A Lexical-Functional Grammar (LFG) fragment is successfully translated into SAIL's CGU formalism, showing that different grammar formalisms can be implemented within SAIL. The resulting feature structures and semantic values are presented as equivalent to the LFG output.
  • Efficiency: The process-activation approach and message passing are argued to offer relative efficiency and avoid computational overhead associated with traditional matching-based methods for certain tasks.
  • Flexibility: The system is designed to be highly flexible, supporting the development of grammars for various linguistic theories and applications.

Limitations and Future Work

  • Full Evaluation: The authors acknowledge that a complete evaluation of mechanisms like message passing and contextual rules has not yet been performed on real-world linguistic cases, only theoretically.
  • Experimental Component: While an experimental component for diagnosing ill-formed input has been implemented and confirmed to be supported by the parsing algorithm, its full capabilities and performance are not detailed.
  • Future Work: The paper mentions plans for searching standard procedures for building grammars in the CGU model starting from Categorial Grammars. The overall system is presented as a valuable tool for developing grammars, with potential for large-coverage applications.

Summary updated

BibTeX
@inproceedings{marino1988process,
  author = {Massimo Marino},
  title = {{A Process-Activation Based Parsing Algorithm for the Development of Natural Language Grammars}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1988},
}
Figure