编译原理第4章。问题集.pptVIP

I will greet this lecture with love in my heart. 主讲人：韩士元 Email: shiyuanhan@126.com Tel: +86 消除左递归 1、设有文法G[A]如下： A→BaC|CbB， B→Ac|c ， C→Bb|b 消除文法G[A]的左递归 P?Pα1|Pα2|…|Pαn|β1|β2|…|βm P?(β1|β2|…|βm)P’ P’?(α1|α2|…|αn)P’ | ε 显示左递归： 核砍蚊鳃惶主阴绊秘爽档鄂咨举骇参酋拓鸯从苫仔赡开配申间工幌方啊说编译原理第4章。问题集编译原理第4章。问题集 消除左递归 1、设有文法G[A]如下： A→BaC|CbB， B→Ac|c ， C→Bb|b 消除文法G[A]的左递归 隐式左递归： (1) 对非终结符号给出一种排序：A1, A2, …, An 要求文法不含回路，即不含P?P + (2) for (i=1; i=n; i++) { for (j = 1; j i; j++) { if (Ai?Ajγ Aj?δ1|δ2|…|δk) Ai?δ1γ|δ2γ|…|δkγ } 消除Ai的左递归 } (3) 化简（去掉无用产生式） 牢近度走卯灭观痕哺苍篮厄蒜涣庆能情串鼻宅往话鼓羞怪硅汁檄继惶弟瘁编译原理第4章。问题集编译原理第4章。问题集 消除左递归 1、设有文法G[A]如下： A→BaC|CbB， B→Ac|c ， C→Bb|b 消除文法G[A]的左递归 排列顺序：A, B, C A: A→BaC|CbB B: B→Ac|c B?BaCc|CbBc|c B?CbBcB’|cB’ B’?aCcB’|ε C: C→Bb|b C?CbBcB’b| cB’ b|b C? cB’ bC’|bC’ C’?bBcB’bC’|ε A→BaC|CbB B?CbBcB’|cB’ B’?aCcB’|ε C? cB’ bC’|bC’ C’?bBcB’bC’|ε 绅核默沁鉴形住山盂矗歧颂坐炎赐蔼奄排绰东自拢季毒瑶切魔刁峨醚弧蓬编译原理第4章。问题集编译原理第4章。问题集 FIRST FOLLOW集合 2、已知文法G[S]如下，求各个非终结符的FIRST集合和FOLLOW集合 S→eT|RT T→DR|? R→dR|? D→a|bd I will greet this lecture with love in my heart. FIRST(R)={ d, ? } FIRST(D)={ a, b} FIRST(T)={ ?, a, b} FIRST(S)={e,d,a,b, ?} FOLLOW(S) = {#} FOLLOW(T) = {#} FOLLOW(R) = {#,a,b} FOLLOW(D) = {d, #} 浙赡赂芬漫炳晦颠岩瞳有情眠缚虞旋避蹿书邑笑币杯茄熟髓荷杖刁噪瘪身编译原理第4章。问题集编译原理第4章。问题集 LL(1) 3、文法G[E]： E→TE’, E’→∨TE’ | ε, T→FT’, T’→∧FT’| ε, F→(E)|┐E|i （1）求G[E]的所有非终极符号的FIRST集。 （2）求G[E]的所有非终极符号的FOLLOW集。 （3）构造G[E]的LL(1)分析表。 FIRST(F)={( , ┐, i} FIRST(T’)={∧, ε} FIRST(T)= FIRST(F)={( , ┐, i} FIRST(E’)={∨, ε} FIRST(E)=FIRST(T)={( , ┐, i} 乏诌埔唉拾伙娄土斥失枝拓肃秒姚汽蓝近恩汁雄畅氮支嫡炭分耀矫煮贝汾编译原理第4章。问题集编译原理第4章。问题集 LL(1) 3、文法G[E]： E→TE’, E’→∨TE’ | ε, T→FT’, T’→∧FT’| ε, F→(E)|┐E|i （1）求G[E]的所有非终极符号的FIRST集。 （2）求G[E]的所有非终极符号的FOLLOW集。 （3）构造G[E]的LL(1)分析表。 FIRST(F)={( , ┐, i} FIRST(T’)={∧, ε} FIRST(T)= FIRST(F)={( , ┐, i} FIRST(E’)={∨, ε} FIRST(E)=FIRST(T)={( , ┐, i} FOLLOW(E)={∨, ∧,#，) } FOLLOW(T)= {∨, ∧,#，) } FOLLOW(E’)= {∨, ∧,#，)} FIRST(F)=(∨, ∧,#，)} FOLLOW(T’)= {∨, ∧,#，) } 攘炼惕栋鸵豪周