-1

I'm writing some static analysis tools and have been trying to avoid doing full-on compilation style string parsing, and that brought me to this question.

Is C# a regular language?

Why or why not?

Codeman
  • 12,157
  • 10
  • 53
  • 91
  • 1
    Just in case you've missed http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/ - good read... And it is for much simple language by the way. – Alexei Levenkov Feb 28 '17 at 04:38
  • or have a look at https://github.com/dotnet/roslyn/wiki/Getting-Started-C%23-Syntax-Analysis – Keith Nicholas Feb 28 '17 at 04:41
  • @AlexeiLevenkov, that's a classic answer and an entertaining one, but it doesn't answer this question, nor does it touch upon the reasons for this answer. – Thom Smith Feb 28 '17 at 04:43
  • @ThomSmith serious part actually contains main part of the answer - http://stackoverflow.com/a/1758162/477420 (context free > regular) + some basic search (http://stackoverflow.com/questions/13428934/is-c-sharp-considered-a-context-free-language or rare common sense) will give the real answer ... Can't close as duplicate of both so... – Alexei Levenkov Feb 28 '17 at 04:50
  • 2
    Use Roslyn if you need a C# parser and semantic analyzer. Don't re-invent the wheel. – Eric Lippert Feb 28 '17 at 05:14
  • 1
    Incidentally, C# is not even a *decidable* language; it was recently proved that languages with nominal subtyping and contravariant interfaces are not decidable. Even leaving aside that, overload resolution is at least NP-HARD. – Eric Lippert Feb 28 '17 at 05:18
  • C# *type checking* is not decidable. But parsing is. C# isn't Perl, after all. Also, are you referring to the result by Kennedy & Pierce, or something more recent? – Thom Smith Feb 28 '17 at 05:30
  • 1
    @ThomSmith: A C# program that does not type check is not a legal C# program. If the question is *is the language C# without type checking* decidable, yes it is, but that is not C#. The question is about C#. – Eric Lippert Feb 28 '17 at 06:29
  • @ThomSmith: The paper you're referring to conjectures that it is undecidable but does not prove it; a recent paper proves it. Funnily enough, the author of that paper learned of the conjecture from one of my SO answers, which I find quite amusing! The paper is "Java Generics Are Turing Complete" by Radu Grigoire. – Eric Lippert Feb 28 '17 at 06:31
  • Now, if you are interested in just C# as she is parsed, fun fact: the language can in theory require arbitrary far look-ahead to parse correctly, due to some ambiguities introduced by generics. In practice these scenarios don't arise often. – Eric Lippert Feb 28 '17 at 07:05
  • Why reinvent the wheel: http://stackoverflow.com/questions/38635/what-static-analysis-tools-are-available-for-c – Ivan Kishchenko Mar 01 '17 at 13:00

1 Answers1

6

No. C# is not a regular language. C# lets you nest parentheses arbitrarily deep, and a regular language cannot recognize correct bracket matching. This, by itself, means that C# is not regular.

Thom Smith
  • 13,916
  • 6
  • 45
  • 91