Applied Computational Linguistics

XFST and FSA syntax - a comparison table

The following table lists xfst operators and their corresponding fsa operators. Blanks in the table normally indicate that the corresponding operation must be defined by more complex means. Further explanation about the meaning of the operators and the implementation of xfst operators in fsa can be found here.

XFST syntax	FSA Utilities syntax	Meaning
a	a	single symbol a
%* or ``*''	escape() or ''	escape literal symbol
abc	abc	multi-character symbol
?	?	any symbol
0 or [ ] or '' ''	[ ]	epsilon symbol - the empty string
{abcd}	[a,b,c,d]	single character brace
A*	A*	Kleene star
A+	A+	Kleene plus
A \| B	{A,B}	union
A & B	A & B	intersection
A - B	A - B	minus
\A	[~A] & ?	term complement
~A	~A	complement
A/B	ignore(A,B)	A ignoring B
A./.B	ignore(A,B) - {[B,?],[?,B]}	A ignoring internally B
$A	$A	containment
$.A	$A - ignore([A,A],?*)	one containment
$?A	{$A - ignore([A,A],?),? - $A}	maximum one containment
A B	[A,B]	concatenation
A^n		n-ary concatenation of A
A^{n,k}		n to k concatenations of A
A^ >n		more than n concatenations of A
A^<n		less than n concatenations of A
A.x.B	A x B	cross product
A.o.B	A o B	composition
(A)	A^	optionality
a:b	a:b	symbol pair
[ ]	( )	order control
R.P.Q	{$R , (domain(Q) - domain(R)) o Q}	upper-side priority union
R.p.Q	{$R , Q o (range(Q) - range(R))}	lower-side priority union
R.-u.Q	(domain(R) - domain(Q) ) o R	upper-side minus
R.-l.Q	R o (range(R) - range(Q))	lower-side minus
A<B	~$[B,A]	A before B
A>B	~$[A,B]	A after B
A.r	reverse(A)	reverese
R.u or R.1	domain(R)	upper language of the regular relation R
R.l or R.2	range(R)	lower language of the regular relation R
R.i	invert(R) or inverse(R)	regular relation inverse
.#.		boundary symbol
xfst restriction rules		restriction rules
xfst replace rules		replace rules
markup rules		markup rules
xfst precedence order	fsa precedence order	precedence order
advanced xfst	advanced fsa	advanced methods

Any Symbol - ?

A question mark (?) in an XFST regular expression stands for any symbol. In an XFST network, however, the question mark stands for any unknown symbol. In FSA the question mark always indicates any symbol (known or unknown).}

XFST restriction rules

XFST restriction rules do not have corresponding operators in FSA, therefore we only bring the list of xfst restriction rules syntax.

A=>L_R
A=>L1_R1,...,Ln_Rn

XFST replace rules

XFST replace rules can be divided into 4 groups:

Unconditional replace rules (one rule with no context).
Unconditional parallel replace rules (several rules with no context that are performed at the same time).
Conditional replace rules (one rule and one condition).
Conditional parallel replace rules (several rules and/or several contexts).

XFST replace rules do not have corresponding operators in FSA, therefore we only bring the list of xfst replace rules syntax.

-> (obligatory, upper to lower replacement)

A->B
A1->B1,...,An->Bn
A->B || L_R
A->B // L_R
A->B \\ L_R
A->B \/ L_R
A11->B11,...,A1n->B1n || L11_R11,...,L1m_R1m
A11->B11,...,A1n->B1n \\ L11_R11,...,L1m_R1m
A11->B11,...,A1n->B1n // L11_R11,...,L1m_R1m
A11->B11,...,A1n->B1n \/ L11_R11,...,L1m_R1m
A11->B11,...,A1n->B1n || L11_R11,...,L1m_R1m
,,
A21->B21,...,A2p->B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1->Bk1,...,Akr ->Bkr || Lk1_Rk1,...,Lks_Rks
A11->B11,...,A1n->B1n \\ L11_R11,...,L1m_R1m
,,
A21->B21,...,A2p->B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1->Bk1,...,Akr ->Bkr \\ Lk1_Rk1,...,Lks_Rks
A11->B11,...,A1n->B1n // L11_R11,...,L1m_R1m
,,
A21->B21,...,A2p->B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1->Bk1,...,Akr ->Bkr // Lk1_Rk1,...,Lks_Rks
A11->B11,...,A1n->B1n \/ L11_R11,...,L1m_R1m
,,
A21->B21,...,A2p->B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1->Bk1,...,Akr ->Bkr \/ Lk1_Rk1,...,Lks_Rks

