Copyright © 2006 Gradiance Corporation.

 

 

     

Manipulating Grammars

 

 

 

Left-factoring and eliminating left recursion.

 

1.  

Here is a left-recursive grammar: 

 
S → Sa | Sb | c | d
 

Use the standard construction in Section 4.3.3 (p. 212) to eliminate left recursion by introducing a new variable S'. Which of the following would be a production of the new grammar?

 

 

 

 a) 

S' → a

 

 b) 

S' → ε

 

 c) 

S' → aS

 

 d) 

S' → bS

 

 

 

 

 

2.  

Here is a grammar to be left factored using the standard construction of Section 4.3.4 (p. 214): 

 
S → AaS | AaA
A → a | ab
 

Left factor this grammar, introducing variables S' to "help" S and A' to "help" A. Then, identify in the list below, the one production that is NOT in the left-factored grammar.

 

 

 

 a) 

A' → ε

 

 b) 

S → AS'

 

 c) 

S → AaS'

 

 d) 

S' → S

 

 

 

 

 

3.  

Here is a left-recursive grammar: 

 
S → SaS | b
 

Eliminate left recursion from this grammar by using the standard construction from Section 4.3.3 (p. 212) that introduces a "helper" variable S'. Which of the following is one of the productions of the new grammar?

 

 

 

 a) 

S → bS'

 

 b) 

S → b

 

 c) 

S → ε

 

 d) 

S' → b

 

 

 

 

 

4.  

Sometimes, when we left factor, there are several prefixes that occur in two or more production bodies for the same variable. If so, the standard factoring algorithm from Section 4.3.4 (p. 214) begins by choosing the longest of these prefixes, which therefore occurs in the fewest of the production bodies. After factoring out that prefix, we will find another opportunity to left-factor, using a shorter, but nonempty, prefix. We continue factoring, until no nonempty common prefixes remain. Here is a grammar: 

 
S → 0SS1S | 0SS0S | 01 | 1
 

that illustrates this situation. There are two common prefixes, 0 and 0SS. Transform this grammar to an equivalent grammar that has no two production bodies for the same variable with a nonempty common prefix. When you have to introduce new variables, introduce S', S'', S''', and so on, in that order. Then, identify from the list below the production that appears in your final grammar.

 

 

 

 a) 

S → 0SSS'

 

 b) 

S → 0S''

 

 c) 

S → 1S'

 

 d) 

S'' → 1S