Currently, I’m enrolled in the Logic in Computer Science course at Bits Pilani. One of the most important concepts in this course is that of grammars. The concept is not too difficult to understand but I found it really confusing at first. This was partly because it was a completely new concept, but mainly because I was refusing to open up to this way of thinking. Once you start accepting it, it is quite easy to understand and almost intuitive.

The word “grammar” is regularly used to refer to the rules making up our natural languages.

For example, consider the sentence:

	The boy rode a horse.

The things I can imply from this sentence are:

  • The subject is the boy
  • The object is the horse
  • The verb is rode which is in the past tense

  • The sentence consists of the above terms which makes it meaningful

    For example, the sentence: The boy rode would not make to much sense without a context.

All these conclusions give us an idea of how the English language works. Of course, the above example is given considering natural languages. The concept of grammars can be extended to logics and artificial languages (programming languages).

A few things to keep in mind:

  • The rules in a grammar must be in the order of lowest to highest precedence of operators.
  • The first rule in our grammar must be the one with the operator of lowest precedence. Any formula following this grammar must ultimately reach this term when simplified.
  • The rules must comply with the operator preference order which must be decided before writing a grammar.
  • Associativity must be followed

$ \ $

Associativity

Basically, associativity of operators allows us to always solve an equation in a specific order for a particular operator. Thus, associativity is broadly classified into the following:

Right associativity

This means that an expression is simplified from the right hand side when faced with multiple occurences of the same operator.

Left associativity

The expression is simplified from the left.

Let’s consider a simple arithmetic equation:
$3 + 4 \times 5$.

Without any given precedence order, this can be solved in one of two ways:

  1. Doing the addition before the multiplication: resulting in:

    $7 \times 5 = 35$

  2. Or the conventional method, where multiplication is given a higher preference than addition. This would result in:
    $3 + 20 = 23$

Let’s assign a preference order for all the operators involved (+ and * in this case). To make it easier to understand, we’ll use the same preference order as defined by BODMAS, that is, multiplication is done before addition.

Thus, in a way, one could write: $\times > +$

$ \ $

Basic rule

Now, lets define a term $X_{num}$, which represents a number. Thus, 3, 4 and 5 can be represented by $X_{num}$. This rule allows us to classify any “number” as $X_{num}$. This, is not necessary for basic grammars.

$ \ $

Multiplication rule

Let me represent a product term ($num \times$ some_other_term) using $X_{product}$.

Thus,
$X_{product} \rightarrow X_{num} \times X_{product}$.

Let me explain the above rule. Consider the equation: $3 \times 4 \times 20$. Let us consider the multiplication here being left associative. Thus, we could solve $3 \times 4$ first. Hence, our equation can be simplified to a product term ($3 \times 4$) multiplied by a number term, which is $20$. From our previous rule, a number ($num$) can be represented using $X_{num}$. And of course, a product term is represented by $X_{product}$. This, brings us back to our rule, $X_{product} \rightarrow X_{num} \times X_{product}$.

What this means is that while generating an equation using my grammar rules, I can break a product term ($X_{product}$) into a product term ($X_{product}$) multiplied by a non-product term ($X_{num}$).

$ \ $

Addition rule

Moving on to the next lowest operator, which is addition (+).

Suppose I have an arithmetic equation with several additions, say:
$10 + 20 + 30$.

Then, I can solve this in two ways (both right and left associativity), though I’d end up with the same answer, since addition satisfies the associative property.

Let me represent a term consisting of two numbers and a + operator with $X_{addition}$ Examples of this would include: $3 + 4, -12 + 32$, etc.
$X_{addition}$ can also represent terms involving a product, like
$3\times4 + 5$.
Though a bit difficult to understand, consider it this way: I can split a sum into two terms which definitely don’t include any operator with a preference lower than $+$ Thus we have:
\(X_{addition} \rightarrow X_{product} + X_{addition}\).

$ \ $

Other Rules

To recap, we have 3 rules now (in no particular order as of now):

$X_{num} \rightarrow num$
$X_{product} \rightarrow X_{num} \times X_{product}$.
$X_{addition} \rightarrow X_{product} + X_{addition}$

$ \ $
But, I have forgotten 2 very basic rules which will become apparent soon. One of the most basic intuitive meaning of a grammar is that one should be able to simplify and formula using the right grammar to a most basic unit. For example, consider the equation: $5$. Now, using the first rule I created, 5 can be replaced with $X_{num}$. But, our grammar also includes the terms $X_{addition}$ and $X_{product}$, which are higher up in the grammar, meaning that our formula must end up being represented by the highest term.

Thus, any $X_{num}$ is also a $X_{product}$ and any $X_{product}$ is also a $X_{addition}$.

$X_{product} \rightarrow X_{num}$ $X_{addition} \rightarrow X_{product}$

Adding the two rules, our grammar becomes:

  1. $X_{addition} \rightarrow X_{product} + X_{addition}$
  2. $X_{addition} \rightarrow X_{product}$
  3. $X_{product} \rightarrow X_{num} \times X_{product}$.
  4. $X_{product} \rightarrow X_{num}$
  5. $X_{num} \rightarrow num$

But, we are not done yet. A grammar looks nice and sophisticated on paper, but it has little purpose if it does n’t allow us to parse or generate a formula properly. Lets try this: Of course, the simplification must occur using the order of preference of the operators because the very grammar has been defined in that way (product is higher preference than addition).

$11 \times 4 + 3 \times 7$ Given expression
$X_{num} \times 4 + 3 \times 7$ rule 5
$X_{num} \times X_{num} + 3 \times 7$ rule 5
$X_{num} \times X_{product} + 3 \times 7$ rule 4
$X_{product} + 3 \times 7$ rule 3
$X_{product} + X_{num} \times 7$ rule 5
$X_{product} + X_{num} \times X_{num}$ rule 5
$X_{product} + X_{num} \times X_{product}$ rule 4
$X_{product} + X_{product}$ rule 3
$X_{product} + X_{addition}$ rule 2
$X_{addition}$ rule 1

Thus, this expression could successfully be parsed using the above grammar. A grammar is correct only if it works for every expression following that grammar.