(->) (optional, upper to lower replacement)

A(->)B
A1(->)B1,...,An(->)Bn
A(->)B || L_R
A(->)B // L_R
A(->)B \\ L_R
A(->)B \/ L_R
A11(->)B11,...,A1n(->)B1n || L11_R11,...,L1m_R1m
A11(->)B11,...,A1n(->)B1n \\ L11_R11,...,L1m_R1m
A11(->)B11,...,A1n(->)B1n // L11_R11,...,L1m_R1m
A11(->)B11,...,A1n(->)B1n \/ L11_R11,...,L1m_R1m
A11(->)B11,...,A1n(->)B1n || L11_R11,...,L1m_R1m
,,
A21(->)B21,...,A2p(->)B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1(->)Bk1,...,Akr (->)Bkr || Lk1_Rk1,...,Lks_Rks
A11(->)B11,...,A1n(->)B1n \\ L11_R11,...,L1m_R1m
,,
A21(->)B21,...,A2p(->)B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1(->)Bk1,...,Akr (->)Bkr \\ Lk1_Rk1,...,Lks_Rks
A11(->)B11,...,A1n(->)B1n // L11_R11,...,L1m_R1m
,,
A21(->)B21,...,A2p(->)B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1(->)Bk1,...,Akr (->)Bkr // Lk1_Rk1,...,Lks_Rks
A11(->)B11,...,A1n(->)B1n \/ L11_R11,...,L1m_R1m
,,
A21(->)B21,...,A2p(->)B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1(->)Bk1,...,Akr (->)Bkr \/ Lk1_Rk1,...,Lks_Rks

<- (obligatory, lower to upper replacement)

A<-B
A1<-B1,...,An<-Bn
A<-B || L_R
A<-B // L_R
A<-B \\ L_R
A<-B \/ L_R
A11<-B11,...,A1n<-B1n || L11_R11,...,L1m_R1m
A11<-B11,...,A1n<-B1n \\ L11_R11,...,L1m_R1m
A11<-B11,...,A1n<-B1n // L11_R11,...,L1m_R1m
A11<-B11,...,A1n<-B1n \/ L11_R11,...,L1m_R1m
A11<-B11,...,A1n<-B1n || L11_R11,...,L1m_R1m
,,
A21<-B21,...,A2p<-B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1<-Bk1,...,Akr <-Bkr || Lk1_Rk1,...,Lks_Rks
A11<-B11,...,A1n<-B1n \\ L11_R11,...,L1m_R1m
,,
A21<-B21,...,A2p<-B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1<-Bk1,...,Akr <-Bkr \\ Lk1_Rk1,...,Lks_Rks
A11<-B11,...,A1n<-B1n // L11_R11,...,L1m_R1m
,,
A21<-B21,...,A2p<-B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1<-Bk1,...,Akr <-Bkr // Lk1_Rk1,...,Lks_Rks
A11<-B11,...,A1n<-B1n \/ L11_R11,...,L1m_R1m
,,
A21<-B21,...,A2p<-B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1<-Bk1,...,Akr <-Bkr \/ Lk1_Rk1,...,Lks_Rks

(<-) (optional, lower to upper replacement)

