Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 7 down vote favorite
1

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

share|improve this question
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 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 at 8:00
Even regex aren't regular anymore – CodesInChaos Feb 9 at 14:09

1 Answer

up vote 27 down vote

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).

share|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 at 1:56
@ratchet freak: How would you handle the parentheses, e.g. in (1 + 2) * 6? – Giorgio Feb 9 at 10:05
@Giorgio I should have added "without parenthesis" – ratchet freak Feb 9 at 12:37
@ratchet freak: Yes, you can find a suitable definition of what a numeric expression is so that, according to your definition, numeric expressions form a regular language. – Giorgio Feb 9 at 14:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.