fst-compiler(1)

📦 version 1.7.0, in debian bookworm, debian trixie, ubuntu jammy, ubuntu noble, ubuntu questing, ubuntu resolute, ubuntu stonking

💖 fst-compiler(1) — the manual page, but make it make sense 💖

okay bestie, sit down, hydrate, because this is the fst-compiler page from section 1 of the manual, and we're gonna go through every single thing in it. no skimming. no "tl;dr". we're eating the whole plate. 🍓

✨ NAME ✨

fst-compiler, fst-compiler-utf8 — two whole compilers for SFST programs. two of them. siblings. iconic behavior. 👑

✨ SYNOPSIS ✨

fst-compiler grammar-file [ output-file ]
fst-compiler-utf8 grammar-file [ output-file ]

like. that's the whole vibe. give it a grammar file, optionally give it an output file, and it does its little thing. 💅

✨ OPTIONS ✨

  • -c — stores the transducer in the compact format, the one that fst-infl2 is out here using. that's the whole point of this flag, no cap.
  • -l — stores the transducer in lowmem format. yes, "lowmem" like low memory. she's efficient. she's also picky about who can read her (spoiler: only fst-infl3).
  • -s — swaps the surface and analysis layer of the transducer. you literally have to use this switch if you want to use fst-infl (fst-infl2, fst-infl3) for generation instead of analysis. generation mode bestie. flip the switch or you're stuck analyzing forever. 🙈

✨ DESCRIPTION ✨

fst-compiler is a compiler for finite-state transducer programs. it generates a minimized finite state transducer, which you can then use with fst-mor, fst-infl, fst-print, fst-compare, fst-parse, and fst-lattice. that's the friend group right there. 🫶

the compact transducer representation — the one you get from the -c flag — is supported by fst-infl2, fst-train, and fst-match.

the memory-efficient transducer representation — the one you get from the -l flag — is only supported by fst-infl3. that's it. just the one. she's exclusive. 💅

so, the arguments:

  • the first program argument is the name of a file that contains the transducer program. the programming language is described below (and yes we're getting to all of it, stay with me).
  • the second argument is the name of the file where the resulting transducer gets written, in binary form.
  • if there's no second argument, the output goes to stdout. classic.

now, fst-compiler-utf8 — she differs from fst-compiler only in the character encoding. that's the entire difference. fst-compiler-utf8 supports UTF8 encoding of the source files, whereas fst-compiler is the one to use for 8-Bit character codes like latin1, which are an extension of the ASCII code. information about the encoding is stored in the transducer files, and the other SFST programs use it. so it's not just a vibe, it's in the file. 🌈

✨ FILE FORMATS ✨

a transducer program is made of:

  1. an optional sequence of alphabet and variable definitions, and then
  2. a single transducer expression, which defines the result transducer.

that's the structure. definitions first, one big expression at the end. periodt.

🌸 Alphabet 🌸

an alphabet definition is the keyword ALPHABET, followed by =, followed by some transducer expression, like:

ALPHABET = [a-z]:[A-Z]

this command redefines the alphabet as the set of symbol pairs occurring on the transitions of the transducer.

⚠️ heads up bestie: occurrences of two-level operators, negation operators, and unquoted periods always have to be preceded by an alphabet definition. always. no exceptions. don't test her.

🌸 Variables 🌸

there are two different types of variables, and you gotta know which is which.

Symbol set variables are enclosed by hash signs (#) and take symbol sequences (see below) as values:

#UC# = A-Z
#LC# = a-z

Transducer variables are enclosed by dollar signs and take transducer expressions as values:

$MAP$ = [a-z]:[A-Z]+
$MAP$ = [#LC#]:[#UC#]+

and then there's the special one. variables whose name starts with the symbol = are agreement variables. if an agreement variable occurs more than once in a transducer expression, it will always have the same value. she's committed. she said what she said and she means it.

consider this transducer program:

$=1$ = [abc]
$=1$ X $=1$

the result transducer recognizes the strings aXa, bXb, and cXc. matching. adorable. 🎀

⚠️ only acyclic transducers — that is, transducers with a finite set of string mappings — can be assigned to agreement variables. if it's not acyclic, she can't hold that promise, and we don't do broken promises here.

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

five flavors. all valid. pick your fighter. 🦋

🌸 Symbol sequence 🌸

a symbol sequence is a sequence of characters, multi-character symbols and character ranges, e.g. a-z \. <x>.

🌸 symbol range 🌸

(yes the heading is lowercase in the original, i'm keeping it, i don't make the rules)

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. buckle up, this is the long one, but every line matters:

  • 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's 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 if X is a TE and op is either * (Kleene's star operator), + (Kleene's plus operator), or ? (optionality operator).
  • op X is a TE if 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 if 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.) shoutout ✨
  • "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 a morpheme list from a file.
  • "<fname>" is a TE. the compiler reads a pre-compiled transducer from the file named fname. This

(okay so the original page literally ends that bullet mid-sentence with "This" and i am NOT inventing an ending for it. i report, i don't make things up. moving on bestie 💀)

🌸 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

(and that's where the original cuts off. the section just says "The command" and then the example starts. i'm leaving it exactly as she left it. 💀)

✨ EXAMPLE ✨

here's an example of a simple transducer program. assuming that the file "adj-stems" contains the two lines

easy
late
big

(yes, "the two lines", and then it lists three. the original says two, i'm telling you it says two, we all move on together.)

this transducer will correctly analyze the adjective forms easy, easier, easiest and late, later, and latest. ate. no crumbs. 🔥

ALPHABET = [a-zA-Z] y:i e:<> <ADJ>:<>

$R$ = y<=>i (<ADJ>:<> e)

$R2$ = e<=><> (<ADJ>:<> e)

$R$ = $R$ & $R2$

$Stems$ = "adj-stems"

$S$ = $Stems$ <ADJ> (<pos>:<>|<cmp>:{er}|<sup>:{est})

$S$ || $R$

✨ EXIT STATUS ✨

fst-compiler returns 0 unless some error occurs. that's it. zero means we're good, anything else means something went wrong and you should go read the error. 👑

✨ BUGS ✨

okay so there IS a known bug and it's giving "she's a little confused but she's got the spirit":

the compiler gets the operator precedence wrong in the case of two-level rules, and interprets the expression "ab c<=>d ef" as "a(b c<=>d (ef))".

💀 so therefore: always surround the left context of two-level rules with parenthesis: (ab) c<=>d (ef). just do it. it costs you two characters and saves you an afternoon of crying. 🫶

✨ SEE ALSO ✨

fst-mor, fst-infl, fst-infl2, fst-infl3, fst-print, fst-compact, fst-parse, fst-compare, fst-compact, fst-lowmem, fst-lattice, fst-train

(and yes, fst-compact is listed twice in the original. i am not editing her. she said it twice and she meant it twice. 💅)

✨ AUTHOR ✨

Helmut Schmid, Institute for Computational Linguistics, University of Stuttgart, Email: schmid@ims.uni-stuttgart.de. This software is available under the GNU Public License.

and that's the whole page, bestie!! 🎀 this little time capsule is dated December 2004, and it's page fst-compiler(1) from the fst-compiler manual. thank you for coming to my ted talk, go compile something gorgeous. 🦋✨💖

📦 where this page comes from