Implement PCRE Matching (prefer left-branch) #2

Merged

Rockingcool merged 48 commits from implementPCREMatchingRules into master

Rockingcool commented

Owner

There is no content yet.

Rockingcool added 48 commits

fbc9dfcc95 Trying something out; we'll see if it works

09812956ac Disable all optimizations

1fd48ae614 Store the current string pointer as a 'thread variable' (allows us to simulate backtracking)

e167cdb2cb Fixed mistake in test output

ad273b0c68 Trying to emulate backtracking by using string pointers within threads (something similar to rsc's 2nd regexp article)

de0d7345a8 Store left and right branches of alternation separately

5563a70568 Reverse the order in which I pop states for alternation, because this messes with the left branch-right branch thing

753e973d82 Started rewrite of matching algorithm, got concatenation and alternation done, kleene and zero-state stuff is next

e0253dfaf3 Change kleene() to an alternation-style construct

3ce611d121 More work towards implementing PCRE matching

d4e8cb74fd Replaced pointer to nfaState with nfaState

7c62ba6bfd Started implementing Thompson's algorithm for matching, because the old one was completely backtracking (so it would enter infinite loops on something like '(a*)*' )

The git diff claims that a ton of code was changed, but most of it was just indentation changes.

858e535fba Continued implementing Thompson's algorithm

cca8c7cda2 Got rid of transitions parameter, changed how kleene state is processed

I replaced the transition parameter for nfaState, replacing it with a
single nfaState pointer. This is because any non-alternation state will
only have one next state, so the map was just added complexity.

I changed alternation processing - instead of having their own dedicated
fields, they just use the new 'next' parameter, and another one called
'splitState'.

I also changed the kleene state processing to remove the unecessary
empty state in the right-side alternation (it actually messed up my
matching).

fbc9bea9fb Commented out unused functions; use new nfaState parameters

ed4ffde64e REFACTOR NEEDED: Added another special case; insert instead of appending into currentStates

8534174ea1 Use pointers instead of values

1d4f695f8f Wrote function to check if a state is in an nfaState, based on the Equals function

ccf3b3b299 More progress on implementing PCRE matching

d2ad0d95a8 Modified question operator so that it doesn't create an unnecessary zero-state

052de55826 question() now returns 2 values

3604486a9b Used Pike's algorithm (an extension to Thompson's algorithm) (see Russ Cox's 2nd article); I think I almost have a working PCRE-style engine

22ead83625 Fixed assertion matching

99230b49de Use new function signature for zeroLengthMatchState()

62ca1a872a Made zeroLengthMatchState() return a pointer; reduced the number of comparisons performd by nfaState.equals

f15a5cae34 Store all states visited in a single run of 'addStateToList()' in a slice