Languages Are Defined By A Grammar

intro
prev: Languages and Recognition

To be a language, there must be rules that distinguish what is "in" that language from what is not in the language. If we can distinguish Egyptian hieroglyphs from random doodles, there must be a set of rules that tell us when the pictures are hieroglyphs. Those rules are the grammar.

Technically, the grammar is said to define the language. That is the rules of the grammar say precisely what is in the language and what is not. If the symbols follow the rules laid down by the grammar, they are in the language. If they do not follow the rules, they are not in the language.

Remember that deciding if a set of symbols is in a language is called recognition. Therefore, by applying the rules of the grammar to the set of symbols one can decide if the symbols are recognized by the grammar, and thus are in the language.

Any set of rules which allow you to decide if something is in a language or not is a grammar. However, we are going to concentrate on rules that follow a specific pattern. These rules will be called a formal grammar.

There are rules about what is a formal grammar. We will learn those rules. Since the rules of a formal grammar allow one to distinguish what is a formal grammar from what is not. There is a language of formal grammars and a grammar of formal grammars.

By the way, the rules of what is a formal grammar are quite simple and many people who deal with this topic often at this point quickly just expound the rules and assume that a reader will get the subtleties embodied therein. However, I am going to avoid that and carefully develop the parts of a formal grammar, so that you can see how the parts come together and build complexity.

You can liken this to the way you learned numbers. First one learns to count to ten, then one learns to add, then to count to one hundred, subtract, add two-digit numbers, subtract two-digit numbers, count to a thousand, multiply, recognize numbers by place-value, divide evenly, use fractions, and so on. All despite the fact that the whole of real number arithmetic can be expressed by some simple rules--rules which one only understands by the building up of the parts. I will try to approach this topic the same way.

next: Symbols

Symbols

intro
prev: Languages Are Defined By A Grammar

To recognize if what we are looking at is a language, it needs to be composed of parts. That is things which we can see over and over again and they always are accepted as being the same. We call those parts symbols.

Symbols appear at many levels. As you read this text, you might note that it consists of a series of "pages", each page discussing a specific topic. Within those pages are "paragraphs", and within paragraphs are "sentences", and within sentences are "words", and finally within words "letters". These are symbols because we can name them and distinguish them. Every time you see a letter, you recognize it as such. Same thing for a word, sentence, paragraph, or page. That is what makes those things symbols (and not doodles).

So, part of having a language that we can recognize is the we must be able to turn it into symbols. Parts that we can clearly and consistently identify.

The fact that you can identify this text as containing letter, words, sentences, and so forth, means that this text is composed of symbols.

Thus, in our building up of what a language is, we can see that the rules of a formal grammar are going to allow us to take a text and recognize it by dividing the text up into symbols.

next: Symbols, Tokens, and Terminals