📄 A New Predictive Analyzer of English

Summary

This paper asks how a parser could read English the way people seem to: left to right, almost never backtracking, and committing early to one structure. Musha extends Kuno's predictive analyzer. In that design, rules in Greibach normal form treat each incoming word as the terminal of a rule and push the nonterminals that follow it as expectations. Musha argues that some of Kuno's rules predict too much too early, so he adds several kinds of prediction: essential, optional, bunch, coordination-driven, insertive, and gap-filling. These are run on three stacks: a prediction stack, an "and stack" and an NP stack. The rule format is also extended with a shifting flag and prefixes that mark optional and gap predictions. Lookahead is done with bounded backtracking, and ambiguity is ordered by preferences. The grammar was tuned on two texts, a software manual and an economics abstract. On more than 150 sentences, over 70% were analyzed as intended, and a lookahead of two words appeared to be the critical length. The work matters as an early, explicit model of near-deterministic, psychologically motivated incremental parsing.

Key points

• Builds on Kuno's stack-based predictive analyzer. Rules are in an extended Greibach normal form whose fields are current word, current prediction, shifting flag and new predictions.
• Three stacks are used:
  • the prediction stack;
  • the and stack, which lists the constituents open at a coordinate conjunction, e.g. (NP VP S);
  • the NP stack, which holds a relative-clause antecedent until its gap is found.
• Prediction kinds:
  • essential predictions;
  • optional predictions, marked with *, e.g. *NP-N;
  • bunch predictions, e.g. after be: NP / ADJ / VP-ing;
  • insertive structures, which suspend the current prediction (adverbs, PPs);
  • NP-gap predictions, marked with +.
• Lookahead counts words, unlike the buffer of constituents in Marcus's parser. A decision made at word n−k becomes final once the parser reaches word n.
• Evaluation covered more than 150 sentences from a software manual and a world-economics abstract. Over 70% were recognized as desired, and two words of lookahead looked critical.

Interesting ideas

• I1. A postmodifier such as a relative clause is not predicted when the noun phrase starts; it is predicted only when its trigger word appears, and the NP is kept in a state where it "may end here". This keeps expectations minimal and avoids speculative structure.
• I2. A bunch prediction pushes an unresolved set of possible categories, and the next word chooses among them. This postpones a choice cheaply without branching the whole analysis.
• I3. At a conjunction, an and stack records every constituent still under construction, so the second conjunct can resume at the NP, VP or clause level.
• I4. Parentheticals and inserted adverbials suspend the current expectation instead of replacing it, and the suspended prediction resumes afterwards.
• I5. Lookahead is measured as a commitment window in words, and the needed size is found empirically (about two words here), while rules are tiered into usual ones tried first and unusual ones tried later.

For Mova

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

• I1 (tree): The perceptron parser could treat an open NP as complete but extendable, attaching a relative clause or PP only when a trigger token arrives, which gives clean and explainable attachment decisions.
• I2 (tree): After copulas or other ambiguous heads, the parser could keep a small typed set of candidate dependents (nominal, adjectival, participial) and resolve it on the following token, logging which option the evidence selected.
• I3 (tree): Coordination attachment in UD (conj/cc) could be decided by choosing among the currently open spans rather than guessing a head, and the list of candidates would serve as a built-in explanation.
• I4 (tree): Inserted adverbs, PPs or clauses could be parsed as temporary pushes that do not disturb the pending object or complement, which would reduce misattachments in heavy-shift sentences.
• I5 (learn): Evaluation could sweep the commitment window and rule tiers as explicit parameters to find how much delay each parser actually needs, and use the results to find constructions that need longer windows.