📄 The Acquisition and Application of Context Sensitive Grammar for English

Summary

The authors argue that hand-built augmented context-free grammars are complex and fragile. They propose a context-sensitive phrase structure grammar (CSG) that is learned from example parses of English news stories. Each parse is treated as a chain of shift/reduce states. A rule pairs a 10-symbol window (five stack symbols and five input symbols, all part-of-speech or phrase labels) with the next operation: shift, or reduce the top two stack items to a named phrase.

Rules live in a hash table keyed on the top two stack elements. A deterministic bottom-up parser picks the stored rule whose remaining context best matches the current state, using position weights inspired by NETtalk.

Grammar acquisition is interactive. A linguist steps through parses while the grammar collected so far proposes each next move. From 92 sentences they gathered about 4000 rules. The parser reproduced the linguist's meaning-based structures almost exactly and predicted about 80% of new parse states. The work matters because it replaces slow neural-network training with a cheap, scalable lookup that still captures contextual preferences.

Key points

• About 4000 CSG rules were collected from 92 newspaper sentences. An earlier neural-network version needed several days to train on only about 2000 rules.
• Rule format: 5 stack symbols + 5 input symbols map to S or (R label). If the window were cut to the two stack items and one input item, the system would reduce to a CFG.
• After 2–3 thousand rules, about 80% of later parse states were predicted correctly. Keeping only the rules the grammar did not already predict shrank 3430 rules to 895, a ratio of roughly 3.8:1.
• The grammar holds 551 binary context-free pairs, estimated as about 95% of the roughly 580 that actually occur, out of 4096 possible. These pairs have 421 distinct left sides, averaging about 1.3 operations per stack pair.
• A log-log growth curve projects that about 25,000 example rules would cover nearly all context-free pairs found in news text. Most parse failures were dead ends caused by one wrong choice midway, so the authors suggest a beam-search parser.

Interesting ideas

• I1. Each parser action is chosen by best-match lookup over stored contexts. Exact match is required on the two focus stack slots, and other positions count less the farther they are from that focus, which makes every decision traceable to a concrete precedent.
• I2. Annotation runs as prediction-plus-correction: the grammar learned so far proposes the next step, and the human only confirms or fixes it, so the annotator's effort drops as the model improves.
• I3. The grammar is compressed by keeping only the examples the current model would have gotten wrong. This is a simple way to find the informative cases and discard redundant ones.
• I4. Coverage is estimated by plotting how fast new rule types appear as examples accumulate, then extrapolating on a log-log scale to judge how much more data is needed.
• I5. Errors are diagnosed as dead ends caused by a single early wrong choice, which points directly to a beam over a greedy path as the remedy.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (tree): The perceptron parser could record, for each transition, the nearest stored training configuration, giving a human-readable justification for each arc.
• I2 (learn): LLM teacher tiers or human reviewers could correct parser proposals step by step rather than write full trees, which speeds up silver data creation.
• I3 (learn): Self-induced repair rules could be kept only when they fix an error the base parser makes, keeping the rule set small and auditable.
• I4 (learn): Tracking the arrival rate of new label/head-pair types in treebank growth could tell when more annotation stops paying off.
• I5 (tree): Logging the states where no transition scores well could show where gparse or the perceptron parser would gain most from a small beam.