Chapter 8 - Transformations of Context-Free Grammars

Question 1

What are equivalent grammars?

Answer 1

Grammars are equivalent if the languages they represent are exactly equal

Question 2

What are useless productions’ properties?

Answer 2

Unreachable - there is no other production that can reach this one, thereby making it impossible to do anything with
Unproductive - A production that basically gets stuck in an infinite loop i.e. B -> bB

Question 3

When removing a useless production, what do you do?

Answer 3

Remove it from ALL instances where it is used or ‘called’ i.e.
S -> AB | A
B -> bB
Removing B will result in this:
S -> A

Question 4

What is substitution in respect to productions?

Answer 4

Substitution is exactly as it sounds, you take a production, and replace its value with the production result i.e. A -> XBY
B -> C | D
After substitution, the result would be this:
A -> XCY | XDY

Question 5

What is left factoring in respect to productions?

Answer 5

Left factoring involves replacing certain ‘common prefixes’ of a production with another one. To explain with an example:
A -> XYX | XYZZY
After left factoring, the result can look like this:
A -> BYX | BZZY
B -> XY

Question 6

When making a CFG unambiguous, what does operator precedence mean?

Answer 6

Operator precedence means that for each operator within a production, you have an order of what takes more precedence, instead of just leaving it so that all operators are of the same precedence.

Question 7

When eliminating left-recursion, what do you do?

Answer 7

Eliminating left recursion requires you to follow a couple of steps. First, select the non-terminal defined by left recursion. Then, split it into A and A’, whereby A looks like this - A -> (beta)A’
And A’ looks like this:
A’ -> (alpha)A’ | epsilon
Example:
A -> A(alpha)
A -> beta
It would then turn into this:
A -> (beta)A’
A’ -> (alpha)A’ | epsilon