A(<-)B
A1(<-)B1,...,An(<-)Bn
A(<-)B || L_R
A(<-)B // L_R
A(<-)B \\ L_R
A(<-)B \/ L_R
A11(<-)B11,...,A1n(<-)B1n || L11_R11,...,L1m_R1m
A11(<-)B11,...,A1n(<-)B1n \\ L11_R11,...,L1m_R1m
A11(<-)B11,...,A1n(<-)B1n // L11_R11,...,L1m_R1m
A11(<-)B11,...,A1n(<-)B1n \/ L11_R11,...,L1m_R1m
A11(<-)B11,...,A1n(<-)B1n || L11_R11,...,L1m_R1m
,,
A21(<-)B21,...,A2p(<-)B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<-)Bk1,...,Akr (<-)Bkr || Lk1_Rk1,...,Lks_Rks
A11(<-)B11,...,A1n(<-)B1n \\ L11_R11,...,L1m_R1m
,,
A21(<-)B21,...,A2p(<-)B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<-)Bk1,...,Akr (<-)Bkr \\ Lk1_Rk1,...,Lks_Rks
A11(<-)B11,...,A1n(<-)B1n // L11_R11,...,L1m_R1m
,,
A21(<-)B21,...,A2p(<-)B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<-)Bk1,...,Akr (<-)Bkr // Lk1_Rk1,...,Lks_Rks
A11(<-)B11,...,A1n(<-)B1n \/ L11_R11,...,L1m_R1m
,,
A21(<-)B21,...,A2p(<-)B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<-)Bk1,...,Akr (<-)Bkr \/ Lk1_Rk1,...,Lks_Rks

<-> (obligatory, upper to lower, lower to upper replacement)

A<->B
A1<->B1,...,An<->Bn
A<->B || L_R
A<->B // L_R
A<->B \\ L_R
A<->B \/ L_R
A11<->B11,...,A1n<->B1n || L11_R11,...,L1m_R1m
A11<->B11,...,A1n<->B1n \\ L11_R11,...,L1m_R1m
A11<->B11,...,A1n<->B1n // L11_R11,...,L1m_R1m
A11<->B11,...,A1n<->B1n \/ L11_R11,...,L1m_R1m
A11<->B11,...,A1n<->B1n || L11_R11,...,L1m_R1m
,,
A21<->B21,...,A2p<->B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1<->Bk1,...,Akr <->Bkr || Lk1_Rk1,...,Lks_Rks
A11<->B11,...,A1n<->B1n \\ L11_R11,...,L1m_R1m
,,
A21<->B21,...,A2p<->B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1<->Bk1,...,Akr <->Bkr \\ Lk1_Rk1,...,Lks_Rks
A11<->B11,...,A1n<->B1n // L11_R11,...,L1m_R1m
,,
A21<->B21,...,A2p<->B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1<->Bk1,...,Akr <->Bkr // Lk1_Rk1,...,Lks_Rks
A11<->B11,...,A1n<->B1n \/ L11_R11,...,L1m_R1m
,,
A21<->B21,...,A2p<->B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1<->Bk1,...,Akr <->Bkr \/ Lk1_Rk1,...,Lks_Rks

(<->) (optional, upper to lower, lower to upper replacement)

A(<->)B
A1(<->)B1,...,An(<->)Bn
A(<->)B || L_R
A(<->)B // L_R
A(<->)B \\ L_R
A(<->)B \/ L_R
A11(<->)B11,...,A1n(<->)B1n || L11_R11,...,L1m_R1m
A11(<->)B11,...,A1n(<->)B1n \\ L11_R11,...,L1m_R1m
A11(<->)B11,...,A1n(<->)B1n // L11_R11,...,L1m_R1m
A11(<->)B11,...,A1n(<->)B1n \/ L11_R11,...,L1m_R1m
A11(<->)B11,...,A1n(<->)B1n || L11_R11,...,L1m_R1m
,,
A21(<->)B21,...,A2p(<->)B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<->)Bk1,...,Akr (<->)Bkr || Lk1_Rk1,...,Lks_Rks
A11(<->)B11,...,A1n(<->)B1n \\ L11_R11,...,L1m_R1m
,,
A21(<->)B21,...,A2p(<->)B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<->)Bk1,...,Akr (<->)Bkr \\ Lk1_Rk1,...,Lks_Rks
A11(<->)B11,...,A1n(<->)B1n // L11_R11,...,L1m_R1m
,,
A21(<->)B21,...,A2p(<->)B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<->)Bk1,...,Akr (<->)Bkr // Lk1_Rk1,...,Lks_Rks
A11(<->)B11,...,A1n(<->)B1n \/ L11_R11,...,L1m_R1m
,,
A21(<->)B21,...,A2p(<->)B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1(<->)Bk1,...,Akr (<->)Bkr \/ Lk1_Rk1,...,Lks_Rks

