Hacker News new | past | comments | ask | show | jobs | submit login

Actually, "plain" regular expressions/FSAs can parse HTML up to any arbitrary finite nesting depth (i.e. all those you will ever encounter in practice). The trade-off is that they need exponentially more states to do so than an equivalent CFG/pushdown automata.

For example the a^n b^n example can be recognised up to n<=3 by the RE ^(|ab|aabb|aaabbb)$.




Fwiw browsers do this in practice, so the subset of HTML usable on the web is already regular. For example, Webkit-based browsers impose a nesting depth limit of 512.


In case anyone is curious:

WebKit and Blink both use 512. Gecko uses 200. Trident uses a limit beyond what I've tested quickly (over 4096). Presto uses 500.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: