Paper: LR(k)-Parsing Of Coupled-Context-Free Grammars

ACL ID C94-1065
Title LR(k)-Parsing Of Coupled-Context-Free Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1994
Authors

(hmpled-Cmltext--l:ree (lrammars are a t~eneralizati(m of context-free, grammars obtained by combining nonter- minals to parcnthescs which can only be substituted si- mnltaneously, l/efl~rring to the generative capacity of the grammars we obtain an inlinite ]licrarchy <)f lanl4uages that comprlscs the context-free languages as the first and all the lattguages generated by ~lYee Adjoining Crammars (TA(;s) as the second eh'.ment. Ilere, we present a genera]izati(in of the context-free LR(k)--notion, which characterizes sub- classes of Couph:d-Context-[:ree (}ralltlltars and ihelefme for TAGs- which c;tn be. pa.rsed in linear time. The pars- ]rig proce.dure described works incrementally so that it can be used for on-llne l)arsing o[natural language. ]'~xanlples show that important Tree Adjobl...