File LanguageDesign.html    Author McKeeman    Copyright © 2007    index

General Advice

The X language is an example of design. The credit for the good ideas goes to Edsger Dijkstra. It is in the nature of the material presented here, and the ambitions of those mastering it, that soon enough more language design is going to take place, in the form of extending X to a specific problem domain.

There is an extensive body of knowledge and set of examples on how to make bad designs. The point of this page is to help the reader avoid the known pitfalls.

C. Anthony R. Hoare wrote a technical note Hints on Programming Language Design in 1973. The copy here is from a scanned technical report published at Stanford. The copy is not pretty, but that does not detract from its wisdom. A quote: "A necessary condition for the achievement of any of these objectives is the utmost simplicity in the design of the language."

Here are my personal vision statements in 1966 and 2004.

Here are my thoughts on notation as a programming language.

Avoiding Trouble

If you have trouble figuring out the meaning of some program text, it is likely that the compiler will also have trouble. Since everything in language procesing proceeds from left-to-right, you must insure that looking at the next thing makes it easy to decide what to do. It is a bad idea to use a particular symbol in two different places in the grammar unless you are quite sure you will never be in a situation where either one or the other might be the next thing. If you get in such a spot, you will have to look ahead for further clues. Once is awhile this is OK, but it can turn a fast compiler into a performance dog if it is wasting time peeking when a good language designer could have given an unambiguous form.

At worst, you can design a grammar that can treat source text two different ways. This in fact happened in early languages like Algol 60. The authors did not realize the implications of their meta formulas. One of the very useful tricks we now have is giving our tentative grammar to an LR parser generator. An ambiguous grammar will surely elicit a diagnostic. Having used the LR generator to test your grammar does not mean you have to use its tables for automatic parsing. But you can.

Arithmetic Precedence

The order of application of operators is usually defined in the CFG. For example, multiplication binds more tightly than addition. In X for instance, * binds more tightly than + because it is more deeply nested in the phrase definitions. The simplest way to understand this use of grammar is to look at the syntax tree for Proposition to see how it expresses the fact that & (meaning logical "and") binds more tightly than | (meaning logical "or").