User:Zzo38/Untitled 5

The program essentially consists of a set of rules and an input. Each rule has a "old" part, a "new" part, and a "add" part. Each of these parts, and the input, consists of a sequence of characters.

Rules

The set of rules (after all implied rules are added) must follow these criteria:

1. The old part of a rule cannot be an empty string.
2. The old parts of all of the rules must be different from each other.
3. The old part of a rule must be the same length as the new part of a rule.
4. An old part of a rule cannot be a prefix of the old part of a different rule.
5. If the old parts of all rules are exchanged with the new parts of those rules, the set of rules must remain valid.

Implied rules

The set of rules from the program will be augmented by adding the "implied" rules, if any are applicable.

An implied rule has an empty "add" part, and the "old" part equal to its "new" part.

You must add all of the rules with the "old" part whose first character that does not occur in the first character "old" part of any existing rules. And then, if there are rules with the "old" part with two characters where not all characters are used for the second character where the first character is the same, then add all of the ones with that same first character and the ununused second characters. And then, similarly also with the first two characters and unused third characters if they are three characters long, etc.

Syntax

For the purpose of this program, a "character" means a byte in the range 0x21 to 0xFF, and a "space" means 0x20.

A comment starts with a space and then anything else up to the next 0x0A; all comments are meaningless and are ignored.

A rule consists of three sequences of characters with spaces in between, being the "old" part, "new" part, and "add" part; and ends with 0x0A.

If a line that is not a comment has the wrong number of spaces, then it is an error.

Execution

The execution consists of turns. The output of one turn will be the input of the next turn. The input of the entire program will be the input of the first turn.

During each turn, begin with an empty start string and an empty end string.

Match the beginning of the input with the "old" part of rules; find the corresponding rule and append the "new" part to the start string and the "add" part to the end string. And then, continue with the part of the input starting after the match, so that it will start to match from there instead of from the beginning. Repeat this until you reach the end of the input.

The output is then the concatenation of the start string followed by the end string.

Backward variant

This variant adds a fourth part, which is the "unadd" part.

Each turn also begins with a empty deletion string. When a rule is executed, you must also append the "unadd" part to the deletion string, and the length of the deletion string is subtracted from the input length to figure out where to stop; you would stop before reading any input in the part past the length of the input string minus the length of the deletion string.

At the end of the turn, if the deletion string is not a suffix of the input string, then it is an error. (The length of the start string should now be equal to the length of the input string minus the length of the deletion string.)