Topic on Talk:Markup spec

I've a background in computer science and/but I found this section hard to follow. The distinctions between relaxed, restrictive and restraining mix concepts together which are really separate, namely

• the form of the rules and
• the way the rules are used, and thus the qualities of the grammar they generate.

Regular grammars have the tightest restrictions on the form of their rules but the grammars they generate impose the fewest restrictions on the use of a rule (together with context-free grammars). The idea that this situation is counter-intuitive results from this confusion of levels rather than from anything intrinsically puzzling about the kinds of grammar. Though I do appreciate that the author wants to highlight this distinction somehow.

I found it surprising to find the following statement: "Considering that it could be argued that Wikicode it is indeed a regular language." Whether Wikicode is or isn't a regular language seems to be more a matter of fact than opinion, but the statement suggests that there is some flexibility in the idea of a regular grammar. Is there a limit on how deeply nested constructs can be? If not, then Wikicode cannot be a regular language. Even if it were regular, the grammar needed to describe it might be far too difficult to understand and/or to implement to be of practical use or interest.

I hope these comments are constructive. I must confess to being a bit shocked that parsers were released for Wikicode before the issue of specifying a grammar for it was properly addressed, but then I am/was a theoretician first and foremost. Fairflow 10:17, 10 October 2011 (UTC)

First of all: you're right.

This came from the eternal discussion about the grammar type that generates Wikicode. There are (are least, there were) lots of opinions and lots of people arguing that wikicode was a 'context-sensitive' language, mostly because they do not know what a 'context-sensitive' language is. I tried to put some light on the topic when I wrote that section, but I recognize it seems that I'm trying to argue that Wikicode can be described with a context-free grammar, when, as you very well point, that is out of the question.

Having said that, you are most welcome to do whatever changes you think are necessary to clarify what I did.

Concerning your last paragraph, I also found that surprising. I was also surprised when I got to know that the parser is not implemented with the usual context-free recognizer, but instead... with a series of regular expressions, applied one after the another. At a glance I do not know if that's equivalent to the pushdown automaton required to analyze a context-free language, but anyways. It's C programming, anything can be done.