Preprocessing Steps Required for Predictive Parsing

Preprocessing steps for predictive parsing are,

• Removing the left recursion from the grammar
• Performing left factoring on the resultant grammar
• Removing ambiguity from the grammar

Removing the left recursion from the Grammar

                Given grammar,

                B → B and B

                B → B or

                B → (B) | true | false

Let the given grammar be,

                B → B and B | true

                B → B or B | false

                B →(B)

Therefore, the given grammar in left recursive, removing left recursion from the grammar

Performing Left Factoring on the resultant grammar

                For the grammar,

                A  → Aα| B

                The productions are

                A →  βA'

                A' → A' | ε

Therefore we have,

                B  → true B’

                B’ → and B B’| ε

                B’ → false B’

                B’ → or BB’ | ε

                B → (B)

i.e., B → true B’ | and d BB’ | false B’ | or BB’ | (B) | ε

The above grammar contains repetitions of the symbol, therefore, performing left factoring on it.

Removing Ambiguity from the Grammar

We know that for the grammar

B → β𝜆1 | β𝜆2 | β𝜆3 …….. | β𝜆v | α

We have the productions

B → 𝜆1 | 𝜆2 | 𝜆3 ……… 𝜆v

Therefore

B → B1B0 | (B) | ε

B0 → true | and B | false | or B

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.