fst-0.10.0.0: FST/FSTStudio.hs

{-# LANGUAGE DoAndIfThenElse, FlexibleContexts, GeneralizedNewtypeDeriving #-}

{- |
fstStudio takes a program consisting of regular relations that denotes
the relation between two regular languages and constructs a
transducer. If a regular expression, not a relation, is given, then it
is interpreted as the identity relation. The syntax is very similar to
Xerox's finite state transducer syntax with two fundamental
differences: a distinction is made between functions (definitions) and
strings, and fststudio allows functional definitions.

[@\"a\"@] A symbol. Example: @[\"b\"]@ denotes the language @{\"b\"}@.

[@a@] A variable. A symbol without quotes is a variable.

[@\"a\":\"b\"@] Describes a relation between the symbol @a@ and @b@.
This relation is ordered and @a@ is said to be a part of the /upper
language/ and @b@ is said to be part of the /lower language/.
Example: @[\"a\":\"b\"]@ denotes the relation @{(\"a\",\"b\")}@.

[@0@] Epsilon symbol. The epsilon symbol denotes the string with no
symbols.  Example: @[0]@ denotes the language @{\"\"}@.

[@?@] All symbol. The all symbol denotes the union of all symbols in
the alphabet. Example: @[?]@ and an alphabet @{a,b,c}@ denotes the
language @{\"a\",\"b\",\"c\"}@.

[@\"\"@] quotes cancel every special meaning of the symbols. Example:
@[\"? 0\"]@ denotes the language @{\"? 0\"}@.

[@\[A\]@] brackets are used to change the precedence of a regular
relation.

[@(A)@] parenthesis expresses optionality, and has the same meaning as
@[A|0]@.

[@A B@] Concatenation of the expressions or relations A and
B. Example: @[[a b] [c d]]@ denotes the language @{\"ac\", \"ad\", \"bc\",
\"bd\"}@

[@A^n@] Concatenation of @A@ /n/ times.  @A^0@ is defined as the empty
string. Example: @[a]^3@ describes the language @{\"aaa\"}@.

[@A|B@] Union of the languages or relations @A@ and @B@. Example: @[a|b]@
describes the language @{\"a\",\"b\"}@.

[@A & B@] Intersection of the languages @A@ and @B@.  Example: @[a b]
& [a]@ describes the language @{\"a\"}@.

[@A - B@] Minus of the languages @A@ and @B@, and has the same meaning as
@[A & B]@.  Example: @[a b] - [a]@ describes the language @{\"b\"}@.

[@~A@] Describes the complement of an expression, and has the same
meaning as @[?* - A]@.  Note that complement is always defined over
an alphabet. The expression @[A]@ is only unambiguous with respect to
an alphabet. Example: @[a]@ denotes the language that doesn't contain
the string @\"a\"@. If the alphabet is @{\"a\",\"b\"}@ then @[a]@
denotes the language @{\"\",\"b\",\"aa\",\"ba\",...}@.

[@A+@] Repetition (Kleenes plus).  A concatenated with itself an
arbitrary number of times, including zero times. Example: @[a]+@ denotes
the infinite language @{\"a\",\"aa\",\"aaa\",...}@

[@A*@] Kleene’s star: @[A+ | 0]@.  Example: @[a]*@ denotes the infinite
language @{\"\",\"a\",\"aa\",...}@

[@$A@] Containment.  The set of strings where @A@ appear at least once
as a substring. Containment is the same thing as @[?* A ?*]@.

[@A .x. B@] Cross product of the languages @A@ and @B@.  Example: @[[a b]
.x. c]@ describes the relations @{(\"a\",\"c\"), (\"b\",\"c\")}@.

[@A .o. B@] Composition of the relations @A@ and @B@.  Example: @[a:b c:d]
.o. [d:e]@ describes the relation @{(\"c\",\"e\")}@.

The precedence of the operators is as follows, where 4 is the highest
precedence:

  1. @.x.@ @.o.@

  2. @&@ @-@

  3. /Concatenation/

  4. @~@ @^@ @*@ @+@ @$@

A file containing a program must end with @.fst@, and an input file
mustend with @.dat@.  A program is a collection of functions defining
regular relations. A function with zero arguments is called a
definition or a macro.  A definition, or a macro, can for example look
like this:

> <digits> ::= "1" | "2" | "3" | "4" | "5" |
>              "6" | "7" | "8" | "9" | "0" ;

and a function can look like this:

> <swap,a,b> ::= b a ;

Note that strings are marked with quotes, and variables have no
quotes. Every program must contain a @\<main\>@ definition (a program
without one will result in a parse error).

> <main> ::= ... ;

The alphabet of a program is the symbols in the regular relation
defined in the program.

/Example program/

> <nickel>  ::= ["n" .x. "c"^5];
> <dime>    ::= ["d" .x. "c"^10];
> <quarter> ::= ["q" .x. "c"^25];
> <cent>    ::= ["c" .x. "c"];
> <money>   ::= [ <nickel> | <dime> | <quarter> | <cent>]*;
> <drink>   ::= ["c"^65 .x. "PLONK"];
> <main>    ::= [ <money> .o. <drink> ];

/Batch mode/

Usage: @fst FILE [Options]@.  FILE must end with @.fst@, which defines
an FstStudio program, or @.net@, which defines a saved transducer. If
no options are given, then input is taken from standard input, the
transducer is applied down, and the output, if any, is produced on
standard output.

[@-u@] Apply the transducer up

[@-d@] Apply the transducer down

[@-i FILE@] Take input from FILE

[@-o FILE@] Write output to FILE

/Interactive mode - list of commands/

[@r REG@] Read a regular relation from standard input. If a regular
expression is typed, then it is interpreted as the identity relation.

[@b@] Build an epsilon-free, deterministic, minimal transducer from a
loaded/typed regular relation.

[@bn@] Build an epsilon-free, possibly non-deterministic, non-minimal
transducer from a load/typed regular relation.

[@m@] Minimize a built transducer.

[@det@] Determinize a built transducer.

[@s FILE@] Save to @FILE@. If @FILE@ ends with @.net@, then the built
transducer is saved. Any other suffix saves the produced output in the
system to @FILE@, if any.

[@l FILE@] Load from @FILE@. @FILE@ must end with @.fst@, @.net@ or
@.dat@. If @FILE@ ends with @.fst@, then a FstStudio program is loaded
into FstStudio. If @FILE@ ends with @.net@, then a transducer is loaded
into FstStudio. If @FILE@ ends with @.dat@, then input is loaded into
FstStudio.

[@l a | b@] Load and union two transducers. a and b must either be a
file ending with @.net@ or the symbol @*@, which refers to the interior
transducer. The produced transducer is possibly non-deterministic and
non-minimal.

[@l a b@] Load and concatenate two transducers. a and b must either be
ale ending with @.net@ or the symbol @*@, which refers to the interior
transducer. The produced transducer is possibly non-deterministicand
non-minimal.

[@l a*@] Load and apply Kleene’s star on a transducer. a must either
be a file ending with @.net@ or the symbol @*@, which refers to the
interior transducer. The produced transducer is possibly
non-deterministicand non-minimal.

[@l a .o. b@] Load and compose two transducers. a and b must either be
a file ending with @.net@ or the symbol @*@, which refers to the
interior transducer. The produced transducer is possibly
non-deterministic andnon-minimal.

[@vt@] View loaded/built transducer.

[@vr@] View loaded/typed regular relation.

[@vi@] View loaded input.

[@vo@] View produced output.

[@d@] Apply transducer down with loaded input.

[@u@] Apply transducer up with loaded input.

[@d SYMBOLS@] Apply tranducer down with @SYMBOLS@.

[@u SYMBOLS@] Apply transducer up with @SYMBOLS@.

[@c@] Clear memory.

[@h@] List commands.

[@q@] End session.

-}
module FST.FSTStudio where

-- This is a dummy module for the sake of documenation