On building a more efficient grammar by exploiting types

What it is about

Not read: this card is written from what is reliably known about the paper, and every idea is marked to check against the text. The paper comes from the special issue on efficient processing with HPSG and describes engineering work on the English Resource Grammar (ERG) in the LKB system. Its point is that the grammar's own design, chiefly the use of the type hierarchy to factor shared constraints, and choices that cut spurious ambiguity and large feature structures, has a large effect on parsing speed, of the same order as improvements in the parser. Changes are measured with systematic profiling over fixed test suites, so that each design decision is judged by its effect on time, memory and coverage.

Ideas

• I1. Profile grammar rules, not only the parser: for each rule or lexicon class in en, log how many candidate edges it creates and how many survive into the final tree on a fixed test suite, and report the most wasteful ones. Two runs must give identical profiles. (to check: which profiling measures the paper uses)
• I2. Factor shared constraints into types: where many lexical entries in en/src/dict.rs or the build-time tables repeat the same feature bundle, replace the copies with one class id, and check that parses are byte-identical before and after while the table shrinks. (to check)
• I3. Treat a coverage change and a speed change as one report: every grammar edit is run on the same suite and reported with coverage, ambiguity per sentence and time, so a speed gain that loses coverage is visible. (to check: the paper's evaluation format)

For Mova

The code is en/src/gram.rs, en/src/dict.rs, en/src/parse.rs and tools/bench. The chapter is 20. Syntax: the Universal Dependencies frame. Nothing from the ERG itself is used.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1017/s1351324900002370

@article{flickinger2000building,
  title = {{On building a more efficient grammar by exploiting types}},
  author = {Flickinger, Dan},
  journal = {Natural Language Engineering 6(1), 15–28},
  year = {2000},
  doi = {10.1017/s1351324900002370},
  url = {https://doi.org/10.1017/s1351324900002370}
}

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/parsers-2000-flickinger-building-more-efficient-grammar/