2
$\begingroup$

I'm trying to understand how the syntax of some programming language is defined.

I know that there are some parts of the syntax of programming languages that can't be defined using regular expressions (such as an equal number of opening and closing braces) and that this is why context-free languages like BNF are needed.

What I'm struggling to understand is how one can tell which parts of the syntax of a language can only be defined using BNF and which parts could also be defined by a regular expression.

At the moment I think only BNF productions that are recursively defined can't be written as a regular expression. For example I think the following BNF can't be written as a regular expression:

<variable> ::= <letter> | <variable> <letter> | <variable> <digit>

But I think this BNF can be defined using a regular expression:

<digit> ::= 0|1|2|3|4|5|6|7|8|9

My problem with this is that I think I can write a regular expression for a recursive BNF production like this:

<word> ::= <letter> | <word> <letter>

<letter> ::= A|B|...|Z

(I'm assuming a letter is a character A-Z)

I would be greatly appreciative if someone could clarify how this works for me.

$\endgroup$
  • $\begingroup$ if { <stmt> } $\endgroup$ – Raphael Jan 9 '18 at 16:50
  • 3
    $\begingroup$ "What I'm struggling to understand is how one can tell which parts of the syntax of a language can only be defined using BNF and which parts could also be defined by a regular expression." -- this may be an ill-posed question. Oftentimes, it's only that the whole of things can't be expressed in a model, but you can't point at a single thing that causes that. $\endgroup$ – Raphael Jan 9 '18 at 16:51
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your detailed response. So with my word example, I can write a regular expression which would define the same language but would be equivalent to a different, regular BNF because the non-regular BNF I've written only contains one recursive non-terminal? $\endgroup$ – Robert Nixon Jan 12 '18 at 10:00
  • $\begingroup$ ... and because that recursion is regular "in nature": it always has the nonterminal at the start, and the rest of the rule is something that can only generate a finite number of strings. $\endgroup$ – reinierpost Jan 12 '18 at 11:31
2
$\begingroup$

Another example of a non-regular language rule can be found in C. The 4 tokens x * y ; can be parsed as a pointer definition or a multiplication. The correct parse depends on meaning of x. When x denotes a type, it's a definition, and when x denotes a variable, it's a multiplication. But to distinguish the two, you need to perform a "lookup" process , which can't be expressed in a grammar (regular or otherwise).

[edit] Obviously the 4 tokens x * y; are an error when x is neither a type nor a variable, or a variable which can't be multiplied.

$\endgroup$
  • 1
    $\begingroup$ Whether x is a variable, a type, or undefined is determined by the preceding C code; hence, it is a syntactic (non-context-free) property. $\endgroup$ – reinierpost Jan 12 '18 at 14:37
0
$\begingroup$

Pretty much all of it.

It's actually more useful to ask the inverse question: What parts of a programming language can be defined using regular expressions?

Terminal Tokens. This is why parser generators and similar tools usually give you regular expressions for defining terminals. String literals and interpolation tend to get a little complicated, but can usually be broken down into a few grammar rules when they don't fit into a regular grammar.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.