Efficient regular expressions that produce parse trees

Efficient regular expressions that produce parse trees.
A thesis submittet in partial fulfillment for the degree of Master of Science in the Philosophisch-naturwissenschaftliche Fakultät Institute of Computer Science and Applied Mathematics:
Full parse tree
Thompson construction
NFA for =((:?); (nd+); ) + =
Modified Thompson construction
Histories are cells of singly linked lists, where only the first (here bottommost) cell can be edited. This is a view of the automaton in figure 2.2 after the string “TomLehrer; 1; AlanTuring;” has been consumed. Only the cell for the closing of the second capture group is shown
A tree of versions. Forks in the tree mean that multiple threads were forked from the same state in the TNFA. The labels describe the relative order of creation
Treap for history storage
A flattened version tree
Tree for relabeling order
Indirection structure: use a compound index with the high-order bits being the index for the upper structure and the
low-order bits being the index for the lower structure. Since the upper index is stored in the summary structure,
log u items can be relabeled in O(1) time
Regular expression grammar parse time
Pathological regular expression parse time