NULL, Recursion and Syntax Diagrams

Alphabets often contain a special symbol, written as NIL or NULL which is an empty symbol. It produces no symbol in the string. For instance, this rule, extracted from a grammar ....

<dipthong> à "A" + NULL + "E"

... would produce the output AE. Similarly, the NULL symbol is used to provide an 'optional' symbol that can be included or not:

<opt punc> à "?" | NULL

In this case, <opt punc> could be a question mark or nothing at all.

Recursion

If a non-terminal symbol is defined rercursively, it means that it is defined in terms of itself. Here is an example of a simple whole number defined recursively:

<number> à <add digit> | <digit>
<add digit> à <number> + <digit>

This has to be examined carefully before it starts to make sense. The symbol <number> is defined as being either a digit (itself defined in some other rule) or something called <add digit>. This is defined as being a number followed by a digit. Effectively, a number is being either a simple digit or another number followed by a digit.

Since a number is now defined essentially in terms of a number, it can produce an almost endless string of digits. The number can be a number(2) followed by a digit, but number(2) can be a number(3) followed by a digit, and number(3) can be a number(4) followed by a digit etc. The process needn't go on forever - at any point, one of the "sub-numbers" somewhere down in the stack can be defined as a single digit.

This underlines an important point about any sort of recursion - there must be a stopping condition built in. Suppose the rules above had been defined as follows:

<number> à <add digit>
<add digit> à <number> + <digit>

In this case, a number is always a number followed by a digit. The definition is never complete, since every time you try to define a number, you end up having to define another number. A grammar like that built into a computer program would cause that program to crash!

Syntax Diagrams

Syntax Diagrams are a pictorial way of representing grammars. They are usually used to define the structures of computer programming languages - for instance, the first syntax diagrams that I came across were used to define sections of standard Pascal.

Syntax diagrams work similarly to flowcharts. You travel along lines including symbols, which are listed in rectangles strung along these lines. When there is a choice of symbols to include, this is shown by a branch in the line. Here, for instance, is the grammar from the first section represented as a sequence of syntax diagrams. Start from the word on the left that you are trying to define, work along in the direction of the arrows and don't stop until you reach the end of the line on the right.

Sentence à <article> + <noun> + <verb>
<article> à "the" OR "a"
<verb> à "jumps" OR "sees" OR "cries"
<noun> à "man" OR "woman" OR "child"

When items need to be chained together, they appear end to end along the line. When there is a choice of items, the line branches and you can take any branch. You can also use syntax diagrams to define structures recursively.

Syntax diagrams give an easy way to specify optional symbols. In the following syntax diagram, both symbols X and Y are optional:

This grammar rule could generate the strings X, Y, XY or an empty string (where both X and Y had been skipped). Similarly, syntax diagrams can specify "one or more" constructions, where a symbol must be included at least once, but can be included any number of times after that ...

... or "zero or more" where a symbol can be included as many times as you like or not at all: