ch7.1-7.3lr-slr语法分析(张素琴)

《ch7.1-7.3lr-slr语法分析(张素琴)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、17.1LR分析概述7.2LR(0)分析7.3SLR(1)分析7.4LR(1)分析7.7语法分析器的自动构造工具yacc第7章LR分析法27.1LR分析概述分析器的逻辑结构及工作过程LR(k)分析技术L----是指从左至右扫描输入符号串R----是指构造一个最右推导的逆过程，K----是指为了作出分析决定而向前看的输入符号的个数。3LR分析方法是当前最广义的无回溯的“移进-归约”方法。LR(k)分析技术knuth于1965年首先提出来的。根据栈中的符号串和向右顺序查看输入串中的k(k0)个符号，就能唯一确定分析器的动作是

2、移进还是归约，以及用哪个产生式进行归约。优点：限制少，适用范围广；分析速度快；报错准确。4缺点：构造分析器的工作量很大，不大可能手工构造用软件工具yacc-YetAnotherCompilerCompiler,Bell,1974.输入LR上下文无关文法的BNF，输出LR分析器。5一、LR分析器逻辑结构输入、输出、栈、驱动程序和分析表组成id+id*id#LR驱动程序动作转移actiongoto输出S1Xm…S1…X1S0#栈状态文法符号产生式表ＬＲ分析特征:规范的符号栈中的符号是规范句型的前缀分析决策依据―栈顶状态和现行输

3、入符号．识别规范句型特定前缀(就到句柄为止)的DFA.四种技术LR(0)SLR(1)LR(1)LALR(1)7不同的语法分析器具有不同的分析表,驱动程序都是一样的LR(0)分析器LR(0)分析表SLR(1)分析器SLR(1)分析表LR(1)分析器LR(1)分析表LALR(1)分析器LALR(1)分析表分析表是LR分析法的核心，它包含两部分：动作表（ACTION）和状态转换表（GOTO）8动作表动作规定如下：移进ai和s=action[sm,ai]进栈action[sm,ai]=归约rj:AXm-r+1Xm-r+2…Xms

4、=goto[sm-r,A]接受成功，规约到识别符号出错9二、LR分析器的工作过程主控程序根据输入串、栈、产生式、分析表进行相应的移近、规约、接受或报错操作。id+id*id#LR主控程序动作转移actiongoto输出S1Xm…S1…X1S0#栈状态文法符号产生式表107.2LR(0)分析A→.XYZA→X.YZA→XY.ZA→XYZ.对于产生式A→XYZ对应的句柄XYZ,其状态划分为：句柄识别态一、LR分析的基本原理把每个句柄的识别过程划分为若干个状态,每个状态下，自左向右地识别了句柄的一部分符号。11活前缀定义:规范推

5、导S*A，的所有前缀称为活前缀。即规范句型的前缀，但右端不超过该句型句柄末端。识别了句柄的一部分就相当于识别了当前规范句型的左起部分，这部分被识别的符号串称之为规范句型的活前缀。对于文法G[S]1.S→vI:T2.I→I,i3.I→i4.T→realvi,i:real是该文法的一个句子S=>vI:T=>vI:real=>vI,i:real=>vi,i:real12vi,i:real#其活前缀是:#vi,iεvI,ivivvI,vIvI:vI:realvI:TSIIvIreal:T1.S→vI:T2.I→I

6、,i3.I→i4.T→realS13DFA的定义：M=（Q,Σ,δ,q0,Z)其中：Q--状态集Σ—输入字母表δ–QxΣ→Q的映射函数LR分析器使用有穷自动机DFA识别各规范句型的活前缀LR(0)项目：14LR(0)项目:用圆点“”表示识别一个产生式右部符号到达的位置，若有规则AXYZ,则有下面四个项目：A→.XYZA→X.YZA→XY.ZA→XYZ.Aa,aVT移进项目AB,BVN待归约项目A归约项目S’´.S开始项目项目A→X.YZ和A→XY.Z称为后继项目S’´S接受项目15拓广文

7、法定义：为了使文法的“接受”状态易于识别，且唯一，常对文法进行拓广改造。对于文法G，我们构造一个G’，引进一个不出现在G中的非终结符S’和一个产生式S’→S，S’为G’的开始符号,S’不出现在规则右部。对于文法G[E]1.E→aA

8、bB2.A→cA

9、d3.B→cB

10、d文法G’[S’]0.S’→E1.E→aA

11、bB2.A→cA

12、d3.B→cB

13、d拓广文法161.S’→E2.S’→E3.E→aA4.E→aA5.E→aA6.A→cA7.A→cA8.A→cA9.A→d10.A→d11.E→bB12.E→b.B13.E→bB14.B

14、→cB对于上述文法G’,所有LR(0)项目如下：15.B→cB16.B→cB17.B→d18.B→d文法G’[S’]0.S’→E1.E→aA

15、bB2.A→cA

16、d3.B→cB

17、d17归约项目：5、8、10、13、16、18接收项目：2移进项目：3、6、9、11、14、17待约项目：4、7、12、15初始