News for hackers. Stuff that matters.
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.