Transducers from Rewrite Rules with Backreferences

Proceedings of EACL '99 Transducers from Rewrite Rules with Backreferences Dale Gerdemann University of Tuebingen K1. Wilhelmstr. 113 D-72074 Tuebingen dg@sf s. nphil, uni-tuebingen, de Gertjan van Noord Groningen University PO Box 716 NL 9700 AS Groningen vannoord@let, rug. nl Abstract Context sensitive rewrite rules have been widely used in several areas of natural language processing, including syntax, morphology, phonology and speech pro- cessing. Kaplan and Kay, Karttunen, and Mohri & Sproat have given vari- ous algorithms to compile such rewrite rules into finite-state transducers. The present paper extends this work by al- lowing a limited form of backreferencing in such rules. The explicit use of backref- erencing leads to more elegant and gen- eral solutions. 1 Introduction Context sensitive rewrite rules have been widely used in several areas of natural language pro- cessing. Johnson (1972) has shown that such rewrite rules are equivalent to finite state trans- ducers in the special case that they are not al- lowed to rewrite their own output. An algo- rithm for compilation into transducers was pro- vided by Kaplan and Kay (1994). Improvements and extensions to this algorithm have been pro- vided by Karttunen (1995), Karttunen (1997), Karttunen (1996) and Mohri and Sproat (1996). In this paper, the algorithm will be ex- tended to provide a limited form of back- referencing. Backreferencing has been im- plicit in previous research, such as in the "batch rules" of Kaplan and Kay (1994), brack- eting transducers for finite-state parsing (Kart- tunen, 1996), and the "LocalExtension" operation of Roche and Schabes (1995). The explicit use of backreferencing leads to more elegant and general solutions. Backreferencing is widely used in editors, script- ing languages and other tools employing regular expressions (Friedl, 1997). For example, Emacs uses the special brackets \( and \) to capture strings along with the notation \n to recall the nth such string. The expression \(a*\)b\l matches strings of the form anba n. Unrestricted use of backreferencing thus can introduce non-regular languages. For NLP finite state calculi (Kart- tunen et al., 1996; van Noord, 1997) this is unac- ceptable. The form of backreferences introduced in this paper will therefore be restricted. The central case of an allowable backreference is: x ~ T(x)/A__p (1) This says that each string x preceded by A and followed by p is replaced by T(x), where A and p are arbitrary regular expressions, and T is a trans- ducer) This contrasts sharply with the rewriting rules that follow the tradition of Kaplan & Kay: ¢ ~ ¢l:~__p (2) In this case, any string from the language ¢ is replaced by any string independently chosen from the language ¢. We also allow multiple (non-permuting) back- references of the form: ~The syntax at this point is merely suggestive. As an example, suppose that T,c,. transduces phrases into acronyms. Then x =¢~ T=cr(x)/(abbr)__(/abbr> would transduce <abbr>non-deterministic finite automaton</abbr> into <abbr>NDFA</abbr>. To compare this with a backreference in Perl, suppose that T~cr is a subroutine that con- verts phrases into acronyms and that R~¢,. …

Content truncated to 500 words