Implement PCRE Matching (prefer left-branch) #2

Rockingcool · 2025-02-09T15:14:08-06:00

Rockingcool commented

2025-02-09 15:14:08 -06:00

No description provided.

Rockingcool added 48 commits 2025-02-09 15:14:11 -06:00

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

Disable all optimizations 09812956ac

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

Fixed mistake in test output e167cdb2cb

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

Store left and right branches of alternation separately de0d7345a8

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

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

Change kleene() to an alternation-style construct e0253dfaf3

More work towards implementing PCRE matching 3ce611d121

Replaced pointer to nfaState with nfaState d4e8cb74fd

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

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

Continued implementing Thompson's algorithm 858e535fba

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

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).

Commented out unused functions; use new nfaState parameters fbc9bea9fb

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

Use pointers instead of values 8534174ea1

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

More progress on implementing PCRE matching ccf3b3b299

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

question() now returns 2 values 052de55826

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 3604486a9b

Fixed assertion matching 22ead83625

Use new function signature for zeroLengthMatchState() 99230b49de

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

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