Marking certains parts of a text should not involve storing hundreds of small strings. This is why the Tagging Engine uses a specially formatted list of tuples to return the results:

Tag List

A tag list is a list of tuples marking certain slices of a text. The tuples always have the format

(object, left_index, right_index, sublist)

with the meaning: object contains information about the slice [left_index:right_index] in some text. The sublist is either another taglist created by recursively invoking the Tagging Engine or None.

Tag Table

To create such taglists, you have to define a Tag Table and let the Tagging Engine use it to mark the text. Tag Tables are really just standard Python tuples containing other tuples in a specific format:

tag_table = (('lowercase',AllIn,a2z,+1,+2),
	     ('upper',AllIn,A2Z,+1),
	     (None,AllIn,white+newline,+1),
	     (None,AllNotIn,alpha+white+newline,+1),
	     (None,EOF,Here,-4)) # EOF 

The tuples contained in the table use a very simple format:

(tagobj, command+flags, command_argument
	      		[,jump_no_match] [,jump_match=+1])
	    

The Tagging Engine reads the Tag Table starting at the top entry. While performing the command actions (see below for details) it moves a read-head over the characters of the text. The engine stops when a command fails to match and no alternative is given or when it reaches a non-existing entry, e.g. by jumping beyond the end of the table.

Tag Table entries are processed as follows:

If the command matched, say the slice text[l:r], the default action is to append (tagobj,l,r,sublist) to the taglist (this behaviour can be modified by using special flags; if you use None as tagobj, no tuple is appended) and to continue matching with the table entry that is reached by adding jump_match to the current position (think of them as relative jump offsets). The head position of the engine stays where the command left it (over index r), e.g. for (None,AllIn,'A') right after the last 'A' matched.

In case the command does not match, the engine either continues at the table entry reached after skipping jump_no_match entries, or if this value is not given, terminates matching the current table and returns not matched. The head position is always restored to the position it was in before the non-matching command was executed, enabling backtracking.

The format of the command_argument is dependent on the command. It can be a string, a set, a search object, a tuple of some other wild animal from Python land. See the command section below for details.

A table matches a string if and only if the Tagging Engine reaches a table index that lies beyond the end of the table. The engine then returns matched ok. Jumping beyond the start of the table (to a negative table index) causes the table to return with result failed to match.

Tagging Commands

The commands and constants used here are integers defined in Constants/TagTables.py and imported into the package's root module. For the purpose of explaining the taken actions we assume that the tagging engine was called with tag(text,table,start=0,end=len(text)). The current head position is indicated by x.

Command	Matching Argument	Action
Fail	Here	Causes the engine to fail matching at the current head position.
Jump	To	Causes the engine to perform a relative jump by jump_no_match entries.
AllIn	string	Matches all characters found in text[x:end] up to the first that is not included in string. At least one character must match.
AllNotIn	string	Matches all characters found in text[x:end] up to the first that is included in string. At least one character must match.
AllInSet	set	Matches all characters found in text[x:end] up to the first that is not included in the string set. At least one character must match.
Is	character	Matches iff text[x] == character.
IsNot	character	Matches iff text[x] != character.
IsIn	string	Matches iff text[x] is in string.
IsNotIn	string	Matches iff text[x] is not in string.
IsInSet	set	Matches iff text[x] is in set.
Word	string	Matches iff text[x:x+len(string)] == string.
WordStart	string	Matches all characters up to the first occurance of string in text[x:end]. If string is not found, the command does not match and the head position remains unchanged. Otherwise, the head stays on the first character of string in the found occurance. At least one character must match.
WordEnd	string	Matches all characters up to the first occurance of string in text[x:end]. If string is not found, the command does not match and the head position remains unchanged. Otherwise, the head stays on the last character of string in the found occurance.
sWordStart	search object	Same as WordStart except that the search object is used to perform the necessary action (which can be much faster) and zero matching characters are allowed.
sWordEnd	search object	Same as WordEnd except that the search object is used to perform the necessary action (which can be much faster).
sFindWord	search object	Uses the search object to find the given substring. If found, the tagobj is assigned only to the slice of the substring. The characters leading up to it are ignored. The head position is adjusted to right after the substring -- just like for sWordEnd.
Call	function	Calls the matching function(text,x,end). The function must return the index y of the character in text[x:end] right after the matching substring. The entry is considered to be matching, iff x != y. The engines head is positioned on y in that case.
CallArg	(function,[arg0,...])	Same as Call except that function(text,x,end[,arg0,...]) is being called. The command argument must be a tuple.
Table	tagtable or ThisTable	Matches iff tagtable matches text[x:end]. This calls the engine recursively. In case of success the head position is adjusted to point right after the match and the returned taglist is made available in the subtags field of this tables taglist entry. You may pass the special constant ThisTable instead of a Tag Table if you want to call the current table recursively.
SubTable	tagtable or ThisTable	Same as Table except that the subtable reuses this table's tag list for its tag list. The subtags entry is set to None. You may pass the special constant ThisTable instead of a Tag Table if you want to call the current table recursively.
TableInList	(list_of_tables,index)	Same as Table except that the matching table to be used is read from the list_of_tables at position index whenever this command is executed. This makes self-referencing tables possible which would otherwise not be possible (since Tag Tables are immutable tuples). Note that it can also introduce circular references, so be warned !
SubTableInList	(list_of_tables,index)	Same as TableInList except that the subtable reuses this table's tag list. The subtags entry is set to None.
EOF	Here	Matches iff the head position is beyond end.
Skip	offset	Always matches and moves the head position to x + offset.
Move	position	Always matches and moves the head position to slice[position]. Negative indices move the head to slice[len(slice)+position+1], e.g. (None,Move,-1) moves to EOF. slice refers to the current text slice being worked on by the Tagging Engine.
Loop	count	Remains undocumented for this release.
LoopControl	Break/Reset	Remains undocumented for this release.