@-> (obligatory, upper to lower, left to right, longest match replacement)

A@->B
A1@->B1,...,An@->Bn
A@->B || L_R
A@->B // L_R
A@->B \\ L_R
A@->B \/ L_R
A11@->B11,...,A1n@->B1n || L11_R11,...,L1m_R1m
A11@->B11,...,A1n@->B1n \\ L11_R11,...,L1m_R1m
A11@->B11,...,A1n@->B1n // L11_R11,...,L1m_R1m
A11@->B11,...,A1n@->B1n \/ L11_R11,...,L1m_R1m
A11@->B11,...,A1n@->B1n || L11_R11,...,L1m_R1m
,,
A21@->B21,...,A2p@->B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1@->Bk1,...,Akr @->Bkr || Lk1_Rk1,...,Lks_Rks
A11@->B11,...,A1n@->B1n \\ L11_R11,...,L1m_R1m
,,
A21@->B21,...,A2p@->B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1@->Bk1,...,Akr @->Bkr \\ Lk1_Rk1,...,Lks_Rks
A11@->B11,...,A1n@->B1n // L11_R11,...,L1m_R1m
,,
A21@->B21,...,A2p@->B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1@->Bk1,...,Akr @->Bkr // Lk1_Rk1,...,Lks_Rks
A11@->B11,...,A1n@->B1n \/ L11_R11,...,L1m_R1m
,,
A21@->B21,...,A2p@->B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1@->Bk1,...,Akr @->Bkr \/ Lk1_Rk1,...,Lks_Rks

@> (obligatory, upper to lower, left to right, shortest match replacement)

A@>B
A1@>B1,...,An@>Bn
A@>B || L_R
A@>B // L_R
A@>B \\ L_R
A@>B \/ L_R
A11@>B11,...,A1n@>B1n || L11_R11,...,L1m_R1m
A11@>B11,...,A1n@>B1n \\ L11_R11,...,L1m_R1m
A11@>B11,...,A1n@>B1n // L11_R11,...,L1m_R1m
A11@>B11,...,A1n@>B1n \/ L11_R11,...,L1m_R1m
A11@>B11,...,A1n@>B1n || L11_R11,...,L1m_R1m
,,
A21@>B21,...,A2p@>B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1@>Bk1,...,Akr @>Bkr || Lk1_Rk1,...,Lks_Rks
A11@>B11,...,A1n@>B1n \\ L11_R11,...,L1m_R1m
,,
A21@>B21,...,A2p@>B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1@>Bk1,...,Akr @>Bkr \\ Lk1_Rk1,...,Lks_Rks
A11@>B11,...,A1n@>B1n // L11_R11,...,L1m_R1m
,,
A21@>B21,...,A2p@>B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1@>Bk1,...,Akr @>Bkr // Lk1_Rk1,...,Lks_Rks
A11@>B11,...,A1n@>B1n \/ L11_R11,...,L1m_R1m
,,
A21@>B21,...,A2p@>B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1@>Bk1,...,Akr @>Bkr \/ Lk1_Rk1,...,Lks_Rks

->@ (obligatory, upper to lower, right to left, longest match replacement)

