TL;DR
This paper introduces a novel technique for improving the quality of natural language grammars and their associated test suites by adapting code instrumentation from software engineering. By marking grammar rules and tracking their usage during parsing, researchers can identify untested grammar rules, redundant test cases, and potential causes of overgeneration, leading to more robust and efficient linguistic tools.
What Problem Does This Paper Address?
The increasing adoption of computational linguistics (CL) in real-world applications like speech recognition and machine translation necessitates rigorous development methodologies for CL systems. While software engineering has well-established methods for assessing program quality, grammar engineering, particularly for large-coverage grammars, often lacks such systematic approaches. Specifically, developing comprehensive test suites that adequately cover complex grammars is challenging. Existing test suites may not exercise all grammar rules, leading to a false sense of confidence in the grammar's coverage. Furthermore, test suites can become bloated with redundant examples, wasting valuable testing time and obscuring the grammar's true performance. This paper addresses the gap in systematically evaluating and improving both grammars and their test suites by proposing a method to leverage linguistic knowledge embedded in grammars for test suite development.
Methods
The core contribution of this paper is the adaptation of code instrumentation from software engineering to grammar engineering. The fundamental idea is to augment grammar rules with special markers that record when a particular rule (or "disjunct" in the paper's terminology) is used during the parsing of a sentence.
- Instrumentation: Grammar rules are modified to include special annotations (e.g.,
DISJUNCT-nn ∈ DISJUNCTS). These annotations are designed to be processed by the grammar's unification mechanism. When a rule containing such an annotation is successfully used in parsing a sentence, the corresponding disjunct marker is added to a multiset associated with the parse solution. - Processing Tools: Automated tools are developed to instrument the grammar rules based on their structure. This instrumented grammar is then used to parse a given test suite.
- Usage Analysis: The output of parsing with the instrumented grammar is a set of parse solutions, each annotated with the disjuncts that were used to construct it. This information allows for the quantitative analysis of grammar rule coverage by the test suite.
- Test Suite Evaluation: The collected usage data is then used to evaluate the test suite based on two main criteria:
- Disjunct Coverage: Measures what proportion of grammar disjuncts are tested by the test suite.
- Test Suite Economy: Identifies redundant test cases based on criteria like similarity and equivalence, aiming to reduce the test suite size without sacrificing diagnostic power.
Datasets
The paper uses existing grammars and test suites for German. Specifically, it mentions:
- A large-coverage grammar for German developed over several years.
- The TSNLP testsuite (containing 1093 items).
- A local testsuite (containing 1787 items).
The paper does not introduce new datasets but rather uses these existing resources to demonstrate the effectiveness of the proposed instrumentation technique.
Key Insights and Ideas
- Bridging the Gap: The paper effectively demonstrates how established software engineering techniques can be adapted to the unique challenges of grammar engineering, offering a systematic way to improve linguistic software.
- Grammar as a Specification for Test Suites: The authors argue that the linguistic knowledge encoded in a grammar can be leveraged to build better test suites, reversing the typical flow where test suites are built independently.
- Hidden Redundancy in Test Suites: Even seemingly comprehensive test suites can contain significant redundancy, where multiple test cases rely on the same set of grammar disjuncts, leading to wasted effort and potentially masking grammar issues.
- Detecting Untested Grammar Rules: Instrumentation reveals that large-coverage grammars are often significantly under-tested, with a substantial portion of their rules not being exercised by existing test suites.
- Identifying Overgeneration: By analyzing which grammar disjuncts are used in parsing ungrammatical sentences, the technique can help pinpoint problematic rules that contribute to overgeneration.
Key Results
- Low Grammar Coverage: For the German grammar analyzed, less than half of its disjuncts were tested by the TSNLP testsuite (Tdis = 0.39) and the local testsuite (Tdis = 0.28).
- Significant Test Suite Redundancy:
- The TSNLP testsuite showed that 71% of its test cases were equivalent, and 19% were similar.
- The local testsuite showed 89% of its test cases were equivalent and 18% were similar.
- Reduction in Test Suite Size: By removing equivalent and similar test cases, the number of test cases could be reduced significantly, leading to a substantial decrease in processing time (e.g., a reduction to 14% of the original runtime for the local testsuite by removing similar cases).
- Identification of Problematic Disjuncts: The method successfully singled out six grammar disjuncts in the TSNLP testsuite that appeared in parseable ungrammatical sentences, suggesting they contribute to overgeneration.
Limitations and Future Work
- Manual Distinction: While instrumentation automatically identifies untested disjuncts, manually distinguishing between "appropriate but untested" disjuncts and "inappropriate" disjuncts still requires human linguistic judgment.
- Interaction Coverage Complexity: Measuring "interaction coverage" (how well combinations of disjuncts are tested) is methodologically challenging due to potential infinite legal combinations and complex dependencies between disjuncts. The paper acknowledges that full interaction coverage is infeasible, similar to path coverage in software engineering.
- No Counting in Unification: The unification formalism inherently limits the ability to count the number of times a disjunct is used; it can only detect its presence.
- Future Work: The authors suggest that instrumentation can be applied to other areas of grammar engineering, such as detecting sources of spurious ambiguities, selecting sample sentences for documentation, and assisting in the construction of additional test cases. They also emphasize the need for methodological work on practical criteria for measuring limited interaction coverage.
Summary updated