Skip to content

Latest commit

 

History

History
67 lines (47 loc) · 1.69 KB

README.md

File metadata and controls

67 lines (47 loc) · 1.69 KB
Raw

regex_engine

Regex engine written in C++.

Specification

Implement a basic regex engine using C++. The requirements are to create a program with the following features:

  • The program is built using the command make bin/regex_engine (in the directory c).

  • The program takes as an input argument an ASCII regular expression, which can contain the following constructs:

    • Character literals (but not character ranges).

      • Character literals only include the alphabetic letters, numbers, and underscore, so each literal must match [a-zA-Z0-9_].

      • The dot construct will not appear, as it is syntactic sugar for a character range containing all characters.

    • One-or-more (but not zero-or-more)

    • Grouping

    • Alternation

    Neither the regular expression nor input strings will contain whitespace.

  • The program should read a sequence of input lines from stdin, and apply the regular expression to the line.

  • Each input line should result in a corresponding output on stdout, which consists of either:

    • Match if the regular expression matches the whole line

    • NoMatch if the regular expression does not match

Efficiency is not important (within reason!). So test inputs are designed to have reasonable run-time, even if there is a worst-case exponential execution time in the regex engine.

Example

An example session would be (with input and output interleaved):

$ make bin/regex_engine
$ bin/regex_engine "ab+"
a
NoMatch
ab
Match
abb
Match
abab
NoMatch

Credits

This implementation is based on the Thompson NFA algorithm described by Russ Cox in this post. This implementation si