9

Are C or C++ regular languages? If not, under which category do we place the programming languages like C/C++, perl, Python?

  • No, egrep is a regular language; C is not. – tchrist Feb 19 '12 at 15:34
  • Most programming language are some sort of context free language. This is why they are usually represented as tree during compilation. en.wikipedia.org/wiki/Context-free_grammar – Laurent Bourgault-Roy Feb 9 '13 at 2:38
  • 1
    @LaurentBourgault-Roy I'd think most weren't even context free as even if they have a CFG there are usually additional rules applied outside the CFG – jk. Feb 9 '13 at 8:00
  • Even regex aren't regular anymore – CodesInChaos Feb 9 '13 at 14:09
31

The only universal definition I know of for "regular language" is one that can be parsed with a deterministic finite automaton, or expressed as a true regular expression (not the extended REs in many current implementations). A regular expression can be written in a series of characters, with potentially infinite repetitions and alternate selections.

Since both C and C++ allow nesting of braces, brackets, and parentheses to arbitrary depths, they aren't regular languages (check out the Pumping Lemma for details).

| improve this answer | |
  • 2
    I would add that no programming language of any use can be regular because it wouldn't even allow any kind of numeric expressions. – Giorgio Dec 3 '11 at 23:55
  • 1
    @Giorgio you can express a numeric expression as a regular language (an alternating sequence of operator and number beginning and ending with a number) parsing (with priorities) them needs a grammar though – ratchet freak Feb 9 '13 at 1:56
  • @ratchet freak: How would you handle the parentheses, e.g. in (1 + 2) * 6? – Giorgio Feb 9 '13 at 10:05
  • @Giorgio I should have added "without parenthesis" – ratchet freak Feb 9 '13 at 12:37
  • 1
    @Giorgio: It is trivially true that syntactically correct postfix expressions do not form a regular language. No matter. A language can be both regular and arbitrarily expressive, including postfix expressions, as long as stack checking is deferred until runtime. Forth is an excellent example, and dc would be another. – david.pfx Jun 2 '14 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy