Now we are getting some where. We will now define a grammar for our language. A grammar is a set of rules for a part of our language. It has four parts: a set of terminals, a set of non-terminals, a set of productions, and a starting string.

The overall set will be the combination of the terminal characters and the non-terminal characters, and the “null character”. Terminals are usually represented by lower case characters and don’t change after they’ve been placed (this will make more since in a bit). They are essentially a final product. Non-terminals are what have to be eliminated in the up coming process. Sometimes, one step in the process will replace a non-terminal with another non-terminal, but in the end, they will be replaced with terminals. The null character is a character that doesn’t really exist. It doesn’t take up a space in the string. It is basically a terminal when you don’t need to replace a non-terminal with anything.

Productions are rules to transform the non-terminals into terminals. They are the rather important part. This is the stuff that is represented in BNF. In this current form, though, the symbols would look different. However, I can’t type an arrow. So I’ll use the BNF symbols as they are easy enough to understand.

Finally, the starting string is a string of symbols, either terminal or non-terminal that will be transformed via the productions into all terminal symbols.

Now, while the symbols in these examples are just character, and while case has a meaning here, that doesn’t mean that it has to remain that way. For instance, if converting from BASIC to C, the BASIC form would be non-terminals and some terminals (like literals and variable names), while the code in C form would be all terminals.

I’ll do some examples of this in part 4, I think. I’m re-reading this post and see how long and confusing it already is. I’ll follow that up with a post actually about BNF.

Before we get into everything, I need to talk a bit about set theory. A set is a collection of things. Makes sense. Most of the time in set theory, we have sets of numbers. The set of all real numbers R. The set of integers N. The set of even integers. That kind of stuff. It makes it easier to explain, and examples in this post will use numbers. However, sets can consists of letters, words, or whatever else we want. This will be important in latter articles.

Lets define a set S. I’m going to use notation like this: S= { 1, 2, 3 }. Notice the curly braces. This helps say that it is a set, and not something else. I could also use S= { 1, 2, 3, …, 10 } which should be understood to mean the numbers 1 through 10. Sometimes it might be written like S={ x | 1<=x<=10 } which would be read as “all numbers x such that 1 is less than or equal to x, is less than or equal to 10″, or just all numbers inclusively between 1 and 10.

Now that we can define a set, lets look at the relations between sets. These rules are interesting and complicated. They are the basis for boolean algebra. But most of them are out of the scope of this lesson. You can look at the union and intersections between sets and also inverses between them.

Union is usually written using something like a U, while the intersection is written similarly, but upside down. However, I can’t quite type that so I’ll be using U and n. If we have two sets, A and B, let A={1, 2, 3, 4, 5} and B={4, 5, 6, 7, 8}. Let our overall set S={1, 2, … 10}. S will be the set of all the numbers we can possibly have in this system. I use it for simplicity.

If we where to look at the intersection between A and B, we would say “A n B” and we’d see {4, 5}. This is what the sets have in common. If we look at the union of A and B, A U B would be {1, 2, 3, 4, 5, 6, 7, 8}, or what they both have.

Also to consider is subsets both A and B are subsets of S. A n B is a subset of both A and B. A U B is a superset of both A and B. In other words, a subset is a set who’s elements are all contained in it’s superset. All the values in A are found in S. Not all the values of S are in A. Not all the values of A are in B, but neither are the values of B all found in A.

One last note about set theory. there is the concept of the inverse. The inverse of A, ~A, is everything that is in our system that isn’t in A. So ~A={6, 7, 8, 9, 10}. This also gives rise to partitions. If you have some sets that do not have anything in common (their intersections equal the null set, or a zero with a slash through it), but their unions come together to form the whole (like S), they are partitions. So if you had A={1, 2, … 5} and B={6, 7, … 10} and S was like before, A and B would be partitions of S.

If you don’t know, I’m good friends with Will B. If you have been following his blog, you’d know he is starting work on a new RAD, similar to my current favorite Realbasic. Anyway, one aspect to making something like this would be to define the language. We can say that we want to use syntax like BASIC. On our high level of understanding, this makes sense. But this doesn’t define the language enough. Computers need rules for everything. Compilers and converters (as this will be at least one of those) need well defined rules for how the language should be formed. But it also can’t be over defined such that you can’t use it as a language.

Now the question is, how do we define the language? We could do it in code. We will end up with it in code, but that isn’t the best way to go because it restricts you to one programming language. A more general form is Backus-Naur Form (BNF). It defines a set of rules for how something should be read. Many programming languages are defined in terms of BNF. Thus any changes are in one common form that can be adapted for any kind of use.

Before I go into BNF, we need to cover what it is based on. BNF is based on a branch of discrete math that deals with formal languages and grammars. Discrete math in general deals with set theory, finite state automata and other weird things.

Therefore, in this series, I’m going to cover some background in discrete math, defining a grammar and thus a language, and on to BNF. I’ll try and keep the math to a minimum, but some of this is going to be in the exact wording of a definition. Thus some things are going to be slightly confusing. Feel free to ask questions. I’m going to be pulling lots of info from wiki and from my discrete math notes and text book. I’ll try and link to the information as I can.

Ok. I went though about 90% of the pages on the site, and validated them thanks to the handy xhtml validator. That took some time, but nothing changed visually. That’s update 1. Nothing big.

The next thing you may notice is that I completely butchered  the wordpress theme. I put my header back in place, and changed the fonts around. If you see problems, let me know.

Finally, now that Wordpress looks mostly like my site as a whole, I want to know what people think about me moving most of the content over to wordpress. It would mean the pages looking rather different. I don’t know if I could have the tables like I’ve had for everything, but I would try and keep things similar. I would also try and separate out site news from other posts for the front page. The content pages would be in the form of WordPress pages, which are more static than posts like this. The downside would be the visual changes, and me not knowing if I can separate out posts like I want. If I don’t move stuff, the blog will continue to look slightly different than the rest of the site.

Let me know what you think about this. Should I go all WordPress, or just leave it at this blog?

I added a new page to the site, detailing my recent school project making Othello. Let me know what you think. I have lots of pictures up there, along with several documents about it.