5 ms·
I classify this as a parser using regular expressions rather than parsing using regular expressions. That is, his regular expressions don't parse the document.
by scott_s 15y ago
I classify this as a parser using regular expressions rather than parsing using regular expressions. That is, his regular expressions don't parse the document. He wrote a parser, and uses regular expressions in that parser.
- pak 15y agoThis is correct. As soon as I saw his lex_html function, I could see that he was using regexes to tokenize and then basically drop into different contexts while consuming the document, thereby tracking multiple levels of state throughout. That's what a full-blown parser does and it goes beyond the scope of regular languages. By "parsing with regular expressions" most people mean applying one or two regexes to the entire document and using, for example, the group capture facility to extract information. That is and will always be a bad idea for HTML, because HTML is not a regular language. Applying regular expressions to tokenize a string for a parsing is actually a fairly standard pattern.
- justinhj 15y agoExactly. Gnu's Flex lets the user define regex's for each state of the parser... http://flex.sourceforge.net/manual/Patterns.html#Patterns http://flex.sourceforge.net/manual/Patterns.html#Patterns
- wisty 15y agoRight. Pyparsing is a nice parsing library, and it uses regular expression. I'd expect most parsing libraries do let you define stuff in regex. But they can't do recursion, right?
- kd0amg 15y agoWhat do you mean by "can't do recursion"? A regular grammar can definitely be recursive.
- qntm 15y agoNegative, a regular grammar which describes a regular language cannot be recursive. For recursion you need to be context-free at least. Of course, most modern "regex" engines provide features which go beyond the strictly regular languages.
- jhck 15y agoNo, kd0amg is right. Here's a simple example of a recursive regular grammar: S → aS | ε This grammar is right linear (see http://en.wikipedia.org/wiki/Regular_grammar http://en.wikipedia.org/wiki/Regular_grammar).
- burgerbrain 15y agoYou can in fact do recursion with regular grammars as you've just demonstrated, but if you mix right regular grammars with left regular grammars (as you would need to do in order to, for example, match parenthesis) your grammar is no longer regular (not equivalent to regular expressions). I suspect that is what wisty meant. Honestly though, this entire conversation is fuzzed by the blurred distinction between "parsing with regular expressions, and writing a parser that uses regular expressions to tokenize" by the original author. I'm not really sure where just about every other person in this discussion is coming from as a result..
- qntm 15y agoI didn't know that a grammar featuring recursion can still be called a "regular" grammar if the language it describes is regular. However, no regular grammar (not even a recursive regular grammar) can describe a recursive language.