Design and Implementation of the FIRE Engine: A C++ Toolkit for FInite Automataand Regular Expressions

摘要

This paper describes the design and implementation of version 1.1 of the FIREengine. The FIRE engine is a C++ class library implementing finite automata and regular expression algorithms. The algorithms implemented in the toolkit are almost all of those presented in the taxonomies of finite automata algorithms. The reader is assumed to be familiar with the two taxonomies and with advanced C++ programming techniques. The toolkit is implemented largely in an object-oriented style, with finite automata and regular expressions being defined as classes. All of the classes and functions in the toolkit are presented in the same format. For each class (or function) the format includes a short description of its behavior, details of its implementation, and techniques for improving its performance.