A->@B
A1->@B1,...,An->@Bn
A->@B || L_R
A->@B // L_R
A->@B \\ L_R
A->@B \/ L_R
A11->@B11,...,A1n->@B1n || L11_R11,...,L1m_R1m
A11->@B11,...,A1n->@B1n \\ L11_R11,...,L1m_R1m
A11->@B11,...,A1n->@B1n // L11_R11,...,L1m_R1m
A11->@B11,...,A1n->@B1n \/ L11_R11,...,L1m_R1m
A11->@B11,...,A1n->@B1n || L11_R11,...,L1m_R1m
,,
A21->@B21,...,A2p->@B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1->@Bk1,...,Akr ->@Bkr || Lk1_Rk1,...,Lks_Rks
A11->@B11,...,A1n->@B1n \\ L11_R11,...,L1m_R1m
,,
A21->@B21,...,A2p->@B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1->@Bk1,...,Akr ->@Bkr \\ Lk1_Rk1,...,Lks_Rks
A11->@B11,...,A1n->@B1n // L11_R11,...,L1m_R1m
,,
A21->@B21,...,A2p->@B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1->@Bk1,...,Akr ->@Bkr // Lk1_Rk1,...,Lks_Rks
A11->@B11,...,A1n->@B1n \/ L11_R11,...,L1m_R1m
,,
A21->@B21,...,A2p->@B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1->@Bk1,...,Akr ->@Bkr \/ Lk1_Rk1,...,Lks_Rks

>@ (obligatory, upper to lower, right to left, shortest match replacement)

A>@B
A1>@B1,...,An>@Bn
A>@B || L_R
A>@B // L_R
A>@B \\ L_R
A>@B \/ L_R
A11>@B11,...,A1n>@B1n || L11_R11,...,L1m_R1m
A11>@B11,...,A1n>@B1n \\ L11_R11,...,L1m_R1m
A11>@B11,...,A1n>@B1n // L11_R11,...,L1m_R1m
A11>@B11,...,A1n>@B1n \/ L11_R11,...,L1m_R1m
A11>@B11,...,A1n>@B1n || L11_R11,...,L1m_R1m
,,
A21>@B21,...,A2p>@B2p || L21_R21,...,L2q _R2q
,, ... ,,
Ak1>@Bk1,...,Akr >@Bkr || Lk1_Rk1,...,Lks_Rks
A11>@B11,...,A1n>@B1n \\ L11_R11,...,L1m_R1m
,,
A21>@B21,...,A2p>@B2p \\ L21_R21,...,L2q _R2q
,, ... ,,
Ak1>@Bk1,...,Akr >@Bkr \\ Lk1_Rk1,...,Lks_Rks
A11>@B11,...,A1n>@B1n // L11_R11,...,L1m_R1m
,,
A21>@B21,...,A2p>@B2p // L21_R21,...,L2q _R2q
,, ... ,,
Ak1>@Bk1,...,Akr >@Bkr // Lk1_Rk1,...,Lks_Rks
A11>@B11,...,A1n>@B1n \/ L11_R11,...,L1m_R1m
,,
A21>@B21,...,A2p>@B2p \/ L21_R21,...,L2q _R2q
,, ... ,,
Ak1>@Bk1,...,Akr >@Bkr \/ Lk1_Rk1,...,Lks_Rks

XFST markup rules

XFST markup rules do not have corresponding operators in FSA, therefore we only bring the list of xfst markup rules syntax.

A-> L...R
A@->L...R
A@> L...R
A->@L...R
A>@ L...R

XFST precedence order

The following list states the order of precedence of XFST operators. Operators of same precedence are executed from left to right, except the prefix operators (~ \ $ $? $.) that are executed from right to left. To enforce another order use angle brackets [ ]. The list begins with the operators of highest precedence, i.e. with the most tightly binding ones. Operators of same precedence are on the same line.

:\
~   \   $   $?   $.
+   *   ^   .1   .2   .u   .l    .i    .r
/
concatenation
>   <
|   &   -
=>   ->   (->)   <-   (<-)   <->   (<->)   @->   @>   ->@   >@
.x.   .o.

FSA precedence order

The following list states the order of precedence in FSA. The brackets () can always be used to express the desired grouping. The order of precedence of operators is as follows:

:   /\
..
+   *    ^
&   -
o    x    xx
!    #

Advanced methods

Both XFST and FSA have advanced methods that do no exist in the other toolbox. For xfst these techniques include Compile-Replace and Flag-Diacritics; for FSA these techniques include predicates and weighted networks.