LR(k)-Parsing of Coupled-Context-Free Grammars

LIl~(k)- I'msing of C( ut 1 A-Cont(xt,-]~ (c Grammars :) -) 0 " ~ ~ ~ '~* ~ * G~se]a Pit;sch l°B lnfornlatik, Universil.i;t des Saarland(!s 1).-6612',/Saar])r{icken, (]ermany E-marl: pitsch~cs.uni-sb.de Abstract (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 Adjobling Languages, e.g. those modelling cross-serial dependencies, c:tn ])e ge.nerate.d by LR(k) Coupled--Context.-]:ree (Iranlmars. ] Introduction ill order to process ll&ttlra[ I;t/l~ll;l~,eS 3 ;Vfl first }lave to model the synta× formally. Many investigations ;is~ e.g., [lligS,l ] show th~tt this cannot be done by context- free graliilllars ((Jl!'(ls). I"or context-sensitive ~.,,l'allllllars which are powerful enough, it is kn(iwlt that the anal5'- sis is PSl)ACl:,--coml~lete. q'hus, there is a trade-off' he tween tile power of the. formalism and it;; analysis coln- plexlty. To solve this dilenlma, much work has ]men done tO char;t(:terize l;tllgl|al~e classes ill Detweett coltt(!xt-free and context-sensitlve languages he{rig powerful enough to model the syntax o[' natural ]allgllages hut endowed with at Imlynomial time analysis. (2mll)[{:(l-(;onl.ext-I"ree Gram mars represent such a. forma]isnl yeneralizhlg CI"Cs. Their suitability to model syntactical phenmnen:t fo]h)ws [rom the fact that they include tit{.' ]itllgllaJ!,eS ~.;CllCl'il(Cd by (he Tree Adjoining (h'ammars (TACs) (i]' [.hls87] as (me sub- class. Anlung other properties, both f()rmallsms are ;d)le to model tim linguistic phenomenon of cross s(:ri;d depen. dencies, which is not context.free hut ]'rcquently appears in natural languages (of. [Shi86]). The formalism of (fOul)led-Context-Free (',ramnlars ]tits been introdu<:ed in [CIIR92] and [Cua92]. It h,'.hmt, s to ~l~(: family (ff v'egulate<l striwg rewriting syslems investigated in [1)P89]. The inc:ruased generative capa<:ity is o])laincd by allowing to rewrite sintultanemlsly a {retain iHllllbCl' of elements. Other regulated string rewriting systems its, e.g., the Scatte.red (Jontext (ll'allllllars of [(',llft.q] general- ize CFCs by allowing simultaneous rewriting of arbitrary combinations o] elements. [n [I)P89], it is shown that this results in languages which are not sentillnear. But semilin= earity is important since it formalizes the "conslant-growth lm)pe.rty" of natural lanyuages (cf. [3os85]). In co,,t,'ast to these, all languages defined by our I'urmallsnl are semi[{near *'['his research has been supported hy a (h'aduh:rtenkol]cg- fellowship of the I)cutsche l"orschtmgsgenleinschaf(. because of two restrlctions. First, only those elementsean he rewritteu simultaneously whh:h were produced by the same re.writing. Second, the Coupled-Conte×t-Free (]ram- llial'S coltsi(ler e]ellleltts Iewr[tten SillllllLalleo|tsly ;ts COil|- portents of ;t parenthesis. Those can only l)e substituted if they form a parenthesis and t]ley can only he suhstitutetl [)y seqlteltc(!s of pa.r(.*lll,heses cov'rectly nested. …

Content truncated to 500 words