This thesis explores efficient regular expressions that generate parse trees, covering topics such as full parse trees, Thompson construction, and NFA. It discusses history storage using singly linked lists, version trees, and an indirection structure for efficient relabeling. The work also analyzes regular expression grammar parse times.
