Is Mediawiki markup context-sensitive?

Question

There seems to be disagreement over whether MediaWiki markup (the markup language used to create and edit Wikipedia articles) is context-free or context-sensitive.

See http://www.mediawiki.org/wiki/User_talk:Kanor#Response_to_article_in_Meatball

I would argue that it is obviously context-sensitive. One example of this would be terminal characters in wikimarkup lists. Lists are formed like:

* One thing
* Another thing
* Yet another thing

The end of a list item is indicated by a carriage return.

However, if the list is nested in, say a table or transclusion, then the end of a list item may either be a carriage return, or a table/transclusion terminal symbol. For example, the following seems to be valid markup:

{{Infobox person
* One thing
* Another thing
* Yet another thing}}

However, a parser would need to keep track of the context, e.g. the fact that it is currently nested within a transclusion, when it encounters the }} symbol, instead of an end-line (carriage-return) character, when determining the end of the last list item.

So... how is this possibly not context-sensitive?

Answer 1

"Context-sensitive" has a precise formal definition, and it does not appear to match your intuition. The grammar

S -> P | E
P -> '(' T '.' ')'
E -> '[' T '!' ']'
T -> <any context-free grammar fragment>

is context free (even regular, if T is regular), despite the fact that what comes after T (dot/exclamation mark) depends on the first character: There are no "context non-terminals" on the left hand side. Even arbitrary nesting isn't a problem:

S -> A | B
A -> '(' S ')'
B -> '[' S ']'

The parser has to remember which unmatched opening braces it has seen so far, but it does not need context in the sense of context-free/-sensitive grammars. These particular grammars aren't even ambiguous (again a formal term, also used in the Wiki user page you link to). Context free does not mean "parser needs no working memory", or equivalently "parser can be restricted to look at every single token in complete isolation".