A transducer program consists of an (optional) sequence of alphabet and variable definitions followed by
a single transducerexpression which defines the result transducer.
Alphabet
An alphabet definition consists of the keyword ALPHABET followed by = and some transducer expression e.g.
ALPHABET = [a-z]:[A-Z]
This command redefines the alphabet as the set of symbol pairs occurring on the transitions of the
transducer. Occurrences of two-level operators, negation operators and unquoted periods always have to be
preceded by an alphabet definition.
Variables
There are two different types of variables. Symbolsetvariables are enclosed by hash signs (#) and take
symbol sequences (see below) as values:
#UC# = A-Z
#LC# = a-z
Transducervariables are enclosed by dollar signs and take transducer expressions as values:
$MAP$ = [a-z]:[A-Z]+
$MAP$ = [#LC#]:[#UC#]+
Variables whose name starts with the symbol `=' are special agreement variables. If an agreement variable
occurs more than once in a transducer expression, it will always have the same value. Consider the
following transducer program:
$=1$ = [abc]
$=1$ X $=1$
The result transducer recognizes the strings aXa, bXb, and cXc. Only acyclic transducers (i.e.
transducers with a finite set of string mappings) can be assigned to agreement variables.
Symbols
A symbol is either
- a single character like A s 5,
- a quoted character like \* or \_,
- a multi-character symbol like <X> or <ab.c5> (which is always
enclosed in angle brackets) or
- a backslash followed by a number which is the numeric code of the
designated character
- the null symbol <>.
Symbol sequence
A symbol sequence is a sequence of characters, multi-character symbols and character ranges, e.g. a-z \.
<x>.
symbol range
A symbol range is either
- a single symbol
- a symbol sequence enclosed in square brackets like [A-Za-z] or
- a symbol sequence starting with ^ and enclosed in square brackets like [^A-Za-z] (designating the
complement of [a-zA-Z]) or
- the period (which represents any symbol from the alphabet)
Transducer expressions
A transducer expression (TE) is recursively defined as follows:
- A pair of two symbol ranges separated by a colon is a TE.
[a-z]:[a-Z]
- A single symbol range like [a-z] is a TE.
It is a short form for [a-z]:[a-z].
- Two symbol sequences enclosed in braces and separated by a colon are
a TE. {a[bc]}:{def} is equivalent to a:d b:e <>:f | a:d c:e <>:f.
- X Y is a TE if X and Y are TEs.
(Blanks are ignored unless they are quoted.)
- (X) is a TE if X is a TE.
- X op is a TE is X is a TE and op is either * (Kleene's star operator), +
(Kleene's plus operator), or ? (optionality operator)
- op X is a TE is X is a TE and op is either ! (negation operator), ^
(target language extraction operator), _ (source language extraction operator), or ^_ (source and target
switch operator).
- X op Y is a TE is X and Y are TEs and op is either & (conjunction
operator), | (disjunction operator), || (composition operator), or - (subtraction operator)
- L x op y R is a TE if L and R are TEs, x and y are symbol ranges and
op is either => (two-level restriction), <= (two-level coercion), or <=> (two-level restriction and
coercion).
- X op L__R is a TE if X, L and R are TEs and op is either ^-> (upward
replacement), _-> (downward replacement), /-> (leftward replacement) or \-> (rightward replacement).
Furthermore, L and R must define automata (i.e. which map their strings onto themselves). These
operators correspond to Karttunen's replace operators. If the arrow is followed by a question mark (?),
the replacement becomes optional.
- X << l is a TE if X is a TE, and l is either of the form
a or the form a:b where a and b are single characters or symbols. The result is a transducer where l was
freely inserted into X. The transducer ab << c for instance is equivalent to c*ac*bc*.
- X op Y L1__R2, ... , LN__RN is a TE if X,Y, L1 through LN and R1
through RN are TEs, and op is either => (general restriction), <= (general coercion), ^=> (general
surface restriction), ^<= (general surface coercion), ^<=> (general surface restriction and coercion),
_=> (general deep restriction), _<= (general deep coercion), _<=> (general deep restriction and
coercion). (These operators were implemented following a suggestion by Anssi Yli-Jyra.)
- "fname" is a TE. The compiler reads the file named fname and turns
it into a transducer of the form line1|line2|line3|... where linex is the x-th line of the file. All
characters other than : and \ are interpreted literally (i.e. not as operators). This TE is typically
used e.g. to read morpheme list from a file.
- "<fname>" is a TE. The compiler reads a pre-compiled transducer from
the file named fname. This
Further Features
Comments start with the symbol % and extend up to the end of the line. Blanks are ignored unless they
are quoted. Expressions terminate at the end of a line unless the end of line is preceded by a backslash.
The command
#include "fname"
can be used to insert source code from a file named fname. The command
RE >> "fname"
stores the regular expression RE in the file fname. The command
#use hopcroft
tells the compiler to use the Hopcroft minimisation algorithm from now on, and
#use default
switches back to the default minimisation algorithm (Brzozowski). The command
Install Now
PNG Icons
