一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语 义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和 错误处理程序。
词法分析程序的主要任务： 扫描源程序，识别出具有独立意义的单词
词法分析程序的其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，将行号与出错信息相联系起来。 宏展开，……
1.设有如下文法 G(S)，试消除其左递归。
G（ S）： S—> Ac| c
A—> Bb| b
B—> Sa| a
解:S->abcS'|bcS'|cS',S'->abcS'|ε
2.试构造与下面G(S)等价的无左递归的文法。
G(S):S->Sa|Nb|c
N—>Sd|Ne|f
解：S-fN'bS'|cS',S'→aS'|dN'bS'|ε,N'->eN'|ε
3.设有文法G(S):
S——>aBc|bAB
A->aAb|b
B->b|ε
①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。
②构造LL(1)分析表，并分析符号串baabbb是否是。
解：(1) FIRST(aBc)={a},
FIRST(bAB)={b}FIRST(aAb)={a},
A→b:FIRST(A→b)={b},
B-b:FIRST(b)={b},FIRST(ε)={ε}
FOLLOW(A)={b,#},FOLLOW(B)={c,#}
SELECT(S→aBc)={a},
SELECT(S→bAB)={b},
SELECT(A→aAb)={a},
SELECT(A→b)={b},
SELECT(B->b)={b}, SELECT(B->ε)={c,#}
因此，所得的LL(1)分析表如表所示。
4.对下列文法
G(S):S——>D(R)
R—>R;P|P
P->S|I
D->i
①计算文法G中每个非终结符的FIRSTVT集和令LASTVT集。
②构造文法G的算符优先关系矩阵。
解：(1) FIRSTVT(S)={(,i},
FIRSTVT(D)={i},
FIRSTVT(R)={;, (,i},
FIRSTVT(P)={i,(},
LASTVT(S)={)},
LASTVT(D)={i},
LASTVT(R)={;,),i},
LASTVT(P)={i,)}
5.已知文法
G(S):S——>a|(T)
T->T,S|S
①给出句子（(a,a),a)的最左推导并画出语法树；
②给出句型（T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。
解：(1)最左推导：
S→（T)=(T,S)=(S,S)→（a,S) =(a,(T)) =(a,(T,S)) =(a,(S,S)) =(a,(a,S)) (a,(a,a))
语法树：如图所示。
(2)句型（T,a,(T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图)。
短语：a||T,a||(T)||T,a,(T)||(T,a,(T))
直接短语：a||(T)
素短语：a||(T)
最左素短语：a
句柄：a
活前缀：ε||(||(T|(T,||(T,a
6.设文法G(S)为：
s->a|aAb
s->b|bBa
A->1A0|ε
B->1B0|ε
求
①LR(0)项目集族；
②构造识别文法G(E)的DFA;
③构造文法G(E)的SLR(1)的分析表；
④分析句子a1100b的识别过程。
解：(1)、（2)LR(0)项目集族和识别活前缀的DFA,如图所示。
