• Convert the grammar to EBNF
• Remove left-recursion: replace N ::= E | NF with N ::= E(F)*
• Left-factor the grammar: replace N ::= EFG | EF’G with N ::= E(F|F’)G
• If N ::= E is not recursive, remove it and replace all occurrences of N in the grammar with E

First the grammar is converted to EBNF. The resulting grammar must have a single production rule for each non-terminal symbol. Next, rules containing left recursion are transformed to rules which do not contain left recursion. Left recursion occurs when the same non-terminal appears both at the head of the rule and as a left-most symbol on the right-hand side. The parser can enter an infinite loop if this transformation is not done. Mutual recursion must also be eliminated but it is more difficult. Next, the grammar is simplified by replacing non-terminals with their defining body. This should be done bottom up, stopping when recursion is encountered. Finally, simplify the grammar by factoring the right-hand sides. This makes it easier for the parser to select the correct grammar rule.

The first and follow sets are used by the parser to select the applicable grammar rule. The rule below summarizes the rules for computing the First and Follow sets.

First[E] and Follow[N]