1. 文法 G（S）:
（1）S -> AB
（2）A ->Da | ε
（3）B -> cC
（4）C -> aADC | ε
（5）D -> b | ε
验证文法 G（S）是不是 LL（1）文法？
FIRST集:
FIRST(A) → { a,b }
FIRST(Da) → { a,b }
FIRST(ε)→{ ε }
FIRST(cC)→{ a,c }
FIRST(b)→{ b }
FOLLOW集:
FOLLOW(S)→{ # }
FOLLOW(A)→{ a,b,c,# }
FOLLOW(B)→{ # }
FOLLOW(C)→{ # }
FOLLOW(D)→{ a,# }
SELECT集:
SELECT(A→Da)={b,a}
SELECT(A→ε)={a,b,c,#}
SELECT(B→cC)={c}
SELECT(C→aADC)={a}
SELECT(C→ε)={#}
SELECT(D→b)={b}
SELECT(D→ε)={a,#}
因为：SELECT(A→Da) ∩ SELECT(A→ε) ≠ Ø
所以G（S）不是 LL（1）文法。
2.(上次作业)消除左递归之后的表达式文法是否是LL(1)文法？
消除左递归后：
E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | i
FIRST集:
FIRST(E) → { ( , i }
FIRST(E') → { +,ε }
FIRST(T) → { ( , i }
FIRST(T') → { *,ε }
FIRST(F) → { ( , i }
FOLLOW集:
FOLLOW(E) → { ) , # }
FOLLOW(E') → { ) , # }
FOLLOW(T) → { + , ) , # }
FOLLOW(T') → { + , ) , # }
FOLLOW(F) → { * , + , ) , # }
SELECT集:
SELECT(E→TE') → { ( , i }
SELECT(E'→+TE') → {+}
SELECT(E'→ε)= FIRST(ε)-{ ε } U FOLLOW(E') = FOLLOW(E') → { ) , # }
SELECT(T→FT') → { ( , i }
SELECT(T'→*FT') → {*}
SELECT(T'→ε) → {+,),#}
SELECT(F→(E)) → { ( }
SELECT(F→i) → { i }
因为：SELECT(E'→+TE')∩SELECT(E'→ε)= ∅，SELECT(T'→*FT')∩SELECT(T'→ε)=∅，SELECT(F→(E)) SELECT(F→i)=∅
所以文法 G（S）是 LL（1）文法。
3.接2，如果是LL(1)文法，写出它的递归下降语法分析程序代码。
E()
｛T();
E'();
}
E'()
T()
T'()
F()
SELECT集:
SELECT(E→TE') → { ( , i }
SELECT(E'→+TE') → {+}
SELECT(E'→ε)= FIRST(ε)-{ ε } U FOLLOW(E') = FOLLOW(E') → { ) , # }
SELECT(T→FT') → { ( , i }
SELECT(T'→*FT') → {*}
SELECT(T'→ε) → {+,),#}
SELECT(F→(E)) → { ( }
SELECT(F→i) → { i }
递归下降语法分析程序：
void ParseE(){
switch(lookahead){
case '(','i':
ParseT();
ParseE'();
break;
default:
print("syntax error ");
exit(0);
}
}
void ParseE'(){
switch(lookahead){
case '+':
MatchToken('+');
ParseT();
ParseE'();
break;
case ')','#':
break;
default:
print("syntax error ");
exit(0);
}
}
void ParseT(){
switch(lookahead){
case '(','i':
ParseF();
ParseT'();
break;
default:
print("syntax error ");
exit(0);
}
}
void ParseT'(){
switch(lookahead){
case '*':
MatchToken('*');
ParseF();
ParseT'();
break;
case '+',')','#':
break;
default:
print("syntax error ");
exit(0);
}
}
void ParseF(){
switch(lookahead){
case '(':
MatchToken('(');
ParseE();
MatchToken(')');
break;
case 'i':
MatchToken('i');
break;
default:
print("syntax error ");
exit(0);
}
}
4.加上实验一的词法分析程序，形成可运行的语法分析程序，分析任意输入的符号串是不是合法的表达式。