Given a sentential form in a leftmost derivation, find (predict) the next senetential form in that leftmost derivation. Use one token of lookahead.Let
Predict: Production -> set of terminals Predict(A->alpha) = First(alpha) (+ Follow(A) if alpha can derive the empty string) First: String of terminals and/or nonterminals -> set of terminals First(alpha) = the set of terminals that begin strings derived from alpha Follow: Nonterminal -> set of terminals Follow(A) = the set of terminals that can appear immediately to the right of A in some sentential formIMPORTANT: If (1)A->alpha and (2)A->beta and Predict(1) intersect Predict(2) is not empty, then the grammar is not LL(1). How to make it LL(1)?
A -> alpha beta A -> alpha gamma becomes A -> alpha B B -> beta B -> gammaExample:
<stmt> -> if <exp> then <stmt> <stmt> -> if <exp> then <stmt> else <stmt> becomes <stmt> -> if <exp> then <stmt> <tail> <tail> -> empty <tail> -> else <stmt>(Look how this would be different if it had an END IF at the end.)
A -> A alpha A -> beta_1 ... A -> beta_nCreate a new nonterminal T:
T -> alpha T | epislon now A -> beta_1 T A -> beta_2 T ... A -> beta_n TWhy does this work? Because eventually one of the non-left-recursive productions will have to be applied for A, at which point the start of the derived string will be determined. So if choose A alpha three times, get (((A alpha)alpha)alpha). If the fourth time choose beta_1, now have (beta_1 alpha alpha alpha). Example:
<exp> -> <exp> + <term> | <term> <term> -> <term> * <factor> | <factor> <factor> -> <id> Rewrite to remove left recursion: <exp> -> <term> <exptail> <exptail> -> + <term> <exptail>| epsilon <term> -> <factor> <termtail> <termtail> -> * <factor><termtail> | epsilon