GitHub - harbu/RegExp-parser: A little Ruby learning project applying concepts from theory of computation.

harbu / RegExp-parser Public

Notifications You must be signed in to change notification settings
Fork 0
Star 3

A little Ruby learning project applying concepts from theory of computation.

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 30 Commits
bin		bin
lib		lib
test		test
README		README

Repository files navigation

SUMMARY
--------------------------------------------------------------------------------
This is a project I'm doing to learn Ruby. I want to create a simple regular
expression parser that creates an equivalent NFA to match against given input.

HOW IT WORKS?
--------------------------------------------------------------------------------
(1) Given a regular expression pattern in infix form, "InfixToPostfix" converts
it into postfix form using the Shunting-yard algorithm.

(2) The postfix pattern is then easily converted into a nondeterministic
finite automaton (NFA) by the "PostfixToAutomaton"-class, which uses conversions
described in the sources [1,2].

(3) A given string can then be matched against the NFA by "AutomatonRunner".



SOURCES
--------------------------------------------------------------------------------
[1] Sipser, M., Introduction to the Theory of Computation, 2nd edition, 2006
[2] http://swtch.com/~rsc/regexp/regexp1.html
[3] http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm
[4] http://en.wikipedia.org/wiki/Shunting_yard_algorithm