The following flags can be added to the command integers above:

CallTag

Instead of appending (tagobj,l,r,subtags) to the taglist upon successful matching, call tagobj(taglist,text,l,r,subtags).

AppendMatch

Instead of appending (tagobj,l,r,subtags) to the taglist upon successful matching, append the match found as string.

Note that this will produce non-standard taglists ! It is useful in combination with join() though and can be used to implement smart split() replacements algorithms.

AppendToTagobj

Instead of appending (tagobj,l,r,subtags) to the taglist upon successful matching, call tagobj.append((None,l,r,subtags)).

AppendTagobj

Instead of appending (tagobj,l,r,subtags) to the taglist upon successful matching, append tagobj itself.

Note that this can cause the taglist to have a non-standard format, i.e. functions relying on the standard format could fail.

This flag is mainly intended to build join-lists usable by the join()-function (see below).

LookAhead

If this flag is set, the current position of the head will be reset to l (the left position of the match) after a successful match.

This is useful to implement lookahead strategies.

Using the flag has no effect on the way the tagobj itself is treated, i.e. it will still be processed in the usual way.

Some additional constants that can be used as argument or relative jump position:

To

Useful as argument for 'Jump'.

Here

Useful as argument for 'Fail' and 'EOF'.

MatchOk

Jumps to a table index beyond the tables end, causing the current table to immediatly return with 'matches ok'.

MatchFail

Jumps to a negative table index, causing the current table to immediatly return with 'failed to match'.

ToBOF,ToEOF

Useful as arguments for 'Move': (None,Move,ToEOF) moves the head to the character behind the last character in the current slice, while (None,Move,ToBOF) moves to the first character.

ThisTable

Useful as argument for 'Table' and 'SubTable'. See above for more information.

Internally, the Tag Table is used as program for a state machine which is coded in C and accessible through the package as tag() function along with the constants used for the commands (e.g. Allin, AllNotIn, etc.). Note that in computer science one normally differentiates between finite state machines, pushdown automata and turing machines. The Tagging Engine offers all these levels of complexity depending on which techniques you use, yet the basic structure of the engine is best compared to a finite state machine.

These functions are defined in the package:

Things that still need to be done:

• Provide some more examples.

• Clean up the C implementation and this document some more.

• Do some benchmarking...

• Add a cached based mechanism that compiles the tuples into easily machine readable and sanity checked C arrays. The cache should keep a weak reference to the tuples in order to be able to use their object id as hash value. The cache ought to free and remove entries whose refcount have gone down to one. This should improve the performance of the already fast engine even more. [Patrick Maupan has contributed a similar implementation which waits to be integrated into mxTextTools.]

• Provide a command to raise parametrized exceptions.

• Add a tag command to match word-in-list. This could also be extended to use multi pattern search objects.

• Add a command or feature to allow efficient lookahead. A table will have to be able to return differentiated information about what part of it actually did match. E.g. if the table matches A(B|C|D) and the string is found to match AC, there should be a way for the caller to identify and use that information for further execution.

• Add a per-call stack and command to manipulate it. This would provide for a way to do recursion without relying on the C stack and also provide a means to implement communication between the different recursive levels (might be of use for the above bullet). [Patrick Maupan has contributed a similar implementation which waits to be integrated into mxTextTools.]

• Convert some more APIs to use the buffer interface instead of insisting on Python string objects.

• Add the examples to the regression tests.

• Add a context object to all commands which call external resources. This should make context sensitive parsing and other cool things much more easy to implement. It will change the function call signatures though, so is likely to break code. [Patrick Maupan has contributed a similar implementation which waits to be integrated into mxTextTools.]

• Provide an Unicode aware version of mxTextTools.

• Use a special list implementation for taglists which resize in larger chunks (e.g. 1024 entries per realloc()). The current scheme implemented in the standard Python list implementation does way to many realloc()s, slowing down the taglist creation considerably.

Things that changed from 2.0.2 to 2.0.3:

• Added isascii().

Things that changed from 2.0.0 to 2.0.2:

• Fixed a bug in the Words.py example. Thanks to Michael Husmann for finding this one.

• Fixed a memory leak in the CallTag processing.