Operator Precedence

2004-02-18: There is an unfortunate mistake on p. 202 of the book in Table 3.31: Precedence of Opeators from High to Low. According to this table, the high-precedence crossproduct operator : outranks everything else, followed by the prefix operators such as ~ (complement) \ (term complement), and $ (contains) that are said to outrank suffix operators such as * (Kleene plus) and + (Kleene star) and other iteration operators. This is true only for the term complement operator \ but false for the other prefix operators, as illustrated by the examples below:

    \a*   is equivalent to     [\a]*    not equivalent to    \[a*]


    ~a*   is equivalent to    ~[a*]    not equivalent to    [~a]*
    $a^2  is equivalent to    $[a^2]   not equivalent to    [$a]^2
is equivalent to    $[a+]    not equivalent to    [$a]+

In the original book release of xfst (version 8.1.7), expressions such as \a:b are not accepted as valid. Because the high precedence crossproduct operator outranks the term complement, \a:b is equivalent to the illegal expression \[a:b]. Note that term complement operator can only be used to modify a regular language and is not applicable to a regular relations sucah as the pair a:b.

Starting with the 8.3.9 release of xfst, the term complement operator outranks the colon. Consequently, an expression such as \a:b is now legal and equivalent to [\a]:b designating the relation that maps any single character symbol other than a to b.

The correct operator precedence table for version 8.3.9 and later xfst versions is given below. It includes the substitution operator ` (see page 51 in the book) that was inadvertently left out of the original table and the precede < and follow operators that appear in the precedence table but are not discussed anywhere in the book.

    \ `                                  Term complement, Substitution
    :                                       High-precedence crossproduct operator
    + * ^ .1 .2 .u .l .i .r   Kleene plus and star, iteration, upper-lower, invert and reverse
    ~ $ $. $?                          Complement, symbol complement, containment
    /                                      Ignore
                                             Concatenation (no overt operator)
   >                                   Precede and follow
    | & -                                 Union, intersect, minus
    => -> (->) @-> etc.         Rule operators
    .x. .o.                            Crossproduct and compose

    Table 3.31: Precedence of Operators from High to Low.

The correct precedence table for xfst-8.1.7 on the book CD can be derived from the above table by exchanging the first two lines.

Last Modified:Wednesday, 18-Feb-2004 18:23:38 PST