第6章编译原理答案(主编张晶).ppt

回忆上一章学习 自顶向下 自底向上 根据文法识别串abbcde S?aAbB A ?c A ? A c B?d B?d B 每个产生式尾部加上【1】序号 S?aAbB 【1】 A ?c【2】 A ? A c【3】 B?d 【4】 B?d B【5】 A-?△XYZ 预期要规约的句柄是xyz，但都未进栈。 A-?X △ YZ 预期要规约的句柄是xyz，X进栈,YZ未进栈。 A-?X Y △ Z 预期要规约的句柄是xyz，XY进栈, Z未进栈。 A-?X Y Z △ 预期要规约的句柄是xyz，XY Z均进栈，是规约项目。 定义:一个LR(1)项目[A→α△β,a],对规范前缀 γ=δα有效 是指存在规范推导 δAy δαβy, y∈ 且满足下列条件 ①当y≠ε时,a=First(y) ②当y=ε时,a=“#” 对于前例: CbBb Cbab β=ε,y=b,First(y)=b,δ=Cb ∴LR(1)项目[B→a△,b]对Cba有效 而[C→a△,b]对Cba不是有效. r r r * r * 暂时进栈的串 又如: CbBb CbCab Cbaab β=ε,y=ab,First(y)=a,δ=Cb ∴ LR(1)项目[C→a△,a]对Cba有效. 由此,在LR(1)中:识别文法全部规范前缀的DFA 的每一个状态对应一个项目集,且每个项目集中的 项目都是有效项目. * r r r 两个函数CLOSURE(Si)和GO(Si,x) 设Si是一个项目集,它的闭包CLOSURE(Si) 定义如下: ① Si中的任何LR(1)项目∈CLOSURE(Si). ②若项目[A→α△Xβ,a]∈CLOSURE(Si), 其中X∈VN,X→y是一个产生式,b∈First(βa), 则[X→△y,b]∈CLOSURE(Si). ③重复②,直到CLOSURE(Si)不再增加为止. GO(Si,x)=CLOSURE(Sj) Sj={任何形如[A→αx△β,a]的项目 |[A→α△xβ,a]∈Si} 每一个LR(1)项目与其后继项目有相同的向前搜 索符号. 构造LR(1)项目集的规范族: 首先把[ →△S,#]作为初始项目集的基本项目, 对其求闭包,然后求后继项目,…,直到没有新的项目 集生成为止. 例6-6 的项目集族如图6.15所示 LR(1)分析表构造算法: ①对于[A→α△xβ,a]∈Si,且GO(Si,x)=Sj,x∈VN 则置GOTO[Si,x]=j ②对于[A→α△aβ,b]∈Si,且GO(Si,a)=Sj,a∈VT 则置ACTION[Si,a]=Sj ③对于[A→α△,a]∈Si,且A→α是文法的第j个产生式, 则置ACTION[Si,a]=rj ④对于[ →S△,#]∈Si,则置ACTION[Si,#]=acc ⑤其他情况置错. 定义： LR(1)文法:按上述算法构造出的分析表若没有 冲突项目,则该文法是LR(1)文法. 例6-6的LR(1)分析表如表6.20所示 6.3.5 LALR(1)分析方法 LR(1)分析能力较强----规范LR分析器 LR(1)缺点:文法较大时,分析表太大. LALR(1)采用一种折中的方法,分析表比LR(1)要小得多,能力也差一点,但它能对付SLR所不能对付的情形. 例: G[ ]: (0) →S (1) S→AA (2) A→aA (3) A→b 构造LR(1)项目集族 如图6.16 构造LR(1)分析表 如表6.21 在图6.16中有一些相似的项目集 如: S3---S6 S3={A→a△A,a/b S6={A→a△A,# A→△aA,a/b A→△aA,# A→△b,a/b} A→△b,# } S4---S7 S4={A→b△,a/b} S7={A→b△,# } S8---S9 S8={A→aA△,a/b } S9={A→aA△,# } 称具有相同的心(核)的项目集称为同心集或等价 状态. 合并等价状态: