So there *is* a point to all that finite automata theory...
-
Saw this[^] come across LtU[^] this morning. Interesting article on how most Regex implementations absolutely suck performance-wise and why they should be using Thompson NFA construction (which, interestingly, is how a lot of the compiler construction lexer/parser toolkits do parsing). You'd think that, since compiler writers use Thompson NFA, regex interpreters would also use it. Yay for my formal CS education. I can actually understand articles like this. There is a reason to sit and read that dragon book. :rolleyes:
-
Saw this[^] come across LtU[^] this morning. Interesting article on how most Regex implementations absolutely suck performance-wise and why they should be using Thompson NFA construction (which, interestingly, is how a lot of the compiler construction lexer/parser toolkits do parsing). You'd think that, since compiler writers use Thompson NFA, regex interpreters would also use it. Yay for my formal CS education. I can actually understand articles like this. There is a reason to sit and read that dragon book. :rolleyes:
-
Saw this[^] come across LtU[^] this morning. Interesting article on how most Regex implementations absolutely suck performance-wise and why they should be using Thompson NFA construction (which, interestingly, is how a lot of the compiler construction lexer/parser toolkits do parsing). You'd think that, since compiler writers use Thompson NFA, regex interpreters would also use it. Yay for my formal CS education. I can actually understand articles like this. There is a reason to sit and read that dragon book. :rolleyes:
Oh my god! I know the dragon book well... It was the source for most of the contempt I had for life during that semester.
I win because I have the most fun in life...
-
My hatred of higher mathematics has always made me blank out when I read algorithms presented that way. :doh:
Actually...none of that involves higher math. (Believe me. I'd know. I'm studying higher math right now. ;P) There's a really good text by Michael Sipser on the Theory of Computation[^] that provides some very clear explanation of finite automata, regular expressions, turing machines, etc. It's really pretty enlightening and will definitely cause you to re-think how you code stuff. :)
-
Saw this[^] come across LtU[^] this morning. Interesting article on how most Regex implementations absolutely suck performance-wise and why they should be using Thompson NFA construction (which, interestingly, is how a lot of the compiler construction lexer/parser toolkits do parsing). You'd think that, since compiler writers use Thompson NFA, regex interpreters would also use it. Yay for my formal CS education. I can actually understand articles like this. There is a reason to sit and read that dragon book. :rolleyes:
Neat. That one's going on my reading list. :)
---- Scripts i’ve known... CPhog 1.8.2 - make CP better. Forum Bookmark 0.2.5 - bookmark forum posts on Pensieve Print forum 0.1.2 - printer-friendly forums Expand all 1.0 - Expand all messages In-place Delete 1.0 - AJAX-style post delete Syntax 0.1 - Syntax highlighting for code blocks in the forums
-
Actually...none of that involves higher math. (Believe me. I'd know. I'm studying higher math right now. ;P) There's a really good text by Michael Sipser on the Theory of Computation[^] that provides some very clear explanation of finite automata, regular expressions, turing machines, etc. It's really pretty enlightening and will definitely cause you to re-think how you code stuff. :)
David Stone wrote:
There's a really good text by Michael Sipser on the Theory of Computation[^] that provides some very clear explanation of finite automata, regular expressions, turing machines, etc. It's really pretty enlightening and will definitely cause you to re-think how you code stuff. :)
The first edition[^] of that book has been constantly perused since it was introduced to me in college back in '99. I'm still fascinated by its contents. I had intro to Computing Theory and intro to Computer Engineering the same semester, and it was without a doubt the single most enthralling semester I had in college. I lost track of how many times I slapped my forehead and said "Holy crap - it's that simple?!?!"
"I hope he can see this, because I'm doing it as hard as I can" - Ignignot
-
Saw this[^] come across LtU[^] this morning. Interesting article on how most Regex implementations absolutely suck performance-wise and why they should be using Thompson NFA construction (which, interestingly, is how a lot of the compiler construction lexer/parser toolkits do parsing). You'd think that, since compiler writers use Thompson NFA, regex interpreters would also use it. Yay for my formal CS education. I can actually understand articles like this. There is a reason to sit and read that dragon book. :rolleyes:
The dragon book was always one of my favorites - I even wrote some parser-generators to test my little knowledge. As far as I understand the problem with the Regex-Implementations is, that they are using more than you can gain by using DFA or NFA (they are both equally powerfull).