SELECT(A→a)集合的定义p78 ■设G=(Vr,VN,S,P)a∈V* ■FIRST(a)={aa=*>aB,a∈Vr} ◆若a*>e,则SELECT(A→a)=FIRST(a) ◆若a==*>e,则SELECT(A→a) =(FIRST(a)-{e})UFOLLOW(A) S→aAd FOLLOW (A)={a,d,#} A→bASE SELECT (A-bAS)=FIRST(bAS)=(b} SELECT(A→E) =(FIRST(E)-E)UFOLLOW(A)={a,d,# SaAld FOLLOW(A)=(a,d,#FIRST(K)={c,E} A→bASK SELECT (A-bAS)=FIRST (bAS)=(b} K→clE SELECT(A一→K) =(FIRST(K)-8)UFOLLOW (A)={c,a,d,# 可D
11 SELECT(A → α)集合的定义 p78 ◼ 设G=(ＶT，ＶN，S，P） α∈Ｖ* ◼ FIRST(α)={a|α==*> aβ，a∈ＶT} ◆若α==*>ε，则SELECT(A→α)= FIRST(α) S → aA|d A → bAS|K K → c|ε FOLLOW(A)={a,d,#} SELECT(A →bAS)=FIRST(bAS)={b} SELECT(A →ε) =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} S → aA|d A → bAS|ε FOLLOW(A)={a,d,#} FIRST(K)={c, ε} SELECT(A →bAS)=FIRST(bAS)={b} SELECT(A →K) =(FIRST(K)-ε) ∪FOLLOW(A)={c,a,d,#} ◆若α==*>ε，则SELECT(A→α) = (FIRST(α)-{ε})∪FOLLOW(A)
LL(1)文法的定义p78 ■一个上下文无关文法是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(1)文法。 12 ☒
12 LL(1)文法的定义 p78 ◼ 一个上下文无关文法是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)文法的定义p78 一个上下文无关文法是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(①)文法
13 LL(1)文法的定义 p78 ◼ 一个上下文无关文法是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)分析p78 ■含义 ◆第一个L表示从左向右扫描输入符号串； ◆第二个L表示生成最左推导； ◆1表示读入一个符号可确定下一步推导。 ■LL(1)文法能够对输入串进行有效的。 ■ 无回溯的自上而下分析。 14 ☑
14 LL(1)分析 p78 ◼含义 ◆第一个 L 表示从左向右扫描输入符号串； ◆第二个 L 表示生成最左推导； ◆1 表示读入一个符号可确定下一步推导。 ◼LL(1)文法能够对输入串进行有效的。 ◼ 无回溯的自上而下分析
LL(1)分析 ■对于文法G,当面临的输入符号为a,要用 非终结符A进行匹配时，假设A的所有产生 式为A→a1a2. an 1)若a∈FIRST(ai),则指派ai去执行任务 2)若a不属于任何候选首符集，则： ①若e属于某个FIRST(ai)且 a∈FOLL0W(A),则让A与e自动匹配 ②否则，a的出现是一种语法错误 章节目录 15
15 LL(1)分析 ◼对于文法G，当面临的输入符号为a，要用 非终结符A进行匹配时，假设A的所有产生 式为 A→α1| α2 |.| αn 1)若a∈FIRST(αi )，则指派αi去执行任务 2)若a不属于任何候选首符集，则： ①若ε属于某个FIRST(αi )且 a∈FOLLOW(A)，则让A与ε自动匹配 ②否则，a的出现是一种语法错误 章节目录