| / F T' | F num | id Consider the grammar Answer: E T + E Hard to predict because for T, two E T productions with int T int T int * T For E, it is not clear how to predict T ( E ) which rule to use What you JUST did is called disjointness test” “pairwise What if the Grammar fails disjointness test? Must to create a predictive parsing grammar left-factor Left-factoring involves rewriting rules so that if a non-terminal has > 1 rule, each begins with a terminal add new non-terminals (new letters) to factor out common prefixes of Left Factoring Example Left factor the grammar below: Answer: S ==> 0S1 S ==> 0S’ | 01 S’ ==> S1 | 1 Answer: S ==> abx S ==> aS’ | aby S’ ==> bS’’ | cS’’ | acx S’’ ==> x | y | acy Answer: A bcW | bcE W x E q A->bcX X->W | E W->x E->q A-> bcX X-> W
| / F T' | F num | id Consider the grammar E T + E E T T int T int * T T ( E ) Answer: Hard to predict because for T, two productions with int For E, it is not clear how to predict which rule to use What you JUST did is called “pairwise disjointness test” What if the Grammar fails disjointness test? Must left-factor to create a predictive parsing grammar Left-factoring involves rewriting rules so that if a non-terminal has > 1 rule, each begins with a terminal add new non-terminals (new letters) to factor out common prefixes of Left Factoring Example Left factor the grammar below: S ==> 0S1 | 01 Answer: S ==> 0S’ S’ ==> S1 | 1 S ==> abx | aby | acx | acy Answer: S ==> aS’ S’ ==> bS’’ | cS’’ S’’ ==> x | y A bcW | bcE W x E q Answer: A->bcX X->W | E W->x E->q A-> bcX X-> W
Parsing.docx