3 ms·
Some person explained that HTML is a Chomsky type 2 grammar and regular expressions are a Chomsky type 3 grammar, and provided this link: http://en.wikipedia.or
by euroclydon 16y ago
Some person explained that HTML is a Chomsky type 2 grammar and regular expressions are a Chomsky type 3 grammar, and provided this link: http://en.wikipedia.org/wiki/Chomsky_hierarchy http://en.wikipedia.org/wiki/Chomsky_hierarchy
Can anyone here provide a link that makes the discussion of these typed grammars available to laymen?
- steveklabnik 16y agoThis answer on Reddit is pretty solid: http://www.reddit.com/r/programming/comments/cm02a/you_cant_parse_html_with_regular_expressions/c0tjedt http://www.reddit.com/r/programming/comments/cm02a/you_cant_... Depends on your definition of 'laymen,' I guess. Also note that PCREs actually are recursively enumerable (I think).
- bad_user 16y agoOh, 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.