-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
24 lines (18 loc) · 1.08 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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