Two Parsing Algorithms by Means of Finite State Transducers

Two Parsing Algorithms by Means of Finite State Transducers Emmaimel Re che* Mitsubishi Electric Kesearch I,aboratories 201, Broadway, (htmbridge, M A 021:/9, roche((0nierl.conl Abstract We present a new apl)roach , ilhlstrated by two algo- rithms> for parsing not only Finite SI.ate (:Iranlnlars but also Context Free Grainlnars and their extension, by means of finite state machines. '/'he basis is the com- putation of a flxed point of a linite-state function, i.e. a finite-state transducer. Using these techniques, we have built a program that parses French sentences with a gramnlar of more than 200>000 lexical rules with a typical response time of less than a second. The tirst al- gorithm computes a fixed point of a non-deterluinistic tinite-state transducer and the second coniplites a lixed point of a deterministic bidirectiollal device called a bimachine. These two algoril;hms point out a new con- nection between the theory of parsing and the theory of representation of rational transduetions. INTRODUCTION Fhlite state devices have recently attracted a hit of interest in computational linguistics. Couiputational ellieioncy has been drastically improved for n)orpho- logical analysis by representing large dictionaries with Finite State Automata (FSA) and by representhig two- level rnles and le×ical hlforination with finite-state transducers [8, 4] More recently, [11] has achieved pars- ing with low level lexical sensitivity by nleans of linite state automata. Finite state apl)roximation of co~,text- free grammars also proved both useful and efficient for certain application [9]. One COlYimon rnotiwttion of all this work is to inl- prove efficiency dranlatically, hoth hi tel'illS of ti nle and sl)a, ee. These results often provide l)rOgl'anls orders of magnitude faster than more traditional hnplenienta- lions. Moreover, F~As are a natural way I.o express lexieal sensitivity, which has always lieell a reqlih'enient in lnorphology and which has proved crucial in syll- tax. The granllllar we used for French: called Lexh:on- Grammar (set, [61 [7] [2] [3] [i01 for insta,,cc), pushes the lexiealization very far and it is our I)elief that this lexicalization trend will alnplify itself and that it will restllt i,l grammars several orders of magnitnde larger than today's representations. This nncovers the need for new methods that will be able to handle such large scale grammars, *Supported by a DRI']T-EcoIe l%lytechnique contract, this work w;Ls done at the ]nstitut (~;tSl)~u'd Monge and ~tt the LADL. Ilowever, a tnahl drawback of the lit;ire st,ate ap- proach to syntax is the dilllcnlty of representing hier- archical data; this partly explains why l'~SA-based pro- gralllS ollly do illcnllll)lete parsillg. This I)itl)er l)resents a ilew i)arshig al)proach based on linite-stal.e trallsdlle- ors, a device that }laS been used ah'eady ill Inorl)liohlgy [81 btit not yet hi synl.~tx, that provides both hierar- chical representations and efllciency hi ;t shnple and natural way. ';'lie represelitatioil is very compact, this allows to hnl)lelllellt large lexical g.ra[ri[nars. Two NOW parshlg algorithms ilhistrate the approach llresented hero. The th'st one uses a finite state l;l'ai/s- duo;Jr alld conlpul;es a fixed point, llllt finite state Ii'ansducer,% unlike F.<JAs, cannot be niade …

Content truncated to 500 words