LL(1)文法的定义p71 ■一个上下文无关文法是LL(1)文法的充分必要条件是 对每个非终结符的两个不同的产生式，A·a,A→B, 满足：SELECT(A→a)∩SELECT(A→B)=Φ S→aAd 求所有SELECT集合： A→bASE SELECT (S-aA)=FIRST (aA)={a} SELECT(Sd)=FIRST(d)={d} ■SELECT(A→bAS)=FIRST(bAS)={b} ■SELECT(A→E) =(FIRST(E)-E)UFOLLOW(A)={a,d,# 求每个非终结符不同产生式SELECT的交集： SELECT(S→aA)∩SELECT(S→d)=Φ SELECT(A→bAS)∩SELECT(A→E)=Φ 所以，该文法是LL()文法。 11 ☑
11 LL(1)文法的定义 p71 ◼ 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→α，A→β， 满足：SELECT(A→α)∩SELECT(A→β)= φ 求所有SELECT集合： ◼SELECT(S→aA)=FIRST(aA)={a} ◼SELECT(S →d)=FIRST(d)={d} ◼SELECT(A →bAS)=FIRST(bAS)={b} ◼SELECT(A →ε) ◼ =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} S → aA|d A → bAS|ε 求每个非终结符不同产生式SELECT的交集： SELECT(S→aA)∩SELECT(S →d)=φ SELECT(A →bAS)∩SELECT(A →ε)=φ 所以，该文法是LL(1)文法
LL(1)文法的定义p71 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→α，A→B 满足：SELECT(A→a)∩SELECT(A→B)=中 S→aAS/b ■F0LL0W(A)={a,b} A→bAE 求所有SELECT:集合： SELECT(S-aAS)=FIRST(aAS)={a} 存在问题： ■SELECT(S→b)=FIRST(b)={b} 当A面临输入符 ■SELECT(A→bA)=FIRST(bA)={b} 号b时，无法用唯 ■SELECT(A-→E) 一的产生式去匹 =(FIRST (E)-E)UFOLLOW(A)={a,b} 配。 求每个非终结符不同产生式SELECT的交集： SELECT(S→aAS)∩SELECT(S→b)=Φ SELECT(A→bA)∩SELECT(A →E)={b}≠Φ 所以，该文法不是LL(①)文法
12 LL(1)文法的定义 p71 ◼ 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→α，A→β， 满足：SELECT(A→α)∩SELECT(A→β)= φ ◼FOLLOW(A)={a,b} 求所有SELECT集合： ◼SELECT(S→aAS)=FIRST(aAS)={a} ◼SELECT(S →b)=FIRST(b)={b} ◼SELECT(A →bA)=FIRST(bA)={b} ◼SELECT(A →ε) ◼ =(FIRST(ε)-ε) ∪FOLLOW(A)={a,b} S → aAS|b A → bA|ε 求每个非终结符不同产生式SELECT的交集： SELECT(S→aAS)∩SELECT(S →b)=φ SELECT(A →bA)∩SELECT(A →ε)={b}≠φ 所以，该文法不是LL(1)文法。 存在问题： 当A面临输入符 号b时，无法用唯 一的产生式去匹 配
LL(1)分析 ■对于文法G,当面临的输入符号为a,要用 非终结符A进行匹配时，假设A的所有产生 式为A→a1a2. an 1)若a∈FIRST(ai),则指派ai去执行任务 2)若a不属于任何候选首符集，则： ①若e属于某个FIRST(ai)且 a∈FOLLOW(A),则让A与e自动匹配 ②否则，a的出现是一种语法错误 13 章节目录
13 LL(1)分析 ◼对于文法G，当面临的输入符号为a，要用 非终结符A进行匹配时，假设A的所有产生 式为 A→α1| α2 |.| αn 1)若a∈FIRST(αi )，则指派αi去执行任务 2)若a不属于任何候选首符集，则： ①若ε属于某个FIRST(αi )且 a∈FOLLOW(A)，则让A与ε自动匹配 ②否则，a的出现是一种语法错误 章节目录
4.2LL(1)文法的判别p72 ■FIRST:集合的计算 ■FOLLOW集合的计算 ■SELECT集合的计算 ■LL(1)文法的判别举例 ■LL(1)文法判别课堂练习 章节目录 14
14 4.2 LL(1)文法的判别 p72 ◼FIRST集合的计算 ◼FOLLOW集合的计算 ◼SELECT集合的计算 ◼LL(1)文法的判别举例 ◼LL(1)文法判别课堂练习 章节目录
FIRST(a)的计算法 定义和关系图p73 ■FIRST(a)={a|a==*>a.,a∈Vr} ◆若a==*>e,则e∈FIRST(a) ■计算文法符号X的FIRST(X) ■计算文法符号串a=XX2.Xn的FIRST(a) 15 ☒
15 FIRST(α)的计算法 ——定义和关系图 p73 ◼FIRST(α)={ a｜α ==*> a . ，a∈ＶT } ◆若α ==*>ε，则ε∈ FIRST(α) ◼计算文法符号X的FIRST（X） ◼计算文法符号串α=X1X2.Xn的FIRST(α)