Hacker News Reader

Comment by scott_s | Hacker News Reader

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.

View on HN

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.

Exactly. Gnu's Flex lets the user define regex's for each state of the parser... http://flex.sourceforge.net/manual/Patterns.html#Patterns

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/

You're quite right, thanks

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?

What do you mean by "can't do recursion"? A regular grammar can definitely be recursive.

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.

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).

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..

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.

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.

Typo: I meant not all recursive languages can be described by regular grammars.

Reply on news.ycombinator.com