#!/usr/bin/perl -w
# -*- mode:perl; fill-column:79; -*-

# Documentation
=pod

=head1 NAME

Cyclexa - regular-expression-like programming langugage

=head1 DESCRIPTION

=head2 About Cyclexa

Cyclexa is a regular-expression-like language designed for several
basic purposes:

=over 4

=item *

Cyclexa can be used in the places where regular expressions would otherwise be
used; as it is more powerful as a language, it also increases the number of
places in which regular expressions can be used. For instance, a Cyclexa
expression can be written to match only a section of a string with properly
nested parentheses: C<('^\(\)'$1|\($1\)|)>. This is impossible to write using
'regular' regular expressions and considerably more difficult in most
programming languages.

=item *

Cyclexa is also designed as a language for writing translators from one
language to another. In some cases, a single Cyclexa expression can completely
translate one language to another, although this is unusual. More commonly,
Cyclexa can be used to parse a string representing a program into a parse tree
which can be used as the basis of a compiler or interpreter.

=item *

Cyclexa also happens to be Turing-complete, and allow for input and output;
this makes it possible to use it as a programming language in its own right.

=back

=head2 Cyclexa Basics

A Cyclexa program consists of one I<expression>, which operates on an I<input
string>. Normally, the Cyclexa expression will be called from some other
programming language, in which case the input string will be provided by that
language. When a Cyclexa program runs standalone, the input string starts out
as a null string.

The expression consists of a sequence of I<commands>, which each have an
operation in the input string or on other commands in the expression. Commands
can be combined into a I<group> of commands by enclosing them in parentheses,
and commands that modify other commands generally come just after the command
or group they modify. (If a command modifies a command that modifies another
command, etc., it also modifies all commands the command it modifies
modifies. This is a pretty simple concept, actually, just hard to express using
reasonable grammar.)

One of the most important commands is the 'default' command, represented by any
character that has no other meaning. This command causes the character used to
represent it to be removed from the start of the input string. (It can do other
things as well, but this is its normal behaviour.) For instance, if the input
string is C<abc>, the expression C<abc> will remove all three characters from
the input string, leaving it empty. When the end of the expression is reached,
as in this example, the program is said to have I<succeeded>.

What if the input string is C<abd>? Then, the first two commands will remove
the C<a> and the C<b>, and the third command will try to remove a C<c> and find
there isn't one. This will cause the command to I<fail>, and in the example
given here, the entire program will fail. Whether the program succeeds or fails
is sometimes the only piece of information that an external program using
Cyclexa is interested in, and is equivalent to whether a 'regular' regular
expression matches or not. A fail can be prevented from causing the whole
program to fail by giving an alternative possibility, in which case the program
I<backtracks> and tries a different possibility.

For instance, the C<?> command modifies another command; it causes that command
to be executed, but if a subsequent command fails, the program will backtrack
to the point at which the C<?> command was executed and continue I<without>
executing the command that the C<?> command modified. If the expression is
C<ab?bba>, and the input string is C<abba>, then the C<a> command will delete
the C<a> in the input string, the first C<b> command will delete the first C<b>
in the input string (but the C<?> will remember that the command might not have
been run; this is known as adding a I<choicepoint>), the second C<b> command
will delete the second C<b> in the input string, and the third C<b> command
will fail. This failure causes the program to go back to the last choicepoint,
in this case at the C<?>, and all the information in the program will be
restored to the state it was previously in. This means that the input string
will again be C<bba>. This time, the first C<b> command in the program will be
ignored, and as a result the three remaining commands will delete the three
remaining characters in the input string, leaving the input string empty and
the program successful. (Note that a program can succeed without leaving the
input string empty.) For more information, see L</Backtracking> below.

=head2 Quoting Constructs

The default command is pretty important; one of the most common ways to remove
a character from the input string is to match it with the default command.
Therefore, there are several possibilities for I<quoting> a character to remove
its special meaning, causing it to become the default command rather than doing
whatever unusual thing it would have done normally.

To quote one character that isn't a letter or number, it can be preceded by a
backslash: C<\?a\\> is an expression that will remove C<?a\> from the input
string. This quoting technique is enough by itself, as letters and numbers
don't have any special meaning (and are guaranteed not to, even if a future
version of Cyclexa comes out). Note that a backslash can remove the special
meaning of another backslash, causing it to be a default command rather than
quoting the next character. (Backslash followed by a letter or number has a
special meaning, which will be explained later on.)

This technique can, however, be quite space-consuming, so another technique is
provided. If a string contains no braces, and it contains at least one
character that isn't a digit or comma, it can be quoted by placing it inside a
pair of braces; so if for some reason you wanted to match and remove the string
C<('^\(\)'$1|\($1\)|)> from the input, you could write the expression
C<{('^\(\)'$1|\($1\)|)}> to do that, which is substantially shorter and more
readable than C<\(\'\^\\\(\\\)\'\$1\|\\\(\$1\\\)\|\)>. (This second string is
what you'd have to write in many other regular-expression notations, maybe
without the backslashes before the apostrophes because apostrophes don't have a
special meaning in 'regular' regular expressions.) The no-brace condition means
that such quotations can't be nested, and the condition that at least one
character must be something other than a digit or comma is to prevent ambiguity
with a different construct involving braces.

The previous technique is provided as a method of quoting a string when you're
writing it inside your own Cyclexa expressions, but sometimes you want to
generate an expression automatically from inside an external program, or you've
written most of the expression beforehand but an external program needs to fill
in a bit (for instance, a string to match) itself. Although it wouldn't be too
hard to code the program to use one of the other two quoting mechanisms, a
third is provided to help in this situation, and also in situations where you
want to quote a long string containing braces. If I<identifier> is any sequence
of letters, digits, and underscores (identifiers can start with digits in
Cyclexa, and are case-sensitive), then anything between C<{{identifier{> and
the matching C<}identifier}}> is quoted. There can be anything at all between
these delimiters, including things that look like opening or closing
delimiters; anything between the first occurrence of the opening delimiter and
the last occurrence of the closing delimiter is quoted. (However, if something
that looks like the closing delimiter appears later in the program, for
instance inside {{id{}id}} quoting, it will be taken as the closing delimiter
rather than the real closing delimiter, so some care is needed when using more
than one of these quoting constructs in the same program.)

Backslash followed by a letter allows characters to be typed into the program
that might be hard to represent portably, or even characters that don't
exist. (Nonexistent characters can be used as a method of making sure that the
characters your program uses for its working don't appear anywhere in the input
string or user input; also, some of them have a special meaning if they appear
in output.) Backslash followed by a lowercase letter refers to a character that
could theoretically be in the input string, whilst backslash followed by an
uppercase letter refers to a nonexistent character. Here is the list of
backslash-letter characters:

    \a Alert character  (ASCII 7)       \A
    \b Backspace        (ASCII 8)       \B Starts a nestable output group
    \c Subtract 64 from next character  \C
    \d Delete character (ASCII 127)     \D Separates output strings
    \e Escape character (ASCII 27)      \E Ends a nestable output group
    \f Form feed        (ASCII 12)      \F
    \g                                  \G
    \h                                  \H
    \i                                  \I
    \j                                  \J
    \k                                  \K
    \l                                  \L
    \m                                  \M
    \n Newline          (ASCII 10)      \N
    \o Character expressed in octal     \O
    \p                                  \P
    \q Character expressed in decimal   \Q
    \r Carriage return  (ASCII 13)      \R
    \s                                  \S
    \t Horizontal tab   (ASCII 9)       \T
    \u                                  \U
    \v Vertical tab     (ASCII 11)      \V
    \w                                  \W
    \x Character expressed in hex       \X
    \y                                  \Y
    \z Null             (ASCII 0)       \Z

    (Combinations without an explanation are reserved for future expansion.)

