An Efficient Algorithm to Induce Minimum Average Lookahead Grammarsfor Incremental LR Parsing

摘要

We define a new learning task, minimum averagelookahead grammar induction, with strong potentialimplications for incremental parsing in NLP andcognitive models. Our thesis is that a suitable learningbias for grammar induction is to minimize thedegree of lookahead required, on the underlyingtenet that language evolution drove grammars to beefficiently parsable in incremental fashion. The inputto the task is an unannotated corpus, plus a nondeterministicconstraining grammar that serves asan abstract model of environmental constraints con-firming or rejecting potential parses. The constraininggrammar typically allows ambiguity and is itselfpoorly suited for an incremental parsing model,since it gives rise to a high degree of nondeterminismin parsing. The learning task, then, is to inducea deterministic LR(k) grammar under whichit is possible to incrementally construct one of thecorrect parses for each sentence in the corpus, suchthat the average degree of lookahead needed to doso is minimized. This is a significantly more dif-ficult optimization problem than merely compilingLR(k) grammars, since k is not specified in advance.Clearly, na(I)ve approaches to this optimizationcan easily be computationally infeasible. However,by making combined use of GLR ancestor tablesand incremental LR table construction methods,we obtain an O(n3 + 2m) greedy approximationalgorithm for this task that is quite efficient inpractice.