4 ms·
Oh, I don't know if reducing the grammars to Chomsky is really necessary. Regular expressions, in their original version, are equivalent to Finite-stage Machin
by bad_user 16y ago
Oh, I don't know if reducing the grammars to Chomsky is really necessary.
Regular expressions, in their original version, are equivalent to Finite-stage Machines (i.e. ... regular grammars, no recursion, no stack, no memory further than keeping the current state). You can't describe the rules of HTML with a FSM.
Perl's regular expressions contain various enhancements. Newer versions of Perl's regexes also contain direct support for recursion (but frankly, you can't call those "regular expressions" anymore).
So ... if your regex library has recursion support, then you can parse HTML (since with recursion you can parse context-free / Chomsky type-2 grammars). If it doesn't support recursion, then you can't.
Btw ... the equivalent for a context-free grammar would be a Push-down Automaton ... http://en.wikipedia.org/wiki/Pushdown_automaton http://en.wikipedia.org/wiki/Pushdown_automaton , which is a FSM + a stack.