Algorithms for Compiler Design: RIGHT LINEAR AND LEFT LINEAR GRAMMAR

1 Right Linear Grammar

Right linear grammar is a context-free grammar in which every production is restricted to one of the following forms:

1. A → wB

2. A → w, where A and B are the nonterminals, and w is in T *

Since w is in T *, w can also be a single terminal; hence, every regular grammar, by default, satisfies this requirement of a right linear grammar. Therefore every regular grammar is a right linear grammar. Similarly, when | w | > 1, productions containing w on the right side can be split into more than one production. Each contains only one terminal and only one nonterminal on the right side by using additional nonterminals, because w can be written as ay, where a is the first terminal symbol of w and y is string made of the remaining symbols of w. Therefore, a production A → wB can be split into the productions A → aB₁ and B₁ → yB without affecting the language generated by the grammar. The production B₁ → yB can be further split in a similar manner. And this can continue until | y | becomes one. A production A → w can also be split into the productions A → aB₁ and B₁ → y without affecting the language generated by the grammar. The production B₁ → y can be further split in a similar manner, and this can continue until | y | becomes one, bringing the productions into the form required by the regular grammar. Therefore, we conclude that every right linear grammar can be rewritten in such a manner; every production of the grammar will satisfy the requirement of the regular grammar. For example, consider the following grammar:

The grammar is a right linear grammar; the production S → aaB can be split into the productions S → aC and C → aB without affecting what is derived from S. Similarly, the production S → ab can be split into the productions S → aD and D → a. The production B → bb can also be split into the productions B → bE and E → b. Therefore, the above grammar can be rewritten as:

which is a regular grammar.

2 Left Linear Grammar

Left linear grammar is a context-free grammar in which every production is restricted to one of the following forms:

1. A → Bw

2. A → w, where A and B are the nonterminals, and w is in T *

For every left linear grammar, there exists an equivalent right linear grammar that generates the same language, and vice versa. Hence, we conclude that every linear grammar (left or right) is a regular grammar. Given a right linear grammar, an equivalent left linear grammar can be obtained as follows:

1. Obtain a regular expression for the language generated by the given grammar.

2. Reverse the regular expression obtained in step 1, above.

3. Obtain the regular, right linear grammar for the regular expression obtained in step 2.

4. Reverse the right side of every production of the grammar obtained in step 3. The resulting grammar will be an equivalent left linear grammar.

For example consider the right linear grammar given below:

The regular expression for the above grammar is obtained as follows. Replace the → by = in the above productions to obtain the equations:

Solving equation (II) gives:

By substituting the value of B in (I), we get:

Therefore, the required regular expression is:

And the reverse regular expression is:

The finite automata accepting the language specified by the above regular expression is shown in Figure 1.

Figure 1: Finite automata accepting the right linear grammar for a regular expression.

Therefore, the right linear grammar that generates the language accepted by the automata in Figure 1 is:

Since C is not useful, eliminating C gives:

which can be further simplified by replacing D in B → 1D, using D → 0 to give:

Reversing the right side of the productions yields:

which is the equivalent left linear grammar. So, given a left linear grammar, an equivalent right linear grammar can be obtained as follows:

1. Reverse the right side of every production of the given grammar.

2. Obtain a regular expression for the language generated by the grammar obtained in step 1, above.

3. Reverse the regular expression obtained in the step 2.

4. Obtain the regular, right linear grammar for the regular expression obtained in the step 3.

The resulting grammar will be an equivalent left linear grammar. For example, consider the following left linear grammar:

Reversing the right side of the productions gives us:

The regular expression that specifies the language generated by the above grammar can be obtained as follows. Replace the → symbols with "=" symbols in the productions of the above grammar to get the following set of equations:

From equation (II), we get:

Substituting this value in (I) gives us:

Therefore,

and the regular expression is:

The reversed regular expression is:

The finite automata that accepts the language specified by the reversed regular expression is shown in Figure 2.

Figure 2: Transition diagram for a finite automata specified by a reversed regular expression.

Therefore, the regular grammar that generates the language accepted by the automata shown in Figure 2 is:

which can be reduced to:

which is the required right linear grammar.

EXAMPLE 1

Consider the following grammar to obtain an equivalent left linear grammar.

The regular expression for the above grammar is obtained as follows. Replace the → by = in the above productions to obtain the equations:

By substituting (III) in (Il) we get:

Therefore, A = (a | gg)A | g and A = (a | gg)*g. By substituting this value in (I) we get:

And the regular expression is:

Therefore, the reversed regular expression is:

But since (a | gg)* is the same as (gg | a)*, the reversed regular expression is same. Hence, the regular, right linear grammar that generates the language specified by the reversed regular expression is the given grammar itself. Therefore, an equivalent left linear grammar can be obtained by reversing the right side of the productions of the given grammar: