《编译原理教案- lr分析》由会员分享，可在线阅读，更多相关《编译原理教案- lr分析（78页珍藏版）》请在金锄头文库上搜索。
1、LR分析,自下而上语法分析算法之,复习：移进-归约分析,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,在步骤3中，用Ab归约 在步骤5中，用AAb归约 问题：何时移进？何时归约？用哪个产生式归约？,3） #ab
2、bcde# 归约(Ab),5） #aAb cde# 归约(AAb),4） #aA bcde# 移进,6） #aA cde# 移进,分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中的状态会发生变化 我们引入一个新的状态栈来表示符号栈中的符号目前状态 用LR分析表来表示不同状态下对于各输入符号应采取的动作,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #aAcB e# 移进 0
3、2357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,Si:移进，并将状态i进栈 ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈,步骤,符号栈,输入
4、符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 02357
5、9 r1 1,状态栈,ACTION,GOTO,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,Si:移进，并将状态i进栈 ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈,问题： 对于一个文法，状态集是如何确定的？ LR分析表是如何得到的？,可归前缀与活前缀,文法GS： (1) S aAcBe1 (2) A b2 (3) A Ab3 (4) B d4,S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,每次归约句型的前部分依次为： ab2 aAb3 aAcd4 aAcBe1,规范句型的这种前部
6、分符号串称为可归前缀 我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe,活前缀（Viable Prefixes）,viable:adj capable of growing and developing capable of being put into practice : workable 定义： S A 是文法G中的一个规范推导，如果符号串是的前缀，则称是G的一个活前缀。,LR分析需要构造识别活前缀的有穷自动机 我们可以文法的终结符和非终结符都看成有穷自动机的输入符
7、号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(
8、AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde#
9、移进 02 S4,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进
10、02 S4,4） #aA bcde# 移进 023 S6,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r
