Live data from Hacker News

Oh Yes You Can Use Regexes to Parse HTML

stackoverflow.com

21–22 of 22 posts

Re: Oh Yes You Can Use Regexes to Parse HTML

#21
post #9

I know of no Regex pattern that can handle all the old and new HTML as well as HTML5: believe me, as one who is looking to put HTML parser on FPGA/ASIC for higher speed, I've actually forayed down this rabbit hole a few times in the fruitless pursuit of identifying this elusive pure Regex pattern for HTML, et. al. Problem is in Regex's lack of support for multiple state machine and its needed interactions between the…

Regex if extended can go as far as Turing-complete

Meanwhile regular expression (the OG Regex) is just an NFA and should be easier to implement in circuit. The problem is an NFA circuit still needs exponential expansion (if minimized to DFA which is just power set of encoding and eliminating possible NFA states), and with Turing complete Regex you have halting problem -- both are hellish to solve unless P=NP

Re: Oh Yes You Can Use Regexes to Parse HTML

#22
post #9

I know of no Regex pattern that can handle all the old and new HTML as well as HTML5: believe me, as one who is looking to put HTML parser on FPGA/ASIC for higher speed, I've actually forayed down this rabbit hole a few times in the fruitless pursuit of identifying this elusive pure Regex pattern for HTML, et. al. Problem is in Regex's lack of support for multiple state machine and its needed interactions between the…

Regex if extended can go as far as Turing-complete Meanwhile regular expression (the OG Regex) is just an NFA and should be easier to implement in circuit. The problem is an NFA circuit still needs exponential expansion (if minimized to DFA which is just power set of encoding and eliminating possible NFA states), and with Turing complete Regex you have halting problem -- both are hellish to solve unless P=NP

Yeah. Doing at firmware-level this Regex-stack-tracking of multiple but separate data streams requires some CPU assist for this "halting" problem.
Post reply on HN