In his 1983 dissertation [1], Kimmo Koskenniemi proposed a declarative system of constraints for describing morphological alternations. Constraints of this type are known as two-level rules. Two-level rules are similar to phonological rewrite-rules introduced in the 1960s by Noam Chomsky and Morris Halle [2] in that both types of rules denote regular relations [3, 4, 5]. Consequently, they can be modeled by finite-state transducers. An important difference is that rewrite-rules are applied in a serial order whereas two-level rules are parallel constraints that have to be satisfied simultaneously. The two-level formalism is expressive enough so that it can describe phenomena that in classical phonology require rule ordering [6].
The compiler described in this document (TwoL Compiler) converts two-level rules to deterministic, minimized finite-state transducers. The first version of the compiler was written in 1985-1987 in Interlisp by Lauri Karttunen, Kimmo Koskenniemi, and Ronald M. Kaplan. The current C version, based on Karttunen's 1989 Common Lisp implementation, was written by Lauri Karttunen, Todd Yampol, and Kenneth R. Beesley (Microlytics) in consultation with Ronald M. Kaplan at Xerox PARC in 1991-92. The compilation algorithm and the rule formalism are as described in [8]. The compiler currently works on Macintosh and UNIX operating systems. The interface to the compiler described here is common to both versions. The transducers produced with the compiler, combined with a lexicon, can be used for word recognition and generation in systems such as Koskenniemi's two-l program [1] and Evan Antworth's PC-KIMMO [7].
Section 2 of this document (Running the compiler) gives an example of how to apply the compiler to an existing set of rules. Readers who are unfamiliar with two-level grammars may wish to start by first reading Section 3 (Two-level grammars) that specifies the grammar format and the rule formalism in detail. Section 4 (Error checking) and 5 (Rule testing) describe ways in which the compiler can assist the rule writer in the development of a two-level grammar. Section 6 (Compiler options) contains further details about the user interface to the compiler. Appendix 1 lists the on-line help messages; Appendix 2 is an example of a two-level grammar.
When you start the compiler (by double-clicking the icon on a Macintosh or by typing 'twolc' in UNIX), it prints a welcoming banner and waits for the user to type a command:
(1)
******************************************************
* Two-Level Compiler 1.0 *
* created by *
* Lauri Karttunen, Todd Yampol, *
* Kenneth R. Beesley, and Ronald M. Kaplan. *
* Copyright (c) 1991-92 by the Xerox Corporation. *
* All Rights Reserved. *
******************************************************
Compiler commands: compile, install-binary, intersect,
list-rules, read-grammar, save-binary,
save-tabular, show, show-rules.
Switches: resolve, time, trace.
Information: ?, banner, help, storage, switches.
Command (C-Q = quit):
Let us start with 'help':
(2)
The two main commands are 'read-grammar' and 'compile'. To illustrate what they do, let us assume that the user has the following mini-grammar stored as a file named rules.txt:Command (C-Q = quit): help Typing "help" explains what does. "help all" prints out all help messages "?" prints a list of available commands. Command (C-Q = quit):
(3)
! First example. Two rules for making the lexical form "kaNpan"
! realized as "kamman".
Alphabet
a b c d e f g h i j k l m N:m N:n n o p q r s t u v x y w z ;
Rules
"N realized as m" ! Before a lexical "p." Always, and only there.
N:m <=> _ p: ;
"p realized as m" ! After a surface "m". Always and only there.
p:m <=> :m _ ;
Note that the exclamation mark is a comment character; after seeing !, the compiler ignores the rest of line. (More about the format of the grammar in Section 3.)
The first step towards getting the rules converted to transducers is to have the compiler read them and verify that there are no syntactic errors in the input. This is what the command 'read-grammar' does, after prompting the user for the name of the input file.
(4)
As it processes the input, the compiler prints messages about its progress and about errors it detects along the way. Here no errors occurred during `read-grammar', so we are ready for the next step, `compile':Command (C-Q = quit): read-grammar Input file: rules.txt reading from 'rules.txt'... Alphabet... Rules... "N realized as m" "p realized as m" Command (C-Q = quit):
(5)
Command (C-Q = quit): compile
Compiling "rules.txt"
Expanding... Analyzing...
Compiling rule components:
"N realized as m" "p realized as m"
Compiling rules:
"N realized as m"
N:m <=>
"p realized as m"
p:m <=>
Done.
Command (C-Q = quit):
The commands 'show-rules' and 'show' display on the screen the resulting transducers; 'show-rules' displays all the compiled rules, and 'show' prompts for a rule name and displays just the transducer for that rule.
(6)
Transducers are displayed on the screen as tables in which each row represents a state and the columns represent transition functions for a class of symbol pairs. In a transducer, all symbols are pairs but conventionally we write just one symbol when the two members of the pair are the same. Thus a and p in the table above mean a:a and p:p, respectively. The first member of a pair is a lexical symbol, the second is a surface symbol. The rows are labeled with the name of the state (an integer) followed by a colon if the state is final and a period if it is nonfinal. At the head of each column is the representative first member of a class of symbol pairs that have the transitions indicated by the column. For example, the number 3 in the first row of the N:m column in the above table means that there is a transition from state 1 (a final state) to state 3 (a nonfinal state) labeled N:m.Command (C-Q = quit): show Rule name: "N realized as m" a p N:m N:n 1: 1 1 3 2 2: 1 3 2 3. 1 Equivalence classes: ((a b c d e f g h i j k l m n o q r s t u v w x y z) (p p:m) (N:m) (N:n)) Command (C-Q = quit):
Only some of the transitions are shown explicitly; the rest can be inferred from the listing of equivalence classes at the bottom of the table. It shows that N:m is in a class by itself, but the p column also represents the transitions of p:m. The equivalence class headed by a contains most of the symbol pairs in the alphabet. Thus the number 1 in the first row of the a column means that there is a transition from state 1 back to itself labeled a; and because a stands for the whole equivalence class (a b c ... x y z), the transducer will react to all these symbol pairs in the same way.
The absence of a transition means that the transducer fails in that state on that input. For example, if the transducer is in state 3, a p or p:m must follow in the input string because the state is nonfinal and there are no transitions for other input pairs.
A conventional state diagram for the same transducer is shown below.
(7)
This table is equivalent to the state diagramCommand (C-Q = quit): show "p realized as m" a m p p:m 1: 1 2 1 2: 1 2 2 Equivalence classes: ((a b c d e f g h i j k l n o q r s t u v w x y z N:n) (m N:m) (p) (p:m))
(8)
The command 'lex-test' prompts for a lexical string and applies the transducers to it, returning any surface strings that are generated and the mapping from the lexical to the surface string as a listing of symbol pairs.Command (C-Q = quit): list-rules "N realized as m" 3 x 4 "p realized as m" 2 x 4
(9)
Command (C-Q quit): lex-test
Lexical string (q = quit): kaNpat
kammat
k
a
N:m
p:m
a
t(10)
The results of the compilation can be saved in two formats: 'save-binary' and 'save-tabular'. The command 'save-binary' produces a compact binary file from which the automata can be reloaded to the compiler for testing or intersection; 'save-tabular' makes a simple ASCII file that can be read in by Kimmo Koskenniemi's two-l program for morphological analysis. We expect that future versions of PC-KIMMO [8] will also accept the same tabular format.Command (C-Q = quit): pair-test Lexical string (q = quit): kaNpat Surface string (q = quit): kammat k a N:m p:m a t ACCEPTED Lexical string (q = quit): kaNpat Surface string (q = quit): kampat k a N:m p REJECTED: "p realized as m" fails in state 2.
Both save-commands first prompt the user for the name of the output file:
(11)
The resulting tabular file looks like this:Command (C-Q = quit): save-tabular Output file: rules.aut Writing "rules.aut" Command (C-Q = quit):
(12)
ALPHABET N a b c d e f g h i j k l m n o p q r s t u v w x y z NULL 0 END AUTOMATA "N realized as m" 3 4 1: 1 1 3 2 2: 1 0 3 2 3. 0 1 0 0 "p realized as m" 2 4 1: 1 2 1 0 2: 1 2 0 2 ALIGNMENT a a 1 1 b b 1 1 ... [omitting alignments of b:b, c:c, etc.] z z 1 1 N m 3 2 N n 4 1 p m 2 4 END
Transition tables in a tabular file are the same that 'show' and 'show-rules' display on the screen except that 0 rather than a blank is used to indicate that there is no transition for a symbol. Equivalence classes are not explicitly shown. The alignment table at the end of the file indicates for every pair in the alphabet which column in each transducer applies to that pair. For example, the line
means that the transitions for the pair N:m are in the third column of the first transducer and in the second column of the second transducer.N m 3 2
If the number of rules is not too large and the transducers are not big, it may be advantageous to combine them into a single transducer. This is what the command 'intersect' does:
(13)
The user has the option of selecting a set of rules to be intersected or applying the operation to all the rules. The default is to intersect all rules. Another option is to choose a name for the result of the intersection. If the user simply hits a carriage return in response to both prompts, as in the example above, the result is called "Unnamed 1".Command (C-Q = quit): intersect Intersect all rules? (y/n) [y]: Name the intersection: Composing common alphabet...Expanding...Intersecting... 4 states, 6 equivalence classes, 15 arcs. Command (C-Q = quit):
Intersected rules can be displayed and saved with the same commands as the input automata:
(14)
This single transducer describes the same relation as original rules in tandem but we can no longer see which individual rule causes the rejection of an incorrect pair:Command (C-Q = quit): show-rules "Unnamed 1" a m p N:m N:n p:m 1: 1 3 1 2 4 2. 3 3: 1 3 2 4 3 4: 1 3 2 4 Equivalence classes: ((a b c d e f g h i j k l n o q r s t u v w x y z) (m) (p) (N:m) (N:n) (p:m))
(15)
The intersection of two or more rule transducers typically has more states than its components; in the worst case its size is the product of the input sizes. The processing time required to run a transducer during analysis or generation is fairly constant and independent of the size; if it is feasible to intersect some rules, the resulting system is faster.Command (C-Q = quit): pair-test Lexical string (q = quit): kaNpat Surface string (q = quit): kampat k a N:m p REJECTED: Rule "Unnamed 1" fails in state 2.
Appendix 2 illustrates the use of the compiler on a larger and more sophisticated set of rules.
The compiler expects as its input a two-level grammar. A two-level grammar is a system of rules that constrain the surface realization of lexical forms, hence the name two-level rule. Two-level rules are parallel constraints; a pairing of a lexical form with a surface form is valid only if it satisfies all the rules. In principle, the grammar could consist of just a set of rules and a specification of a pair alphabet, but in practice it is useful to introduce some auxiliary notions. In this section we first describe the general format of a two-level grammar and then focus on some important details.
3.1 General format
A two-level grammar consists of sections that are headed by a
keyword. Every grammar must start with an Alphabet declaration
and end with Rules. In addition there may be three optional
sections headed by the keywords Diacritics, Sets, and
Definitions. In addition, comments can be freely inserted
anywhere. Anything that follows an exclamation mark, up to the end of
the line, is treated as a comment and ignored. If ! or
some other special symbol is used as an ordinary character, it must be
immediately preceded with a %.
The Alphabet section is a list of elements (single symbols,
complete or incomplete pairs) terminated with a semicolon. The rule
compiler needs to know all symbols in the lexical and surface alphabet
and all possible correspondences. Much of that information it can
deduce directly from the rules. But if some symbol or correspondence
is not explicitly mentioned elsewhere, it must be declared in the
Alphabet section. For example:
(16)
The optional Diacritics section is a list of single lexical
symbols terminated with a semicolon. The compiler converts them to a
list of diacritic pairs with zero surface realization. Diacritics are
typically used as features that force or block the application of
particular rules. All rules that do not specifically refer to a
diacritic allow that diacritic to occur freely without affecting the
context that the rule specifies. For example, the declaration
(17)
The optional Sets declaration serves the same purpose as
distinctive features in generative phonology: it enables the user to
define classes of symbols that are equivalent in some respect. For
example, it is often useful to define a set of vowels and a set of
consonants:
(18)
(19)
(20)
The optional Definitions section allows the user to write
regular expressions to create and name two-level relations. For
example,
(21)
The Rules section is the last part of a two-level grammar:
(22)
3.2 Regular Expressions
Like the definitions, the correspondence and context parts of rules
are written as regular expressions of symbol pairs. Symbols that occur
as the first member of some pair constitute the lexical
alphabet, the set of second members is called the surface
alphabet. The total pair alphabet of a grammar is called the set
of feasible pairs. Because all symbols in two-level rules
denote pairs (for convenience x:x is written as
x), the regular expressions of a two-level grammar
designate equal-length relations rather than simple string
languages. The correspondence part typically consists of a single pair
but it can be a more complicated expression, for example, a union of
pairs. This section reviews the syntax of regular expressions
recognized by the compiler and the regular relations over symbol pairs
that they denote.
3.2.1 Brackets and Parentheses
Enclosing a regular expression in a pair of matching brackets yields
an equivalent expression: a:b, [a:b],
[[a:b]], etc. denote the relation consisting of the
single pair a:b. An empty pair of brackets,
[], denotes the empty relation that maps the
empty string to itself.
Round parentheses indicate optionality. (A) denotes
the union of the relation A with the empty
relation.
Curly brackets, { }, can be used as an alternative to
square brackets to form a union of regular relations. Union and other
Boolean operators are discussed in section 3.2.4.
If brackets or parentheses are used as ordinary symbols, they must be
prefixed with a percent sign; for example, %[ is the
relation that maps the left bracket to itself.
3.2.2 Special symbols
The numeral 0 (zero) is special when it does not
constitute a part of some larger symbol (as in
007). It is the conventional two-level counterpart of
the epsilon symbol which stands for the empty string. But for
technical reasons 0 is different from epsilon in that
it is treated like any other symbol during the compilation of
two-level rules to transducers. In the two-level calculus, all regular
expressions must denote pairs of strings that are of the same length,
thus in a:0 both the lexical side of the relation,
a, and the surface side, 0, are
one-element strings. This is important because only equal-length
regular relations (see [5]) are closed under intersection and
negation, which are essential operations in the compilation of
two-level rules to transducers. The interpretation of zero as the
empty string takes place only in the application of the resulting
transducers to input strings. A zero that is prefixed with a percent
sign, %0, is interpreted as an ordinary numeral.
In the two-level calculus, the question mark ? stands
for the union of all known and unknown feasible pairs; it is called
the other symbol. When a regular expression containing
? is compiled into an automaton, the interpretation of
? is dynamically updated to reflect the changes in the
pair alphabet. For example, in the course of converting the
sequence
(23)
(24)
The current implementation of the compiler assumes that the pair
alphabet is completely specified by the Alphabet declaration in
conjunction with the rules. When the total pair alphabet becomes
known, the compiler removes all remaining instances of
? from the automata. Consequently, the transducers
fail to apply to strings that contain unknown symbols. Because this
has proved inconvenient in practice, future versions of the compiler
may retain ? in output tables as a place holder for
new symbols.
For historical reasons, and for backward compatibility with older rule
systems, the compiler also recognizes the equal sign,
=, as a special any symbol. The interpretation
of = as a single symbol is the union of all feasible
pairs. It is like ? except that ? also
potentially includes unknown pairs. Symbol pairs in which
= appears on one side are interpreted in the same
manner as incomplete pairs (see next section). For example,
a: is equivalent to a:=.
The symbol # is commonly used to indicate a lexical
word boundary. Languages typically have rules that refer to the
beginning or the end of words. The compiler does not need to give any
special treatment to #, but other software that uses
the results of the rule compiler may have a built-in assumption that
words are flanked by #.
3.2.3 Incomplete pairs
It is possible to leave one side of a symbol pair unspecified. Such
one-sided pairs are interpreted as the union of all feasible pairs
which contain the specified symbol on the appropriate side. For
example, if k appears on the lexical side only in the
feasible pairs k, k:0,
k:v and k:j, then the one-sided symbol
k: is implicitly defined as the union of these four
relations. Similarly, :k denotes the union of all
feasible pairs that have k as the surface symbol.
The equal sign may be used as a filler in a partially specified pair:
k:= and =:k are equivalent to
k: and :k, respectively. It is also
legal, although possibly confusing, to use a plain colon to stand for
a completely unspecified pair, denoting the union of all feasible
pairs, which is what a lone = also means.
This declaration tells the compiler that a (=
a:a), b:0, and 0:c are
possible pairs. It does not constrain them in any way. If
b and b:0 are possible pairs and there
are no rules that require b to be realized only one
way in some contexts, then b can be deleted or
realized as b anywhere. The incomplete pair
:d tells the compiler that d is a
possible surface symbol but does not indicate what its lexical
counterparts are; e: stands for pairs that have an
e on the lexical side. Because incomplete pairs like
:d and e: in the Alphabet
section are meaningful only if there are complete pairs of that type
declared elsewhere, it is not necessary to mention them, although it
may be a useful reminder for the rule writer.Alphabet
a b:0 0:c :d e: ;
tells the compiler that ':0 and @:0 are
possible pairs but are irrelevant to any rule that doesn't mention them
explicitly.Diacritics
' @ ;
A symbol that has been defined as a set can be used in a rule to replace a
union. For example, Sets
Vowel = a e i o u;
Cons = b c d f g h j k l m n p q r s t v x y w z ;
VclessStop = k p t ;
Liquid = l r ;
is equivalent tok:0 <=> Vowel _ Vowel ;
Similarly, Vowel:0 means {a:0 | e:0 | i:0 | o:0
| u:0}, assuming that all five pairs occur somewhere in the
grammar (more about that in Section 3.6).k:0 <=> {a | e | i | o | u} _ {a | e | i | o | u} ;
defines ClosedOffset as a relation that has on the
surface side a consonant followed by a second surface consonant or a
word boundary on the lexical side. When ClosedOffset
is found in a rule, the compiler interprets it as a reference to a
relation it only needs to compute once. From the grammar writer's
point of view, definitions can be thought of and used like macros.Definitions
ClosedOffset = :Cons {:Cons | #:} ;
Each rule must have (1) a name, written within double quotes,
(2) a lexical:surface correspondence like k:0
that is constrained by the rule, (3) a rule operator that
defines the nature of the constraint, (4) one or more contexts,
divided between a left and a right context by an
underscore, and, optionally (5) a where-clause that specifies
the assignment of values to variables (if any). Each context and the
optional where clause must be terminated with a
semicolon. Although the formalism does not require it, in practice it
is useful to include a couple of comment lines (starting with
!) to explain what the rule is intended to do. If a
semicolon, underscore or exclamation point is used in a rule as an
ordinary symbol, it must be prefixed with %, the
escape character. The same goes, of course, for the escape character
itself.Rules
"Consonant gradation" ! Single k, p, and t are realized as
! zero, v, and d, respectively, in the
! beginning of a closed syllable.
Cx:Cy <=> h | Liquid | Vowel: _ Vowel ClosedOffset;
where Cx in (k p t)
Cy in (0 v d)
matched ;
"Geminate gradation" ! Geminate stops are shortened to
! single stops in a closed syllable.
Cx:0 <=> Cx _ Vowel ClosedOffset ;
where Cx in VclessStop ;
to a transducer from left to right, the first member of the
concatenation starts out just as other and becomes the union of
other with a:b and c:d as the
interpretation proceeds. An equivalent expression for the same
relation is? a:b c:d
where the brackets and vertical bars mark the union. A question mark
prefixed with a percent sign, %?, is interpreted as a
question mark without a special meaning.[ ? | a:b | c:d] a:b c:d
