Grammars and regular expressions are both ways to describe a language. Grammars are far more powerful. Context-free grammars are restricted grammars, with less power; regular grammars are further restricted context-free grammars, with less power again.
Regular grammars can describe exactly all regular languages, that is, all languages that can be described by regular expressions.
(Side note: this is only true for the regular expressions taught in computer science, which only use concatenation, union and Kleene star. In programming practice, extended types of regular expressions tend to be used with much more power.)
Regular grammars can be recursive, but only in a very restricted way:
- each right hand side of a rule has at most one nonterminal
- that nonterminal is either always at the end of a rule (for right-regular grammars) or always at the start (for left-regular grammars)
In your example:
<variable> ::= <letter> | <variable> <letter> | <variable> <digit>
<letter> ::= a | b | c | ...
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
the first rule isn't regular, but it only contains one recursive nonterminal: <letter> and <digit> both generate a finite set of strings. Hence, we can expand them into the rule to yield the equivalent set of rules
<variable> ::= A | B | ... |
<variable> A | <variable> B | ... |
<variable> 0 | <variable> 1 | ...
which is (left-)regular.
Hence, a regular expression for <variable> exists:
(a | b | c | ...)(a | b | c | ... | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)$^*$
There are, in fact, straightforward algorithms for converting regular expressions to regular grammars and vice versa.
So context-free grammars can only generate non-regular languages by containing either right-hand sides with material on both sides of a nonterminal, for instance,
<block> :== { <statements> }
or rules with multiple "recursive" nonterminals (i.e. of which more than one generates an infinite language).
If they do contain such rules, the language described may still be regular, and it can be really hard to figure out whether it is (it is undecidable).
However, we weren't looking at a grammar and trying to see whether it describes a regular language; we were looking at a language and trying to see whether it is regular.
A general rule I think you may find most useful in practice is to determine whether you can decide whether an utterance (in the case of a programming language: a program) belongs to the language by scanning it from left to right while never remembering more than a constant amount of information. The syntax is regular if and only if you can do this.
In practice, you usually see two forms of recursion in languages:
- a construct may contain another construct repeated an arbitrary number of times: this is regular;
- a construct may contain occurrences of itself nested (that is, with some form of brackets to indicate the nesting) arbitrarily deeply: this is not regular, but context-free.
To take C as an example:
- a block opens with a
{ character, followed by arbitrarily many (possibly empty) statements, separated by ;, and ends with }: this is regular, except that
- a statement may itself be a block; thus, blocks can be nested inside blocks arbitrarily deeply: this is not regular.
JSON isn't a regular language for the same reason.
It isn't regular because the { and } brackets must match up, and while scanning from left to right, it isn't possible to determine this unless you somehow keep track of how many more { brackets you've seen than } brackets, and this count can be arbitrarily high: no constant amount of information can contain it.
Granted, in practice, you will rarely see C programs or JSON structures with blocks nested more deeply than, say, MAXINT times; but in theory, you may, which makes C syntax and JSON syntax non-regular.
I hope this gives you some intuition on how to distinguish regular from non-regular context-free languages in practice. It must be added that many requirements on the syntax of programming languages aren't even context-free: for instance, requiring variables to be defined before they are used is not.
if { <stmt> }$\endgroup$