Click here to Skip to main content
15,893,487 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 
GeneralRe: That's the last straw... Pin
Eddy Vluggen3-Feb-20 11:58
professionalEddy Vluggen3-Feb-20 11:58 
GeneralRe: That's the last straw... Pin
kalberts3-Feb-20 12:22
kalberts3-Feb-20 12:22 
GeneralRe: That's the last straw... Pin
Eddy Vluggen3-Feb-20 12:31
professionalEddy Vluggen3-Feb-20 12:31 
GeneralRe: That's the last straw... Pin
dandy724-Feb-20 5:13
dandy724-Feb-20 5:13 
GeneralRe: That's the last straw... Pin
Mark_Wallace3-Feb-20 12:50
Mark_Wallace3-Feb-20 12:50 
GeneralRe: That's the last straw... Pin
MarkTJohnson4-Feb-20 4:06
professionalMarkTJohnson4-Feb-20 4:06 
GeneralRe: That's the last straw... Pin
dandy724-Feb-20 5:16
dandy724-Feb-20 5:16 
GeneralFinal optimization, and it's super cool Pin
honey the codewitch3-Feb-20 6:25
mvahoney the codewitch3-Feb-20 6:25 
So I finally got the regex optimizing compiler to spit the output i wanted


And it's almost perfect, save the jmp at the beginning the but that's negligible. This is nearly a pure DFA.

The tricky part is at the root some of my lexer expressions may not be able to be converted into this DFA (optimized) code. And while order of evaluation doesn't matter for DFAs it does matter for NFAs (any of the non-optimizable expressions)

So basically what I had to do was scan through my lex expressions top to bottom, looking for entire runs of optimizable expressions

Those I'd transform into a single DFA expression with multiple different match instructions.

And then I intersperse those with the unoptimized expressions in the same order they came to me in.

And boom it allows me therefore to go from
L0000: save 0
L0001: jmp L0002, L0008, L0019, L0022
L0002: set "A".."Z", "_", "a".."z"
L0003: jmp L0004, L0006
L0004: set "0".."9", "A".."Z", "_", "a".."z"
L0005: jmp L0003
L0006: save 1
L0007: match 0
L0008: jmp L0009, L0011
L0009: char "0"
L0010: jmp L0017
L0011: jmp L0012, L0013
L0012: char "-"
L0013: set "1".."9"
L0014: jmp L0015, L0017
L0015: set "0".."9"
L0016: jmp L0014
L0017: save 1
L0018: match 1
L0019: set "\t", "\n", "\v", "\f", "\r", " "
L0020: save 1
L0021: match 2
L0022: any
L0023: save 1
L0024: match -1


Which requires lots of fibers and therefore multiple scans of a character per pass

to this, which requires only two scans per pass max (error checking accounts for the extra jmp):

L0000: save 0
L0001: jmp L0002, L0008
L0002: switch case "\t".."\r", " ":L0003, case "-":L0003, case "0":L0005, case "1".."9":L0004, case "A".."Z", "_", "a".."z":L0005
L0003: switch case "1".."9":L0004
L0004: switch case "0".."9":L0004, default:L0006
L0005: switch case "0".."9", "A".."Z", "_", "a".."z":L0005, default:L0006
L0006: save 1
L0007: match 0
L0008: any
L0009: save 1
L0010: match -1


The only thing left i have to potentially do is eliminate that jmp at the beginning, and add the second operand as the default in the switch/case that follows.

Edit: Perf testing shows me maybe i don't need to that, as it's already on par with the DFA. WOO!

I'm proud of myself. Shucks | :-\

Edit: Whoops, bit of a bug i just noticed but minor.
Real programmers use butterflies

QuestionRe: Final optimization, and it's super cool Pin
Eddy Vluggen3-Feb-20 7:27
professionalEddy Vluggen3-Feb-20 7:27 
AnswerRe: Final optimization, and it's super cool Pin
honey the codewitch3-Feb-20 7:48
mvahoney the codewitch3-Feb-20 7:48 
GeneralRe: Final optimization, and it's super cool Pin
Eddy Vluggen3-Feb-20 8:03
professionalEddy Vluggen3-Feb-20 8:03 
GeneralRe: Final optimization, and it's super cool Pin
honey the codewitch3-Feb-20 8:57
mvahoney the codewitch3-Feb-20 8:57 
GeneralRe: Final optimization, and it's super cool Pin
Eddy Vluggen3-Feb-20 9:41
professionalEddy Vluggen3-Feb-20 9:41 
GeneralRe: Final optimization, and it's super cool Pin
honey the codewitch3-Feb-20 10:07
mvahoney the codewitch3-Feb-20 10:07 
GeneralThought of the Day Pin
OriginalGriff3-Feb-20 4:36
mveOriginalGriff3-Feb-20 4:36 
GeneralRe: Thought of the Day Pin
littleGreenDude3-Feb-20 5:21
littleGreenDude3-Feb-20 5:21 
GeneralRe: Thought of the Day Pin
OriginalGriff3-Feb-20 5:26
mveOriginalGriff3-Feb-20 5:26 
GeneralRe: Thought of the Day Pin
honey the codewitch3-Feb-20 5:47
mvahoney the codewitch3-Feb-20 5:47 
GeneralRe: Thought of the Day Pin
Gary Wheeler3-Feb-20 7:21
Gary Wheeler3-Feb-20 7:21 
GeneralRe: Thought of the Day Pin
honey the codewitch3-Feb-20 5:46
mvahoney the codewitch3-Feb-20 5:46 
GeneralRe: Thought of the Day Pin
Jacquers3-Feb-20 7:11
Jacquers3-Feb-20 7:11 
GeneralRe: Thought of the Day Pin
W Balboos, GHB3-Feb-20 7:31
W Balboos, GHB3-Feb-20 7:31 
GeneralRe: Thought of the Day Pin
Daniel Pfeffer3-Feb-20 22:05
professionalDaniel Pfeffer3-Feb-20 22:05 
GeneralNew workplace! Pin
Sander Rossel3-Feb-20 1:14
professionalSander Rossel3-Feb-20 1:14 
GeneralRe: New workplace! Pin
honey the codewitch3-Feb-20 1:20
mvahoney the codewitch3-Feb-20 1:20 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.