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 loworder 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

In Hamburg geboren, jetzt als Mathematiker und Informatiker in der Schweiz lebend.