An Implementation of a Multilingual Regular Expression Segmentor for Ordinary and Morphologically Rich Lexical Tokens

An Implementation of a Multilingual Regular Expression Segmentor for Ordinary and Morphologically Rich Lexical Tokens Paul Wu Horng Jyh and Kevin Cheong Institute of Systems Science, National University of Singapore, Singapore 0511 Email: <paulwu, kcheong>ei iss.nus.sg Abstract Lexical pattern matching and text extraction is an essential component of many Natural Language Processing applications. Following the language hierarchy first conceived by Chomsky, it is commonly accepted that simple phrasal patterns should he categorised under the class of Regular Language (RL). There are 3 operations in RL - Union, Concatenation and Kleene Closure - which are applied to a finite lexicon. The machinery that recognises RL is the Finite State Machine (FSM). This paper discusses and postulates that the degree with which a class of patterns exercise the aspects of RL operators, is directly proportional to the richness in morphology of lexical tokens. 1 Introduction Lexical pattern matching can be used to recognise phrasal patterns of different languages and which reflect morphological variations. For example, it is used to recognise regular English phrasal verbs like ".. give * up .." or reduplicated Chinese words like "GaoXing-Bu- GaoXing" (literally "happy-not-happy"). Simple phrasal patterns are categorised under the class of Regular Languages (RL) [2]. The degree with which lexical patterns within the language exercise the RL operators varies. Certain classes of lexical patterns, for instance (dead) idioms and Chinese lexicon items, are quite fixed. For such cases, the Concatenation operator in RL is sufficient to generate and recognise the patterns. On the other hand, there are other instances, such as the phrasal verbs and word reduplications (as shown above), which require a combination of Kleene Closure, the Don't-Care symbol and Back-Referencing (a special device by which we can encode a class of word-reduplication as the pattern ( s rrir) where r is the reduplicated word) [4]. An interesting theoretical question to ask here is — can we classify lexical patterns based on the degree with which they exercise the aspects of RL operators'? This theoretical question has a further implication to the implementation of such pattern recognition machines. Principle 1: Each class of lexical patterns should be handled by different classes of machinery to take advantage of the computing efficiency. In this paper, we discuss the concepts and component techniques of a Regular Expression Segmentor (REXSEG) which adheres to Principle 1. A Lexical Pattern Command Language (LPCL) was designed and implemented as a grammar to assist computational linguists in matching and processing significant lexical patterns in texts. Finally we detail comparisons with other lexical pattern matchers in use today and the future development of REXSEG. 267 2 Regular Expression Segmentor 2.1 Background REXSEG is an implementation of a lexical pattern matcher — a compiler which lexically analyses and parses a set of phrasal patterns defined by the LPCL. Intermediate code is generated for matching phrasal patterns in normal texts. REXSEG allows application development programmers and computational linguists to develop sophisticated lexical analysers and parsers based on extended RL processing techniques. 2.2 Regular Language Regular …

Content truncated to 500 words