FAQ: Complementing a Replace Rule Context

Q: I want to replace some regular-language A to some other regular language B as long as there is no regular-language C after A.

I was expecting to be able to do something like this:

A -> B || _ ?* ~C;

However, this does not do what I want.

A: No, it won't work like that. Two key points to remember:

  1. A rule of the form

    A -> B || L _ R ;

    is compiled as

    A -> || ?* L _ R ?* ;

    with the left and right context being extended out infinitely to the left and right, respectively. (You can block the infinite extension by overtly indicating the word boundaries with .#.)

  2. Remember that ~C is the complement of C, and if C does not include the empty language, then ~C will include the empty language. Thus ~C can match the empty string and so will match the empty language. Thus

    A -> B || _ ?* ~C

    will match with any right context. I.e. you basically have

    A -> B || ?* _ ?* ~C ?*

    where ~C includes the empty language, so the rule reduces to

    A -> B || ?* _ ?*

    and does not constrain the replacement at all.

    The following should perform the constraint that you want:

    A -> B || _ ~$[C] .#.

    I.e. the right context must not include C. Be sure to indicate the .#. or the automatic extension of the contexts with ?* will get you in trouble again.

Last Modified:Sunday, 07-Mar-2004 22:08:49 PST