Parsing Beyond Context-Free Grammars
Springer Science & Business Media, Aug 16, 2010 - Language Arts & Disciplines - 248 pages
Given that context-free grammars (CFG) cannot adequately describe natural languages, grammar formalisms beyond CFG that are still computationally tractable are of central interest for computational linguists. This book provides an extensive overview of the formal language landscape between CFG and PTIME, moving from Tree Adjoining Grammars to Multiple Context-Free Grammars and then to Range Concatenation Grammars while explaining available parsing techniques for these formalisms. Although familiarity with the basic notions of parsing and formal languages is helpful when reading this book, it is not a strict requirement. The presentation is supported with many illustrations and examples relating to the different formalisms and algorithms, and chapter summaries, problems and solutions. The book will be useful for students and researchers in computational linguistics and in formal language theory.
What people are saying - Write a review
We haven't found any reviews in the usual places.
2 Grammar Formalisms for Natural Languages
4 Tree Adjoining Grammars
5 Parsing Tree Adjoining Grammars
6 Multiple ContextFree Grammars and Linear ContextFree Rewriting Systems
7 Parsing MCFG LCFRS and Simple RCG
8 Range Concatenation Grammars
active items adjunction arity Automata automaton auxiliary tree bottom-up Boullier chart parsing Chomsky Normal Form complete CompleteNode components compute contains Context-Free Grammars context-free languages copy language corresponding CYK algorithm daughters deduction rules defined Definition derivation tree dim(A Earley algorithm Earley parsing elementary tree EPDA equivalent example finite set foot node Furthermore given goal item grammar formalisms indexed grammar initial tree instantiated clause Joshi k-MCFL Kallmeyer label LCFRS left-hand side lexicalized linear LR parser MCFG MCTAG mildly context-sensitive moves the dot natural languages non-terminals NP VP obtain operation parse trees parser parsing algorithms passive items position production pumping lemma range boundaries Range Concatenation Grammars range constraint vector range vector regular language S(XYZ scan simple RCG SRCG string language substitution node substrings subtree Swiss German terminals thread top-down top-down parsing tree-local treebanks tuple variables word yield