News for hackers. Stuff that matters.
Re:Oh Yes You Can Use Regexes to Parse HTML by scott_s on Friday July 08, 2011 @10:25AM (#2742509)
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.
Re:Oh Yes You Can Use Regexes to Parse HTML by pak on Friday July 08, 2011 @10:37AM (#2742578)
This 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.

Re:Oh Yes You Can Use Regexes to Parse HTML by justinhj on Friday July 08, 2011 @12:23PM (#2743065)
Exactly. Gnu's Flex lets the user define regex's for each state of the parser... http://flex.sourceforge.net/manual/Patterns.html#Patterns
Re:Oh Yes You Can Use Regexes to Parse HTML by LukeShu on Friday July 08, 2011 @01:41PM (#2743365)
Flex is used by the GNU System, but it is not GNU. It is incorrect to call it "Gnu's Flex". http://www.gnu.org/software/flex/
Re:Oh Yes You Can Use Regexes to Parse HTML by justinhj on Friday July 08, 2011 @09:31PM (#2744745)
You're quite right, thanks
Re:Oh Yes You Can Use Regexes to Parse HTML by wisty on Friday July 08, 2011 @10:43AM (#2742611)
Right. 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?
Re:Oh Yes You Can Use Regexes to Parse HTML by kd0amg on Friday July 08, 2011 @10:58AM (#2742695)
What do you mean by "can't do recursion"? A regular grammar can definitely be recursive.
Re:Oh Yes You Can Use Regexes to Parse HTML by qntm on Friday July 08, 2011 @12:28PM (#2743086)
Negative, 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.

Re:Oh Yes You Can Use Regexes to Parse HTML by jhck on Friday July 08, 2011 @01:33PM (#2743333)
No, 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).
Re:Oh Yes You Can Use Regexes to Parse HTML by burgerbrain on Friday July 08, 2011 @01:50PM (#2743397)
You 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..

Re:Oh Yes You Can Use Regexes to Parse HTML by qntm on Friday July 08, 2011 @04:33PM (#2743967)
I 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.

Re:Oh Yes You Can Use Regexes to Parse HTML by nandemo on Friday July 08, 2011 @10:10PM (#2744802)
That's basically the standard definition of regular grammar: a grammar that describes a regular language.

All this subthread is fairly confusing because people are using the term "recursive" in a non-stardard way. Recursive languages are the languages decidable by a Turing machine. They're a strict superset of regular languages, i.e., not all regular languages can be described by regular grammars, but all regular grammars describe recursive languages.

Now, some regular grammars are left-recursive or right-recursive, which means sometimes the same symbol appears on both sides of a rule. It doesn't mean they the have the power of full recursion that we find in full-blown programming languages, since they don't have the equivalent of a stack.

Re:Oh Yes You Can Use Regexes to Parse HTML by nandemo on Saturday July 09, 2011 @01:10PM (#2745885)
Typo: I meant not all recursive languages can be described by regular grammars.