Take the 2-minute tour ×
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.

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 '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
add comment

1 Answer 1

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 '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
    
@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 '13 at 14:08
show 7 more comments

Your Answer

 
discard

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