T-106.290 Ohjelmoinnin laboratoriotyöt

Subject: Regular Expression Libraries (2 or 3 cr)

The purpose of this assignment is to review and evaluate existing C/C++ systems for regular expression matching:

• GNU regex
• libtre
• Henry Spencer's library
• pcre
• John Maddock's library
• vstring
• Possibly also mptn

Benchmark the libraries a large variety of regular expressions and matched data. Use also extremely large or machine-generated regular expressions in order test the libraries beyond their normal usage. Although computational efficiency is the most natural measurement, follow also memory consumption in case of anomalies. Give in your report also a good compilation of qualitative data, such as observed reliability, features, license, etc.

You can extend the topic to three credits by extending your study to cover also:

• Libraries implemented in Java
• ragel or programs generated by lex or flex.

Some references

Presumably most information for this topic is found in the Internet either as software or on-line articles. DMOZ has a good link list, but oriented more from a regular expression user's point of view.

To some degree the following general algorithmics sources are useful:

• Aho, Hopcroft, Ullman, Data Structures and Algorithms
• Aho, Hopcorft, Ullman, The Design and Analysis of Computer Algorithms
• Cormen, Leiserson, Rivest:  Introduction to algorithms
• Horowitz, Sahni:  Fundamentals of Data Structures in Pascal
• Kingston, Algorithms and Data Structures
• Sedgewick:  Algorithms / Algorithms in C / Algorithms in C++
• Weiss:  Data Structures and Algorithm Analysis (various versions for Pascal, C, C++ and Java)
• Wirth, Algorithms + Data Structures = Programs