Computational grammar is a subject that is sometimes viewed as a form of torture by computer science students, but understanding something about it really does help ....

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem ***NEW!
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

This chapter is a slight detour from the subject of what is computable. We have discovered that different types of computing model are equivalent to different types of grammar and the languages they produce. What we haven’t looked at so far is the impact this practical problem has had on theoretical computer science. Many hours are spent studying grammar, how to specify it and how to use it. What is often ignored is what practical relevance grammar has to the meaning of a language? Surely the answer is none whatsoever! After all, grammar is about syntax and semantics is about meaning. This isn’t quite true. A grammar that doesn’t reflect meaning is a useless theoretical construct.

There is an argument that the arithmetic expression is the whole reason that grammar and parsing methods were invented, but once you have the theory of how to do it you might as well use it for the entire structure of a language.

Backus-Naur Form - BNF

In the early days of high-level languages the only really difficult part was the translation of arithmetic expressions to machine code and much of the theory of grammar was invented to deal with just this problem. 

John Warner Backus
1924 - 2007

At the core of this theory, and much used in the definition of programming languages, is BNF, or Backus Normal Form. Because Donald Knuth pointed out that it really isn't a normal form in the sense of providing a unique normalized grammar it is often known as Backus-Naur Form after John Backus the inventor of Fortran and Peter Naur one of the people involved in creating Algol 60. Fortran was the first "high level" computer language and its name derives from FORmula TRANslation. The intention was to create a computer language that would allow programmers to write something that looked like an arithmetic expression or formula. For example, A=B*2+C is a Fortran expression. Working out what exactly had to be done from a formula is not as easy as you might think and other languages ducked the issue by insisting that programmers wrote things out explicitly - "take B multiply it by two and add C". This was the approach that the language Cobol took and it was some time before it added the ability to use formulas.

Not only isn't Backus Normal Form a normal form, there isn't even a single standard notation for BNF, and everyone feels free to make up their own variation on the basic theme. However, it is always easy enough to understand and it is very similar to the way we have been describing grammar to this point.

For example, using "arrow notation" you might write:

<additive expression> -> <variable> + <variable>

You can read this as saying that an additive expression is formed by taking a variable, a plus sign and another variable.

You can read this as saying that an additive expression is formed by taking a variable, a plus sign and another variable. This rule only fits expressions like A+B, and not A+B+C, but you get the general idea.

Quantities in angle brackets like

<additive expression> 

are called “non-terminal” symbols because they are defined by a BNF rule and don’t appear in the final language. The plus sign on the other hand is a “terminal” symbol because it isn't further defined by a BNF rule.

You might notice that there is a slight cheat going on in that the non-terminal <variable> was replaced by a terminal in the examples, but without a rule allowing this to happen. Well, in proper BNF, you have to have a rule that defines every non-terminal in terms of terminal symbols, but in the real world this becomes so tedious that we often don’t bother and rely instead on common sense. In this case the missing rule is something like:

<variable> -> A|B|C|D etc .. |Z

where the vertical bar is read as “OR”. Notice that this defines <variable> as just a single character - you need a slightly more complicated rule for a full multicharacter variable name.

If you want to define a variable that was allowed to have more than a one-letter name you might use:

1 <variable> -> <variable> <letter> | <letter>
2 <letter> -> A|B|C|D etc .. |Z

This is the BNF equivalent of a repeating operation. It says that a variable is either a letter or a variable followed by a letter. 

For example, to use this definition you start with:

<variable>

and use rule one to replace it by:

<variable><letter>

then use rule two to replace <letter> by A to give:

<variable>A

Next we use the first rule to replace <variable> to get:

<variable><letter>A

and so on building up the variable name one character at a time.

Boring isn’t it?

But it is an ideal way to tell a computer what the rules of a language are.

Just to check that you are following – why does rule 1 include the alternative

|<letter> ?

The reason is that this is the version of the rule we use to stop a variable name growing forever, because once it is selected the next step is to pick a letter and then we have no non-terminals left in the result. Also notice that the BNF definition of a variable name cannot restrict its length. Rules like “fewer than 8 characters” have to be imposed as notes that are supplied outside of the BNF grammar.