The decimal, octal, and hex characters take all the characters that are digits
in the relevant base that are consecutively after the escape character, and
form them into a number that gives the ASCII character code of a character to
insert; for instance, C<\o33d>, C<\x1B@d>, C<\q27d>, and C<\ed> are all
equivalent, and represent ESC d. (The @ is a command-separation character that
separates the end of the hex string from the character after it; see the
L</Commands> section below.) This could also have been written C<\c[d>, because
the ASCII code of the [ character is 64 greater than that of ESC.

Some of the non-existent characters have a special effect on output. If any
C<\D> characters are present in the output, they cause more than one output
value to be returned; the output is split into multiple values at the C<\D>
characters. (Some external programs that might call a Cyclexa program can't
handle this sort of output, and neither can a standalone Cyclexa program; in
such cases, the C<\D> characters are represented as newlines.) Also, some
external languages allow for a more complicated structure than simply strings;
in the case where a nested structure is llowed, C<\B> and C<\E> can be used to
open and close nesting levels of the structure respectively, and if the
external language doesn't have such a feature, they're replaced by opening and
closing parentheses.

=head2 Commands

Here is a complete list of all the commands available in Cyclexa, and also some
other characters with a special meaning.

=over 4

=item The default command: I<any character without a meaning> or I<any quoted character>

This is the default command. Normally, it will remove one character from the
start of the input string, as long as that character is the same as the one
used to represent the default command, and fail if the character it tries to
remove isn't there. It can do other things as well under certain circumstances;
see L</Other Uses for the Default Command> below.

A sequence of characters in the input string that is removed as a result of
executing a command or expression is said to I<match> that command or
expression; therefore, the expression C<a> matches the input C<a>, and in
general the default command matches itself (at least when performing its usual
function).

=item Separating commands: the C<@> character

The at-sign character isn't a command in the proper sense; instead, it's a
separator between commands. Some commands are expressed with multiple
characters (for instance C<+?> and C<??>), and this leaves strings like C<+??>
ambiguous; as C<+> and C<?> are also commands, there are three possible
interpretations for this string. There are tie-breaker rules for a Cyclexa
interpreter to guess what is meant when such strings appear, but the C<@>
character can be used to make it clear where each command starts and ends; the
three possible interpretations of C<+??> would be expressed as C<+@??>,
C<+?@?>, and C<+@?@?>. (Two-character commands always take precedence over
one-character commands, so there is no need to worry about the apparent
ambiguity of C<??> or C<+?> in these examples.) C<@> isn't a command, so C<a?>
has the same meaning as C<a@?>, even though C<?> applies to the 'previous
command or group' (the previous command is the default command, here expressed
as C<a>, in each case).

It's possible to specify that inside a particular group, unquoted whitespace
characters (spaces, tabs, vertical tabs, linefeeds, carriage returns, and
formfeeds) have the same meaning as C<@> (which can improve an expression's
readability); otherwise, they have no special meaning and represent the default
command.

Despite the special behaviour of C<@>, it can be quoted just the same way as
any other character.

=item Optional commands: the C<?> command

The C<?> command modifies the previous command or group. When encountered, it
creates a choicepoint and then executes the group it modifies. If the
choicepoint is backtracked to (either if the group it modifies fails or if it's
the most recent choicepoint when L<backtracking|/Backtracking> happens), it
instead continues the program without executing the group it modifies.

Therefore, the meaning of C<?> is effectively 'do this if you can, but if you
can't, it doesn't matter'. For example, C<a(bcd)?e> will match C<ae> or
C<abcde>.

C<(group)?> is identical to C<(??(group)|)> and C<c?> is identical to
C<(??c|)>. (These equivalences sometimes become important when considering the
interaction between C<?> and C<:>.)

=item More optional commands: the C<??> command

The C<??> command is like the C<?> command, except that its preferences are
reversed; it modifies the previous command or group, causing it to be ommitted
and adding a choicepoint, and continuing with that command or group inserted if
the choicepoint is backtracked to.

For instance, C<aa??b??a> matches C<aa> in C<aa>, C<aa> in C<aaba>, and C<aba>
in C<aba>. (If C<?> was used rather than C<??>, the matches would be C<aa>,
C<aaba>, and C<aba> respectively.) The meaning of C<??> in English is 'do this
if you have to, but avoid it if you can.'

For the purpose of interaction with C<:>, C<(group)??> is identical to
C<(??|(group))> and C<c??> is identical to C<(??|c)>. (Note that the question
marks in the equivalences given aren't the C<??> command, but a group option;
see L</Groups> below.)

=item Looping commands: C<*>, C<*?>, C<+>, and C<+?>

The C<+> and C<+?> commands modify the previous command or group, causing it to
be repeated one or more times; the C<*> and C<*?> commands are the same, except
that they cause zero or more repetitions. The C<+> command causes the affected
group or command to be repeated until it fails, creating a choicepoint at each
repetition, and then continues as normal; when any of the choicepoints is
backtracked to, the resulting code continues with one repetition fewer than
before. C<+> fails if no repetitions at all can be done; C<*> is identical,
except that it succeeds (without creating choicepoints) if no repetitions at
all can be done (that is, when trying to repeat the group, the first repetition
fails). When repeatedly backtracked to, C<+> can go down to one repetition and
C<*> to no repetitions before the commands run out of choicepoints and can't be
backtracked to any more. In English, C<+> is 'repeat this as many times as
possible, and at least once', and C<*> is 'repeat this as many times as
possible, but it doesn't matter if you can't'.

C<+?> and C<*?> are like C<+> and C<*> with opposite repetition preferences;
C<*?> just creates a choicepoint and succeeds (without executing the command or
group it modifies), and if that choicepoint is backtracked to, executes the
command it modifies (failing if it fails) and recreates the choicepoint, trying
one more repetition each time it's backtracked to. C<+?> is identical, except
that the modified command or group is executed once (with the C<+?> failing if
the modified command or group fails) before the choicepoint is created. In
English, C<+?> is 'do this, and do it as many times more as necessary, but
don't do it if you don't have to', and C<*?> is 'do this as many times as you
need to, but no more'.

One major difference between the I<greedy> looping commands C<*> and C<+> and
the I<ungreedy> looping commands C<*?> and C<+?> is that if a command that
never fails is modified by a greedy looping command, an infinite loop is
caused; for instance, C<a*@*> is an infinite loop because C<*> is incapable of
failing unless it's backtracked to. On the other hand, an ungreedy looping
command doesn't cause an infinite loop in such a situation unless it's
backtracked to repeatedly; C<a*@*?b> doesn't necessarily cause an infinite loop
(for instance, it matches C<aab> without a problem), but still can do when
backtracking happens (for instance, it would infinite-loop if given the input
C<aac>, because the b would repeatedly backtrack to the C<*?>, which is capable
of generating an infinite number of choicepoints). Note also that C<a*?@*?b> is
an infinite loop when applies to C<aab>; the outside C<*?> will do nothing,
then the C<b> will backtrack, then the inside C<*?> will match zero C<a>s, then
the C<b> will backtrack again, then the inside C<*?> will match zero C<a>s
twice, then the C<b> will backtrack again, and so on; the expression will never
reach a point at which the C<a>s are removed, and so the C<b>s will never
succeed.

Here are equivalences of these commands in terms of C<|> and C<$> (where C<e>
represents a single command or a group), both to give extra examples of how
they work and to define the interaction with C<:>:

=over 4

=item *

C<e*> is equivalent to C<(??e$+|)>

=item *

C<e*?> is equivalent to C<(??|e$+)>

=item *

C<e+> is equivalent to C<(??e)(??$-$+|)>

=item *

C<e+?> is equivalent to C<(??e)(??|$-$+)>

=back

=item Multiple possibilities: the C<|> command

The C<|> command modifies the entire group that contains it (not the preceding
group or command, as is more normally the case). When a group is entered, a
choicepoint is created if it has a C<|> inside it, and then the portion of the
group before the first C<|> is executed (instead of the whole group, which
would happen if there wasn't a C<|>). If that portion of the group fails, or a
failure after that portion of the group causes backtracking to the created
choicepoint, then instead the bit between the first and second C<|> in the
group, or from the first C<|> in the group to the end if there was only one, is
executed (if there was a second C<|> in the group, a choicepoint is created
first). Another failure causes the next portion between C<|> to be executed,
and so on until the containing group runs out of portions, at which point there
will be no more choicepoints and backtracking will go back somewhere
else. (Note that the entire program will be treated as the containing group if
the C<|> command is outside any group.)

For example, C<abc|d+|e??f> could match C<abc>, C<dd>, or C<ef> (among other
possibilities). C<|> is roughly equivalent to the English 'do this, or this, or
this, or this...'.

=item Magic dollar C<$>

The 'magic dollar' command (which uses the same character as the recursion
command C<$> to represent it) succeeds if there is no data left in the input
string, or fails otherwise. (The input string must be completely empty for it
to succeed; see L</Other Uses for the Default Command> for information on the
sort of things other than input text that might have ended up there, causing it
not to be empty.)

The command is known as the 'magic dollar' because it's conceptually the same
as imagining that there's a special character, represented by the magic dollar,
at the end of the input string, which can only be matched by the magic dollar
itself.

To distinguish the magic dollar from recursion, the recursion is taken as the
meaning of a dollar whenever possible. (After all, you can't match a
default-command C<-> or number after the end of a string, and repeating a magic
dollar with C<+> or C<*> would just be an infinite loop at the end of the
string, which is probably not what you mean.) Likewise, C<$+?> is grouped as
C<$+@?>, not C<$@+?>. (The second command here, 'generate an infinite number of
choicepoints but only at the end of the input string', is possibly marginally
useful, but not nearly as useful as the first, 'recurse if you can'.) See the
section on L</Precedence> below.

=item Recursion: C<$number>, C<$*number>, C<$+>, and C<$->

The C<$> command must be followed by a group number, or C<+> (which refers to
the group the command itself is in) or C<-> (which refers to the last group
that is entirely before the command itself). When reached, it replaces itself
with a modified copy of the group it refers to; the modification simply changes
the numbers of the groups it contains to group numbers not used elsewhere in
the program (unless they are I<global> groups; see L</Groups> below), and the
numbers of each reference to a group being copied (likewise, unless they are
global references, defined in the next sentence) to refer to the group's new
number rather than its old one; a reference is a group number, or number
implied with C<+> or C<->, in a C<$>, C<:>, C<!>, C<\>, or C<=?> command. A
C<*> can be inserted between the dollar and the number to make this reference a
global one (if a number is used); otherwise, the reference is a global one if
and only if it refers to a global group.

This command implements I<recursion> in Cyclexa, an important concept that
makes it possible to create complicated control structures, and makes the
language more powerful than an ordinary regular expression; mathematically
speaking, it improves the computational class of Cyclexa from being a
finite-state machine to being a push-down automaton. (The C<:> command is also
required to make the language Turing-complete.) As an example, suppose your
input string is known to consist only of opening and closing parentheses, and
you want to know if they're correctly matched or not. This operation cannot be
done by an ordinary regular expression; however, in Cyclexa, it can be written
as C<(|\($+\)$+)$>. (Here, the last dollar is a 'magic dollar', not the
recursion command.) The expression can be read in English as 'A string of
parentheses is correctly matched if either it's empty, or it consists of a pair
of parentheses containing a matched string of parentheses followed by a matched
string of parentheses, and then ends'. Note that care is needed in writing a
recursive expression, to prevent it being an infinite loop; in this case, the
expression obviously isn't an infinite loop because there are two posibilities
for the repeated group, the first of which removes a group from the program and
the second of which removes two characters from the input.

Note that it is theoretically possible for two groups to have the same number;
if a C<$> command refers to a group with the same number as another group (even
using C<$+> or C<$->), then it is unspecified which of the groups with the same
number will be referred to, although it will be exactly one group.

=item Antitext: the C<^> and related commands

One problem with running a standalone Cyclexa program, or with a program that
needs to produce output that wasn't present in its input, is that the commands
mentioned so far can only remove information from the input string, and what is
needed is some method of putting information back so it can be matched
later. This can be used both as a method of storing information (although it is
far from perfect in this regard, and other methods like backslash-number need
to be combined with it to help make it into a reasonable information-storage
scheme), and to generate text usable in output.

The C<^> command modifies a command or group, and does something inside the
group which has the approximate affect of 'reversing' the behaviour of the
group, turning text into antitext and vice versa. For instance, C<(abcde)^> has
the effect of adding C<abcde> to the start of the input string, with the a
ending up first in the resulting string, whereas C<a^b^c^d^e^> would add
C<edcba> to the start of the input string, because the C<e^> is the last
command to run and add itself to the start of the input string.

The precise details of how this works are somewhat complicated and have been
moved to their own section; see L</Other Uses for the Default Command> below.

=item Doing it the same way: the C<:> command

The C<:> command modifies the previous command or group; it is followed by a
C<+>, C<->, number, or asterisk followed by a number, and references another
group (which group it references is determined the same way as with the C<$>
command used for recursion, except that C<:-> refers to the last group that is
entirely before the group or command it modifies (rather than the last group
entirely before the C<:> command, which would be the group it modifies in many
cases).

The C<:> command causes the group it modifies to execute, but in a limited
way. Whenever any group that contains C<|> commands is executed, then due to
the semantics of the C<|> command each portion of the group between C<|>
commands is executed in turn, proceeding to the next one each time a failure
happens in one section. However, a number is also recorded specifying which
portion of the group is currently being executed (when inside the containing
group) or which portion of the group succeeded (when after the containing
group); this number is recorded in each group that contains the group with the
C<|> commands (even indirectly), and in the group with the C<|> commands. (To
be precise, these numbers are associated with the number of the group, rather
than the group itself, so if multiple groups have the same number then each
group will add to the other's list of numbers.) Groups can contain more than
one of these numbers, in which case the order in which the numbers were
obtained is relevant. (The numbers don't affect the expression in any way
except when C<:> (or C<=*>) commands are used; think of them as being stored in
a special place that exists only for the benefit of C<:> and C<=*> commands.)
Note also that there is a group option that prevents these numbers being
generated; see L</Groups> below. Note also that those numbers are not generated
when directly or indirectly inside a group modified by C<:> itself. (They
I<are>, however, generated inside a group directly or indirectly modified by
C<=*>, unless it is also directly or indirectly modified by C<:> or a group
option is given to prevent their generation.)

When a command or group executes whilst being modified by a C<:> command, these
numbers become very important; the numbers generated during the execution of
the command or group are compared with the numbers that have accumulated in the
group referenced by the C<:> command, and anything that would cause the two
sequences of numbers to become different causes the expression to instantly
fail and backtrack at that point. For instance, C<(a|b|c)(d|e|f):-> will match
C<ad>, C<be>, or C<cf>, but nothing else; the option that's used in the second
group is forced by the C<:> command to be the same as the option that's used in
the first group.

The C<:> command and C<$> command (and the usual commands found in regular
expressions) together make Cyclexa Turing-complete. With just regular
expression commands and the C<$> command, Cyclexa is a push-down automaton;
this is the class of programming languages that can match a string if and only
if it consists of any number of C<a>s, followed by the same number of C<b>s
(one Cyclexa expression for this is C<(a$+?b)?$>). However, out of the commonly
used computational classes, Turing-completeness (the computational class that
most programming languages attain) is required to match a string if and only if
it consists of any number of C<a>s, followed by the same number of C<b>s,
followed by the same number of C<c>s; this operation cannot be done merely with
regular expression commands and C<$>, but with C<:> it becomes easy:
C<(a*)b*:-c*:-$>. (The last C<:> command refers back to the group C<(a*)>,
because it's the last group strictly before the implied group created by the
C<*> after the C<c>; C<:> and C<$> can't refer back to implied groups, only
groups that actually existed in the original program.) Looking at the
equivalence in terms of C<|> (which has to be done to determine for certain how
the C<:> command will work in a particular case), the C<*> command will
generate a 0 for each repetition it creates, followed by a 1; all three C<*>
commands do this, so for them all to generate the same sequence of numbers (as
C<:> guarantees), they all have to have the same nubmer of repetitions. (This
expression could be made more efficient using a cut, writing it as
C<(a*)!b*:-c*:-$>, to avoid some needless backtracking.)

=item Abbreviation commands: C<!?>, C<|?>, C<+*>, C<=+>, C<+^>, and C<^+>

Several commands exist only as abbreviations for more complicated expressions;
they act in exactly the same way as if the full expression was written out. In
the examples below, C<e> is used to represent any command or group.

=over 4

=item *

C<e!?> is equivalent to C<(??e!''|)>. C<!?> has approximately the meaning of
'succeed if and only if the previous group would fail'; it's equivalent to what
Perl calls a negative lookahead assertion.

=item *

C<|?> is equivalent to C<!''|>; it's like C<|>, except that the group before it
then represents a way for the containing group to fail rather than a way for
the containing group to succeed.

=item *

C<e+*> is equivalent to C<(??e|.)*>. It's most useful when C<e> contains an
C<=> sign but not an C<=^> command, in which case it is equivalent to the C</g>
modifier on 'regular' regular expressions; it causes the replacement specified
by the C<=> to take place at all possible places in the string, not just one.

=item *

Because C<+*> and C<=^> are commonly combined, C<=+> is provided as an
abbreviation for C<+*=^>.

=item *

C<e+^> is equivalent to C<(??e)$-:-^>; it corresponds to a positive lookahead
assertion in Perl, and expresses matching an expression and then undoing all
the effects of that match by regenerating it in antitext. (A negative lookahead
assertion would be C<e!?>.)

=item *

C<e^+> is equivalent to C<(??e)^$-:->; it corresponds to generating the
expression represented by e in antitext, and then removing that expression
again. This is mostly a way to run commands without them failing or having an
effect on the input string, for instance to change a group's recorded text for
the benefit of the C<\number> command or to produce output.

=back

=item Character classes: the C<'> notation

(A note for people more used to traditional regular expressions: traditionally
the C<[]> notation was used for character classes; this is the only case where
Cyclexa makes a different choice of notation. This is because the C<'> notation
is often more concise, and also causes one character less to have a special
meaning.)

A I<character class> starts at an unquoted C<'> inside an expression, and ends
either when the group that contains the C<'> ends, or at another C<'>. There is
one special case of a character class; if there are no commands or groups at
all inside the class, then it becomes a command that always fails (that is,
C<''> is a command that always fails, and so is C<'> at the end of a group).

Assuming that there is at least one command or group inside a character class,
then a virtual C<|> command is added between each command or group inside the
character class, and the class itself is enclosed in an anonymous group (see
L</Groups> below); for instance, C<'abc'> is equivalent to C<(??a|b|c)>. The
only difference between a virtual C<|> command and a C<|> command that wasn't
generated by a character class is that the scope of an C<=> command extends to
the C<|> commands on either side of it or to the ends of the group it's in, and
that these must be real C<|> commands, not virtual ones; likewise, the scope of
a virtual C<|> command goes as far as the ends of the character class, to the
next virtual or real C<|> command, or to a C<=> command, whichever is nearest,
whereas the scope of a real C<|> command extends past a C<=> command to the
nearest real C<|> command or the ends of the group it's in. When real and
virtual C<|> commands would be mixed in the same group, an extra anonymous
group is placed around each section between real C<|> commands that contains
virtual C<|> commands in order to make the interaction with C<:> clear.

If the first character of a character class is C<^>, then that character is
removed, and instead C<!?.> is placed immediately after the anonymous group
generated around the character class; this has the effect of 'negating' the
character class by succeeding if and only if the character class fails, and
then removing one character from the input. (See the section below for the
definition of C<.>.)

Each time the character class contains the C<-> character and that character
has a default command on each side of it, then the C<-> character will be
replaced by all characters which have an ASCII code greater than that of the
character to its left and less than that of the character to its right, in
ascending order by ASCII code. In the event that the character to the left of
the C<-> has a greater ASCII code than that of the character to its right, then
the C<-> character is replaced by all characters with an ASCII code greater
than that of the character to its left (in ascending order), followed by all
characters with an ASCII code less than that of the character to its right (in
ascending order). Therefore, C<'^e-g> and C<'h-d> match the same set of
characters. (However, they behave differently if antitexted, and interact
differently with C<:>.) The characters with which the C<-> is replaced with are
quoted if necessary to make sure that they are interpreted as default commands
and not as anything else.

=item Match any character: C<.>

The C<.> command is equivalent to a character class that contains every
possible character in ASCII code order (quoted if necessary so that they're all
the default command). Unlike ordinary regular expressions, C<.> will match any
character (even a newline).

As an example, consider the expression C<(.*)$.^@*:->. This expression first
removes all the input from the input string, and then places it back in reverse
order by antitexting it back one character at a time in the same order as it
was removed. (As a further example of C<^>, compare C<(.*)$.*@^:-> to this,
which places the characters back all at once, so they end up in the same order
as in the start and the statement has no effect as a standalone statement.)

=item Cutting away choicepoints: C<!>, C<!number>, and C<!*number>

The C<!> command may be followed by a group number (or an asterisk and a group
number); otherwise, the group number defaults to the group the C<!> command is
in. The C<!> command is a reference to that group (it's a global reference if
it refers to a global group, or if the form of the command using an asterisk is
used). It causes all choicepoints that were generated more recently than the
last time a group with the given number started to be executed to be removed
altogether (so that they can no longer be backtracked to); this command is
therefore a control-flow mechanism that allows the behaviour of backtracking to
be manipulated.

One common use of this command is to optimize an expression; suppose for
instance you want to succeed if and only if the input string consists of any
number of C<a>s followed by a C<b>. An expression that does this is C<a*b$>;
this expression will work, but it can be slow in some situations. (Imagine what
happens when you have lots of C<a>s in the input followed by something that
isn't a C<b>; the C<*> command will match all the C<a>s, then the C<b> will
backtrack, then the C<*> command will match all but one of the C<a>s, then the
C<b> will backtrack again, and so on.) To speed up this expression, it could be
written C<a*!b$>; the C<!> will remove all the choicepoints generated by the
C<*> command (remember that a group surrounds the entire program), which
doesn't affect the logic of the program (because it's known in advance that a
success is impossible if a failure happens in the C<b> or C<$> command) but
does speed it up.

Sometimes a cut does change the logic of a program; consider the program
C<a!b|c!d|>. This succeeds when given any input that starts with C<ab>, or with
C<cd>, or with a character other than C<a> or C<c>; however, input like C<ae>
will cause it to fail, because backtracking to the third (empty) option is
prevented by the cut.

=item Input: C<=*>

The C<=*> command modifies the preceding command or group. It interacts with
the user, asking them to make a decision between all the possible input strings
that would be matched exactly by the group it modifies. The way the input is
achieved depends on the contents of the group that the C<=*> command
modifies. In most cases, this is acheived by reading in characters from
standard input until something is reached that matches the group or command
modified by C<=*>, or until it becomes clear that there can be no match, in
which case no more characters are accepted; the user will have to backspace the
input to try further input. (If standard input is a noninteractive device like
a file, the input command instead just fails at that point if the characters
read so far don't constitute valid input according to the modified command or
group or pushed the character back into the input and succeeds if the
characters read do match the modified command or group; likewise, if an error
signal is input, the C<=*> command fails, and it also fails if end-of-file is
reached on the input and the characters input so far don't match the regular
expression.) In these cases, no prompt is displayed. There are, however,
several possibilities for the modified command/group where the method of input
is specified differently:

=over 4

=item .=*

This reads in one character from standard input, displaying no prompt except
possibly a cursor. If possible with the input device being used, the program
continues immediately after the character is input without waiting for a
newline; if that isn't possible, a line of input is read in and all but the
first character is discarded (this discards the newline at the end as
well). (With this and all other versions of the input commands, the input is
echoed to the screen if the input is from a keyboard or similar interactive
device.)

=item .*=*

This reads in one line from standard input, displaying no prompt except
possibly a cursor. The newline at the end of the line is read in too. (This is
handled specially, as the input string can't contain newlines except at the
end; if this behaviour isn't desirable, writing C<(.*)=*> or something else
that's slightly different than C<.*=*> will prevent this special handling being
used, but this will result in the program waiting for an end-of-file signal on
standard input before returning. Also note that C<.*@=*>, C<.@*=*>, and similar
variations involving @ or whitespace are considered identical to C<.*=*> for
this purpose.)

=item 'abc'=* (or any other set of default commands in the character class)

When standard input is a keyboard or similar interactive device, this puts up a
prompt listing all the possible options (the recommended form of this is C<
(a/b/c): >, retaining the space at the start and the end); then (regardless of
what device standard input is) it reads in characters from standard input until
one of the options given is input. The prompt isn't followed immediately by a
newline unless that's required by the output device being used; however, if the
prompt was shown, a newline is output immediately after the character in
question was input.

=item (abc|def|ghi)=* (with any number of options that are strings of default commands)

If standard input is a file or similar noninteractive device, this reads
characters as long as they are consistent with the modified group, as
usual. However, if it's an interactive device like a keyboard, the Cyclexa
interpreter places up a menu of the possible options, and uses an appropriate
method to input one of the options (which isn't specified here, and which may
vary from system to system and between different Cyclexa interpreters).

=back

The input is read in first, and then converted to a sequence of numbers via
which the modified command or string is guided (the same way as with the C<:>
command); one common way to obtain input is via antitexting the C<=*> command
(in which case the input is added to the input string), but it's also possible
to write code like C<y^'yn'=*> (which succeeds if the input is 'y' but fails if
the input is 'n') or even C<(one|two|three)=*^+(1|2|3)^:->.

=item Replacement: C<=> and C<=^>

First, a note: the syntax for replacements is never actually needed; it's an
abbreviation that could be entirely replaced by what it stands for. However, it
can considerably shorten some programs, and also makes the programs clearer and
more maintainable.

Each expression in Cyclexa has two other expressions associated with it; its
I<left expression> and I<right expression>. Whenever the expression contains no
C<=> signs, its left and right expressions are identical and equal to the
expression itself. It's actually the left expression that's evaluated when an
expression is evaluated outside a group modified by C<=^>, but when C<=> and
C<=^> aren't used this just appears identical to the expression itself being
evaluated.

C<=^> modifies the previous command or group; if C<l> is taken to represent
that command or group's left expression and C<r> is taken to represent its
right expression, it replaces that command or group with C<(??(??l)(??r)^:-)>;
the left expression of the entire C<=^>-modified expression is equal to the
expanded expression itself, as is its right expression. There are a few
replacements done on the right expression first; any magic dollars in it are
removed, and C<$> recursion commands in it change as well (see below). (In
other words, it replaces it with its left expression, followed by its right
expression antitexted and 'done the same way'; or colloquially and slightly
inaccurately (but closely enough to give a reasonable mental image and
understanding), it corresponds to 'replacing' the left expression with the
right expression in the input string.)

C<=> is the character used to cause the left expression and right expression of
an expression to be different from each other. In the simplest case, the left
expression of a portion of an expression between C<|> commands, or from C<|>
commands to the end of the group enclosing them, or an entire group that
doesn't contain C<|> commands, is the part of the portion to the left of an
C<=> sign the portion contains (or the whole thing if there isn't an C<=>
sign), and the right expression is the part of the portion to the right of the
C<=> sign the portion contains (or the whole thing if there isn't an C<=>
sign); so for instance C<(a|b=c|d)> is identical to C<(a|b|d)=(a|c|d)>, and the
'regular' regular expression substitution C<s/a/b/g> could be expressed in
Cyclexa as C<(a=b)=+!>. (Without the cut, the expression would, if backtracked
into, try again with some replacements not done; also, notice that this
expression succeeds even if no substitutions are done, due to the meaning of
C<=+>.) If this substitution made up the entire Cyclexa program (and if
Cyclexa's being used as a regular expression language to help out another
programming language, this is an entirely plausible use for a program), the cut
would not be needed because a failure after the end of the program would be
impossible, so it could be written C<(a=b)=+> instead; also, if a Cyclexa
program's left expression and right expression are different and the program
doesn't end in a 'magic dollar' or have C<^> as a group option for the group
representing the entire program, an implicit C<=+> command is placed modifying
the entire program, so the program could be written as just C<a=b>. (The /g
modifier therefore is the 'default' on Cyclexa programs that represent
substitutions.) If the program's left expression and right expression are
different and the program does end with a magic dollar or have C<^> as a group
option, instead an implicit C<=^> command is placed modifying the entire
program.

There are, however, several special cases. First, recursively including another
group using C<$> actually includes its left expression; however, when C<=^>
replaces the command or group it modifies with its left and right expressions,
it changes all instances of the recursive C<$> command there to another command
(which doesn't have a character to represent it and therefore can't be typed in
the input program) which includes a group's right expression rather than its
left expression. This is particularly useful when writing Cyclexa programs that
translate from one programming language to another (as it makes it easier to
write parsers; see the example at the end of this section).

Second, the C<=> sign has a different meaning if there is already an C<=> to
its left in the same group; it must be followed by a number, in decimal. All
the recursions with the C<$> command and groups which don't have C<??> as a
group option to the left of the C<=> sign are given an 'equals number' in the
order they appear. The presence of C<=> signs on the right of an C<=> causes
the right-expression of the group to be not what is to the right of the C<=>
sign, but instead C<(??left-expression)^+(+??right-of-equals-sign)>, and each
C<=equalsnumber> in the area to the right of the equals sign is replaced by
C<$groupnumber:groupnumber>, where I<groupnumber> is the group number of the
part of the copy of the left-expression in the right-expression which had the
correct equals number (if that part is a C<$> recursion rather than a group, a
group is created around it and given an unused group number). This means that
it's possible to write code like C<^'abc'|$+$+\~==2=1>; this might be an
interpreter for a simple concatenative reverse-Polish language with three
possible operands C<a>, C<b>, C<c>, and one operator C<~> which swaps its two
operands on the stack. (This isn't particularly useful; it's just an example.)
What's going on here from an informal point of view is quite simple; instead of
matching the right-hand-side in the same order as the left-hand-side, it's
possible to specify a different order in which to do this.

As an example for C<=> as a whole, consider the following code:

 ^*(((('0-9'+|\($2\)=$2)|
      $3(\*|\/)$4==1\ =3=2)|
     $2(\+|\-)$3==1\ =3=2)$)=^
   (($5|$6)\ ==1)=+

It converts arithmetic expressions in infix notation into minimum-length
equivalent arithmetic expressions in reverse-Polish notation, taking
associativity and precedence into account. When written like this, Cyclexa can
be seen as an unusual notation for BNF that also attaches an action to each
rule, in much the same way as compiler compilers like yacc, but with a much
more concise syntax.

=item Text-only backreference: C<\number>

The backslash isn't always used just for quoting or producing special
characters. When placed before a number, it has an entirely different meaning,
that of referencing the text that a previous group matched. (This operation may
be familiar from regular regular expressions.) Whenever a character is removed
from the input string for any reason (to be precise, a modified or unmodified
character: see L</Other Uses for the Default Command> below), it is stored in a
I<backslash memory> for that group's group number. Each group number has a
backslash memory that originally starts out empty, and removing a character
from the input string (normally, by using the default command) adds that
character to the end of the backslash memory for every group containing the
command that removed it. The backslash command itself is equivalent to a
sequence of default commands, one for each character in the backslash memory
for the referenced group (the group must be referenced by group number, and as
always it's a global reference if and only if it references a global group, or
to be precise, a group number which at least one global group has). So for
instance, C<(?1.*)\1> will match any string that consists of any sequence of
characters, followed by the same sequence again. (The C<?1> is setting the
group number of the group to 1; if it were the first group in the program, this
would not be necessary, but in both cases it is necessary to ensure no other
group is numbered 1 for this particular example to work reliably.) In this
case, C<(.*)$-:-> would have the same effect: this equivalence holds in most
simple cases, but fails in more complicated cases.

=item Modify backslash memory: C<=?number>

The C<=?number> command modifies a command or group, and executes it. However,
instead of the input string that most commands or groups act on, the command or
group will instead act on the backslash memory of the referenced group
number. (As usual, the reference is global if and only if it references a
global group, or a group with the same number.) The backslash memory of the
referenced group is read when the group is entered and written when the group
is exited; this means that operating on the memory does not alter it until the
end of the group, and that removing characters from the backslash memory inside
the group whose memory is being modified does not append those characters to
the end of the new temporary input string.

=back

=head2 Precedence

With all the commands available, many of which use the same character, there is
more than one way the sequence of characters that make up a Cyclexa expression
could be split into commands. In order to resolve this ambiguity, there is a
precedence order of commands. The way it works is that anywhere the C<!number>
command (the first command in precedence order) could be represented, it is;
then sequences of characters progressively further down the precedence list are
interpreted together as a single command, and so on until all the characters in
the expression have either been interpreted as commands, or the end of the list
is reached (in which case all characters not interpreted as commands or as
group options (see L</Groups> below) are treated as the default command). Note
that quoting has a higher precedence than any command; quoted characters can
never be interpreted as anything but default commands. Likewise, grouping
parentheses and group options have a higher precedence than anything but
quoting. Also, note that the C<@> character (and whitespace, if the correct
group options are given) can override this precedence order, except when it's
quoted. Some commands are given the same precedence below, because the relative
precedence order between those commands doesn't matter.

=over 4

=item 1

Quoting (C<{{id{}id}}> quoting is interpreted first, then quoting using
backslashes, then quoting using {})

=item 1

Groups and group options (see L</Groups> below)

=item 1

Precedence overrides using C<@>

=item 1

C<!number> and C<!*number>

=item 1

C<\number>

=item 1

C<!?> and C<|?>

=item 1

C<$+>, C<$->, and C<$number>

=item 1

C<+*>

=item 1

C<=*>

=item 1

C<=?>

=item 1

C<=^> and C<=+>

=item 1

C<??>

=item 1

C<+?> and C<*?>

=item 1

C<^+>

=item 1

C<+^>

=item 1

C<=number>, but only if there's an = earlier in the group

=item 1

All single-character commands: C<+>, C<*>, C<?>, C<^>, C<|>, C<!>, C<$>, C<.>,
and C<=>

=item 1

Character class notation

=item 1

C<^> and C<-> when used as special notation in a character class

=item 1

The default command

=back

=head2 Backtracking

=head2 Groups

Various options can be given to a group to change the way in which it behaves.
These options are represented as a string of characters at the start of the
group that set the options; if a character could be interpreted as a group
option, it is. (The only case in which a character could be interpreted as a
group option or a command is in a situation like C<(?1234)>, where the digits
C<234> could be interpreted as default commands or as group options; this can
be disambiguated with the C<@> character in the usual way, writing C<?12@34>,
for instance.) Note that the entire program is itself a group, and so can be
given group options the same way other groups can be given options.

Here are the various possibilities for group options, in the order in which
they must appear:

=over 4

=item Force initial match: C<^>

When given as a group option for the entire program, this prevents characters
from the input being discarded before the start of the program to attempt to
cause a match. (See L</Program Invocation> below.) It is reserved for use at
the start of a group that isn't the entire program, and should not be used in
this context. Note that the same character does the same thing in regular
regular expressions, and for much the same reasons.

=item Turn off group option: C<+^>, C<++^>, C<*^>

If a group has the group option C<+^>, it never acts as though a direct or
indirect containing group was modified by the C<+> option, even if some
containing group is. C<++^> turns off C<++> in the same way, and C<*^> turns
off C<*>.

=item Don't constrain character classes: C<++>

This group option causes the anonymous groups created by character classes
directly or indirectly inside the modified group (and therefore by the C<.>
command, which is equivalent to a character class) to be created with the C<+>
option; normally they aren't.

=item Don't constrain at all: C<+>

While directly or indirectly inside a group modified by +, groups containing
the C<|> command, or equivalent to groups containing the C<|> command, no
longer generate numbers used by the C<:> and C<=*> commands. This means that
they can match in an unconstrained way if modified by those commands, and that
matches in the group do not constrain those commands if they reference the
group or a group that directly or indirectly contains it.

=item Ignore whitespace: C<*>

Directly or indirectly inside a group with the C<*> option, all whitespace is
treated as being equivalent to the C<@> character, rather than the default
command, unless quoted. This is like the C</x> option in Perl, and is there for
the same reason: to allow proper indentation and whitespacing for readability.

=item Comment: C<**>

A group with the group option C<**>, and all groups directly or indirectly
inside it, are ignored. (Note that there isn't a group option C<**^> to turn
this off.) The code inside the group is still parsed (in particular, to find
out where it ends), but the group itself succeeds without doing anything when
executed. This option implies C<??>, and makes the other options on the group
redundant. (This also means that this cannot be given as a group option for the
entire program.)

=item Set group number: C<??>, C<?number>, and C<?*number>

Each group in Cyclexa has a number (this is its group number, as opposed to the
list of numbers generated for the benefit of the C<:> command); group numbers
must be non-negative integers. It is possible to set the group number of a
group with the C<?number> or C<?*number> commands; these set the group number
to the number given, and in the case of C<?*number>, the group also becomes a
global group (this is the only way to cause a group to become global, except
that if a group number of 0 is ever given explicitly, it also causes the group
to become global). It is permissible for more than one group to be given the
same number this way. Then, the group representing the entire program is given
the lowest unused group number available (normally 0), if it doesn't have one
already. (Incidentally, modifying the entire program with C<??> is not
permitted.) Then each group that doesn't already have a number and isn't
modified with C<??> is considered in turn, starting with the group with the
leftmost opening parenthesis, then the group with the next leftmost opening
parenthesis, and so on; each of those groups is given the lowest non-negative
number that's unused and higher than the number that the previous such group
was given (and the first such group is given the lowest unused non-negative
number higher than the number for the entire program). Finally, each group with
C<??> is given some unused number.

In addition, groups modified with C<??> don't produce the data used by the
C<\number> command. (This data would be useless anyway, as there would be no
way to reliably reference the group because its number would be unknown.)

=back

=head2 Other Uses for the Default Command

Antitext is a complicated feature of Cyclexa that is important to the language,
but non-trivial to describe or to implement. Technically speaking, it works by
using advanced features of the default command, as well as the behaviour of the
C<^> command.

The implementation works by assigning an extra piece of information to each
character in the input string. This is an abstract property, but it helps to
visualise what's going on if it's thought of as colour (and Cyclexa debuggers
conected to a colour screen could quite possibly colour the input string to
show how the colours change during the execution of a program).

To start with, all the characters in the input string are I<unmodified> ('red')
characters, and the I<cursor> is at the start of the string, pointing to the
right. (The cursor keeps track of where the default command operates.) When the
cursor is pointing to an unmodified character, the default command will remove
that character if the character representing the default command is the same as
the unmodified character, and fail otherwise. (This is the only behaviour of
the default command that is used when no antitext is present in an expression.)

The C<^> command does something both before and after the group or command it
modifies. (This is, of course, unless the group or command it modifies somehow
manages to fail, in which case the execution backtracks to before the C<^>
command was called; as you'll see later in this section, some common failure
reasons no longer apply inside an antitext group.) Before the group or command,
it reverses the direction of the cursor (so it's pointing to its left, rather
than its right, unless its direction has been reversed earlier), and then
inserts an I<antitext delimiter> (a nonexistent character that can't be
expressed any other way in Cyclexa) immediately in front of the cursor.

When a default command is executed and the cursor is pointing to an antitext
delimiter or to an I<added> ('blue') character, the character representing the
default command is added to the input string just in front of the cursor
(leaving the cursor in the same place and pointing in the same direction),
becoming an added character. For instance, using C<E<gt>> to represent the
cursor, and C<|> to represent an antitext delimiter, doing C<(abcde)^> on an
empty input string causes the state of the input string to be C<|abcdeE<lt>>
just after the C<e> default command is executed.

When the group or command modified by the C<^> finishes executing, the cursor
moves forwards to the next antitext delimiter in front of it, changing the
colour of each character in the input string it goes past until it reaches the
delimiter; added ('blue') characters change to I<modified> ('magenta')
characters; unmodified ('red') and modified ('magenta') characters change to
I<true antitext> ('green') characters, and true antitext ('green') characters
change to unmodified ('red') characters. Modified characters act in almost an
identical way to unmodified characters; they are removed from the input string
by the default command, or cause the default command to fail if it doesn't
match in exactly the same way unmodified characters do. (In fact, the only
difference between modified and unmodified characters is that they can cause
different output from a program in some circumstances.) True antitext
characters likewise act exactly like added characters, causing added characters
to be inserted into the input string when the default command is run with the
cursor pointing at a true antitext character. There is one important
difference, though; if at any point in the execution of the program, a true
antitext character and a modified or unmodified character are next to each
other in the input string, with nothing in between (not even the cursor or an
antitext delimiter), and they are the same character apart from their colour,
they immediately cancel each other out and are both removed from the input
string. After the cursor has moved to an antitext delimiter at the end of the
execution of a C<^> command, it removes the antitext delimiter and changes
direction again (and so ends up pointing back the same way it was before the
C<^> command was executed).

=head2 Program Invocation

When a Cyclexa interpreter starts or is called by another programming language,
it will be given a Cyclexa program and possibly an input string. If an input
string isn't given, it defaults to the null string.

Before the program is evaluated, some changes are made to it first. If C<^>
wasn't given as a group option for the group representing the entire program,
C<.*?> is prepended to the program. (This mirrors the behaviour of 'regular'
regular expressions, which don't have to match at the start of the string
unless C<^> was used. ) Then, if the expression's left expression and right
expression are different, a C<=+> group is placed around it (or C<=^> group if
C<^> was given as a group option to the entire program or the program ends with
a 'magic dollar', or both).

=cut

# Line to help out syntax highlighters that were confused by the documentation:
# '#"#)#}

# Imports and options
use strict; # to help prevent typos
use Fatal qw(open close); # nothing better to do on an error

# Remove all the @ signs from a string.
sub deat($)
{
    local $_ = shift;
    s/\@//;
    $_;
}

# Find the lowest number above the first arg that isn't a key in the
# second arg (which is a hash). The first arg must be an integer.
# The name stands for 'unique group number'.
sub ugn($%)
{
    local $_ = shift;
    my %g = (@_);
    $_++ while exists($g{$_});
    $_;
}

# Change Cyclexa expressions into a 'normalised' form which is easy to
# parse and process. Return the normalised version.
sub cxa_normalise($)
{
    # Read the arguments
    local $_ = shift;

    #####
    # The first thing to do is to resolve quoting constructs. This is
    # because they aren't affected by context and they aren't affected
    # by quoting constructs other than backslashes, but they are
    # capable of affecting anything else in the program.

    # {{a{...}a}} quoting. This matches the first opening delimiter to
    # the last closing delimiter, quotemetaing the characters in
    # between; so if there's only one of these constructs in a
    # program, it's guaranteed to work no matter what is inside.
    # Don't check for preceding backslashes, as the code will be wrong
    # both ways round.
    while(/\{\{([0-9a-zA-Z_])\{/)
    {
	s/\{\{([0-9a-zA-Z_])\{(.*)\}\1\}\}/quotemeta($2)/se
	    ;#or do{die "Unmatched {{$1{ found in program.";};
    }

    # {abc} quoting. This quotemetas the contents as long as there are
    # no braces there, and there is at least one character that isn't
    # a digit or comma.
    s/(?<!\\)(?<!\\c)((?:\\\\|\\c.)*)\{([^\{\}]*[^\{\}0-9,][^\{\}]*)\}/$1.quotemeta($2)/gse;

    # \c. quoting. Subtract 64 from the third character's char code.
    # The line is written twice to deal with consecutive \c quotations.
    s/(?<!\\)(?<!\\c)((?:\\\\)*)\\c(.)/$1.quotemeta(chr(ord($2)-64))/gse;
    s/(?<!\\)(?<!\\c)((?:\\\\)*)\\c(.)/$1.quotemeta(chr(ord($2)-64))/gse;
    # Note that from now on \c no longer has to be given as an exception
    # at the start of a regexp match.

    # \o (octal), \q (decimal), \x (hex). We have to be careful not to
    # leave nulls in the output sring, here, because many programs
    # have problems with them, instead leaving \z.
    s/(?<!\\)((?:\\\\)*)\\[oqx]0+/\\z/gs;
    s/(?<!\\)((?:\\\\)*)\\o([0-7]+)/$1.quotemeta(chr(oct($2)))/gse;
    s/(?<!\\)((?:\\\\)*)\\q([0-9]+)/$1.quotemeta(chr($2))/gse;
    s/(?<!\\)((?:\\\\)*)\\x([0-9a-fA-F]+)/$1.quotemeta(chr(hex($2)))/gse;

    #####
    # Next, fully @-separate all tokens. This makes it considerably
    # easier to write regexps to process Cyclexa later due to its
    # strange precedence rules. Care needs to be taken not to change
    # group options this way; so we first change group options to have
    # @@@ between each character and before the entire set (after
    # reducing multiple @s to a single @ in the original program),
    # with a single @ after the set, and remove all @@@s in the
    # program afterwards.  Existing @s in the program are changed to
    # @@; and an @ is added between each existing token. The
    # precedence rules then eliminate @ signs from the program until
    # there are @ signs only in the correct places.
    my @precedence=('!0','!*0',"\\0",'!?','|?','$+','$-','$0','+*',
		    '=?0','=*','=^','=+','??','+?','*?','^+','+^');
    # \@ will cause so many problems in the following code that it's
    # changed to \c.
    s/(?<!\\)((?:\\\\)*)\\\@/$1\\c/gs;
    # Multiple @s to one @
    s/(?<!\\)((?:\\\\)*)\@\@/$1\@/g while m/(?<!\\)((?:\\\\)*)\@\@/;
    # The entire program is a group too! Enclose it in parens, and leave it
    # that way until the end of normalisation.
    $_="($_)";
    # Separate group options with @@@
    s=(?<!\\)((?:\\\\)*)(\([+^*]*(?:\?(?:\*?[0-9]+|\?))?)=$1.join('@@@',split(//,$2)).'@'=gse;
    # Change single @s to double @s
    s/(?<!\@)\@(?!\@)/\@\@/gs;
    # Add @s between every token in the program (note that \0 is two
    # tokens at this stage because operator precedence hasn't been considered
    # yet)
    s/(?<!\@)(?<!\\)((?:\\\\)*)([^@])/$1\@$2/gs while m/(?<!\@)(?<!\\)((?:\\\\)*)([^@])/s;
    s/(?<!\\)\\([0-9])/\\\@$1/gs;
    # Eliminate @s to cover operator precedence
    for my $ct (@precedence)
    {
	if($ct =~ /0$/)
	{
	    my $cr="\\\@\\".join "\\\@\\",split(//,$ct);
	    $cr =~ s/\\0/([0-9]\\\@)+/;
	    $ct =~ s/0//;
	    eval "s/$cr/\"\\\@".quotemeta($ct)."\".deat(\$1).\"\\\@\"/gse";
	}
	else
	{
	    my $s="\@".substr($ct,0,1)."\@".substr($ct,1,1)."\@";
	    my $t="\@".$ct."\@";
	    $_=join $t,split(quotemeta($s));
	}
    }
    # Eliminate @@@, squeeze @@ in the string
    s/\@\@\@//gs;
    s/\@\@/\@/gs;
    undef @precedence;
    # From here, we need not fear commands being backslashed, as long
    # as they're at least two chars long and don't contain an @ sign.
    # Even if that condition doesn't hold, it's only necessary to
    # check for the presence or absence of a backlash, rather than an
    # odd/even number of them.

    #####
    # Every group needs a number.

    # Check what numbers exist currently.
    my %groupnumbers;
    {
	local $^W=0; # there is an expected warning here
	%groupnumbers =
	    map {$_ => 1} (m/(?<!\\)\([+^*]*\?(?:\*?([0-9]+)|\?)/g);
	delete $groupnumbers{undef};
	delete $groupnumbers{''};
    }

    print "Groups used: ", join(",",keys %groupnumbers), "\n";

    # An explicit ?0 causes a group to become global.
    s/\?0\@/?*0\@/g;

    # Assign group numbers to groups which don't already have them.
    # First for consistency we add a @ at the start of the program
    # if there isn't one already.
    /^\@/ or $_='@'.$_;
    my $lgu=0;
    s/\G/'?'.($lgu=ugn($lgu,%groupnumbers),$groupnumbers{$lgu}=1,$lgu)/e
	while(scalar(/\@\((?>[+^*]*)(?!\?)/g));

    # Groups explicitly modified with ?? change last of all.
    s/\G/$lgu=ugn(0,%groupnumbers),$groupnumbers{$lgu}=1,$lgu/e
	while(scalar(/\@\((?>[+^*]*)\?\?(?![0-9])/g));
    s/\?(\?[0-9]+)/$1/g;

    #####
    # Return the normalised version. \c will be changed back into
    # \@ so that the resulting program is a genuine Cyclexa program
    # (this might quite possibly be undone at the next step!), and
    # likewise the parens are removed from around the program.
    s/\\c/\\\@/;
    s/^\@?\(//;
    s/\)\@?$//;
    $_;
}

# Read in the program (argument [0])
$/=undef;
open INFILE, $ARGV[0];
my $program = <INFILE>;
close INFILE;

# Read in the input, if available
$_="";
if($#ARGV == 1)
{
    open INFILE, $ARGV[1];
    $_ = <INFILE>;
    close INFILE;
}

# When reading from a file, a final newline is removed unless written
# as \n.
$program =~ s/\n$//;

print cxa_normalise($program),"\n";