Why do regular expressions have not enough power to express syntax of programming languages?

Answer 1

Because programming languages contain recursive structure, which cannot be represented by a regular expression.

To give an example, most computer programs will have arithmetic expressions with matched parentheses:

E --> F

E --> E operator F

F --> number

F --> lparen E rparen

This very simple grammar cannot be represented by a regular expression.

Proof:

Suppose that there were a regular expression for a language of matched parentheses. Let the length of the regular expression be m. Consider the string (m+1)m+1. This is in the language. Since the first half of the string is longer than the regular expression itself, it must avail of a star somewhere in the first half. Suppose this star was used to repeat n times a substring of length k. The same regular expression could be used to represent a similar string in which the substring of length k was repeated n+1 times. This means that the regular expression would also match the string (m+1+k)m+1 which is not in the language. Thus, the assumption that the language could be represented by a regular expression is false.