Paper: Two Parsing Algorithms By Means Of Finite State Transducers

ACL ID C94-1071
Title Two Parsing Algorithms By Means Of Finite State Transducers
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1994
Authors

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 r...