3 ms·
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 tra
by nmadden 11y ago
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)$.
- _delirium 11y agoFwiw 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.
- gsnedders 11y agoIn 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.