自底向上的解读

1、School of Computer Science & Technology Harbin Institute of Technology重点：重点：自底向上分析的基本思想，算符优先分析法的基本思想，自底向上分析的基本思想，算符优先分析法的基本思想，简单算符优先分析法。简单算符优先分析法。LR LR 分析器的基本构造思想，分析器的基本构造思想，LRLR分析算法，分析算法，规范句型活前缀及其识别器规范句型活前缀及其识别器DFADFA，LR(0)LR(0)分析表的构造，分析表的构造，SLR(1)SLR(1)分析表的构造分析表的构造, LR(1), LR(1)分析表的构造。分析表的构造。难

2、点：难点：求求FIRSTOP FIRSTOP 和和LASTOPLASTOP，算符优先关系的确定，算符优先分，算符优先关系的确定，算符优先分析表的构造，素短语与最左素短语的概念。规范句型活前缀，析表的构造，素短语与最左素短语的概念。规范句型活前缀，LR(0)LR(0)项目集闭包与项目集规范族，它们与句柄识别的关系，活前项目集闭包与项目集规范族，它们与句柄识别的关系，活前缀与句柄的关系缀与句柄的关系, LR(1), LR(1)项目集闭包与项目集规范族。项目集闭包与项目集规范族。 第五章第五章 自底向上的自底向上的语法分析语法分析2022-6-192第第5章章 自底向上的语法分析自底向上的语法分析

3、5.1 自底向上的语法分析概述自底向上的语法分析概述5.2 算符优先分析法算符优先分析法5.3 LR分析法分析法5.4 语法分析程序的自动生成工具语法分析程序的自动生成工具Yacc5.5 本章小结本章小结2022-6-1935.1 自底向上的语法分析概述自底向上的语法分析概述n思想思想n从输入串出发，反复利用产生式进行归约，如果从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。则输入串有语法错误。n核心核心n寻找句型中的当前归约对象寻找句型中的当前归约对象“句柄句柄”进行归约进行归约, ,用不同

4、的方法寻找句柄，就可获得不同的分析方法用不同的方法寻找句柄，就可获得不同的分析方法2022-6-194例例5.1 一个简单的归约过程一个简单的归约过程n设文法设文法G为：为：SaABe AAbc|b Bd2022-6-195语法分析树的生成演示语法分析树的生成演示a b b c d eAABSAbAbAAbcAAbcBdBdSaAcBeSaAcBe2022-6-1965.1.1 移进移进-归约分析归约分析n系统框架系统框架n采用表驱动的方式实现采用表驱动的方式实现n输入缓冲区：保存输入符号串输入缓冲区：保存输入符号串n分析栈：保存语法符号分析栈：保存语法符号已经得到的那部已经得到的那部分分析结

5、果分分析结果n控制程序：控制分析过程，输出分析结控制程序：控制分析过程，输出分析结果果产生式序列产生式序列n格局：格局：栈栈+ +输入缓冲区剩余内容输入缓冲区剩余内容= =“句型句型”2022-6-197移进移进-归约语法分析器的总体结构归约语法分析器的总体结构 移进移进-归约归约控制程序控制程序栈内容栈内容+ +输入缓冲区内容输入缓冲区内容 # # “当前句型当前句型 ” # #栈栈输入缓冲区输入缓冲区 2022-6-198与与LL(1)的体系结构比较的体系结构比较 输入缓冲区输入缓冲区( (符号序列符号序列) )控制程序控制程序P132预测分析表预测分析表M M2022-6-199移进移进

6、-归约分析的工作过程归约分析的工作过程n系统运行系统运行n开始格局开始格局n栈：栈：# #；输入缓冲区：；输入缓冲区：w#w#n存放已经分析出来的结果存放已经分析出来的结果, ,并将读入的符号送入栈，并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈将结果压入栈n问题：系统如何发现句柄在栈顶形成？问题：系统如何发现句柄在栈顶形成？n正常结束正常结束: : 栈中为栈中为 #S#S，输入缓冲区只有，输入缓冲区只有 # #2022-6-1910输出结果表示：输出结果表示：用产生式序列表示语法分析树用产生式序列表示语法分析树E idi

7、d + id * id EEEEE例例5.2 EE+E|E*E|(E)|id2022-6-1911id + id id + id * * idid例例5.2 分析过程分析过程E EE EE EE E2022-6-1912分析器的四种动作分析器的四种动作1) 1) 移进：将下一输入符号移入栈移进：将下一输入符号移入栈2) 2) 归约：用产生式左侧的非终结符替换栈顶归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）的句柄（某产生式右部）3) 3) 接受：分析成功接受：分析成功4) 4) 出错：出错处理出错：出错处理？决定移进和归约的依据是什么？决定移进和归约的依据是什么回头看是回头看是否可

8、以找到答案否可以找到答案2022-6-1913移进移进-归约分析中的问题归约分析中的问题n1) 1) 移进归约冲突移进归约冲突 n例例5.25.2中的中的 6)6)可以移进可以移进 * * 或按产生式或按产生式EE+EEE+E归约归约 2022-6-1914id + id id + id * * idid例例5.25.2分析过程分析过程E EE EE EE E2022-6-1915移进移进-归约分析中的问题归约分析中的问题1) 1) 移进归约冲突移进归约冲突 n例例5.25.2中的中的 6)6)可以移进可以移进 * * 或按产生式或按产生式EE+EEE+E归约归约 2) 2) 归约归约冲突归约

9、归约冲突 n存在两个可用的产生式存在两个可用的产生式n各种分析方法处理冲突的方法不同各种分析方法处理冲突的方法不同n如何识别句柄？如何识别句柄？n如何保证找到的直接短语是最左的如何保证找到的直接短语是最左的? ?利用栈利用栈n如何确定句柄的开始处与结束处？如何确定句柄的开始处与结束处？2022-6-19165.1.2 优先法优先法n根据归约的先后次序为句型中相邻的文法符号根据归约的先后次序为句型中相邻的文法符号规定优先关系规定优先关系n句柄内相邻符号同时归约，是同优先的句柄内相邻符号同时归约，是同优先的n句柄两端符号的优先级要高于句柄外与之相邻的句柄两端符号的优先级要高于句柄外与之相邻的符号符

10、号na1ai-1 aiai+1aj-1aj aj+1ann定义了这种优先关系之后，语法分析程序就可定义了这种优先关系之后，语法分析程序就可以通过以通过ai-1 ai和和aj aj+1这两个关系来确定句柄这两个关系来确定句柄的头和尾了的头和尾了 2022-6-1917 根据句柄的识别状态（根据句柄的识别状态（句柄是逐步形成的句柄是逐步形成的） 用状态来描述不同时刻下形成的那部分句柄用状态来描述不同时刻下形成的那部分句柄 因为句柄是产生式的右部，可用产生式来表示句因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态柄的不同识别状态 例如：例如： SbBB可分解为如下识别状态可分解为如下识别状

11、态 S.bBB 移进移进b SbB.B 等待归约出等待归约出B Sb.BB 等待归约出等待归约出B SbBB. 归约归约 采用这种方法，语法分析程序根据当前的分析状采用这种方法，语法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约态就可以确定句柄的头和尾，并进行正确的归约。 5.1.3 状态法状态法2022-6-19185.2 算符优先分析法算符优先分析法n算术表达式分析的启示算术表达式分析的启示n算符优先关系的直观意义算符优先关系的直观意义n+ + * * + + 的优先级低于的优先级低于 * *n( ) ( ( ) ( 的优先级等于的优先级等于 ) )n+ + + + +

12、 + 的优先级高于的优先级高于 + +n方法方法n将句型中的终结符号当作将句型中的终结符号当作“算符算符”，借助于算，借助于算符之间的优先关系确定句柄符之间的优先关系确定句柄2022-6-1919算术表达式文法的再分析算术表达式文法的再分析nEE+EnEE-EnEE*EnEE/E nE(E) nEidnEE+T| E-T| T TT*F| T/F| F F(E)|id2022-6-1920算符文法算符文法n如果文法如果文法G=（ V，T，P，S）中不存在形如）中不存在形如ABC 的产生式，则称之为算符文法的产生式，则称之为算符文法(OG Operator Grammar)即：如果文法即：如果文

13、法 中不存在具有相邻非终结符的中不存在具有相邻非终结符的产生式，则称为算符文法。产生式，则称为算符文法。2022-6-1921 定义定义5.1 假设假设G是一个不含是一个不含-产生式的文法，产生式的文法，A、B和和C均是均是G的语法变量，的语法变量，G的任何一对终结符的任何一对终结符a和和b之间之间的的优先关系定义优先关系定义为：为： ab，当且仅当文法，当且仅当文法G中含有形如中含有形如Aab或或AaBb的产生式；的产生式； a b，当且仅当文法，当且仅当文法G中含有形如中含有形如AaB的产的产生式，而且生式，而且Bb或或BCb； a b，当且仅当文法，当且仅当文法G中含有形如中含有形如AB

14、b的产的产生式，而且生式，而且Ba或或BaC； a与与b无关系，当且仅当无关系，当且仅当a与与b在在G的任何句型中都不的任何句型中都不相邻。相邻。 问题：什么是算符优先文法？问题：什么是算符优先文法？5.2.1 算符优先文法算符优先文法2022-6-19225.2.1 算符优先文法算符优先文法n设设G=（V，T，P，S）为）为OG，如果，如果 a,bVT, ab, a b, a b 至多有一个成立，则称之为至多有一个成立，则称之为算符优先文法算符优先文法(OPG Operator Precedence Grammar) 在无在无产生式的算符文法中，如果任意两产生式的算符文法中，如果任意两个终结

15、符之间至多有一种优先关系，则称为个终结符之间至多有一种优先关系，则称为算符优先文法。算符优先文法。2022-6-19235.2.2 算符优先矩阵的构造算符优先矩阵的构造n优先关系的确定n根据优先关系的定义na b AaBP且(B+b或者B+Cb)n需要求出非终结符B派生出的第一个终结符集na b ABbP且(B+a或者B+aC)n需要求出非终结符B派生出的最后一个终结符集n设G=（V，T，P，S）为OG，则定义nFIRSTOP(A)=b|A+b或者A+Bb,bT,B VnLASTOP(A)=b|A+b或者A+bB,bT,B V2022-6-1924算符优先关系矩阵的构造算符优先关系矩阵的构造n

16、Aab ; AaBb, 则则abnAaB,则对则对 bFIRSTOP(B),a bnABb,则对则对 aLASTOP(B), a bnif ABP,then FIRSTOP(B) FIRSTOP(A)nif ABP,then LASTOP(B) LASTOP(A)n问题：编程求问题：编程求FIRSTOP、LASTOP2022-6-1925算符优先关系矩阵的构造算符优先关系矩阵的构造nA AXX1 1X X2 2X Xn n如果如果X Xi iX Xi+1i+1TTTT则：则： X Xi iX Xi+1i+1如果如果X Xi iX Xi+1i+1X Xi+2i+2TVTTVT则：则：X Xi i

17、X Xi+2i+2如果如果X Xi iX Xi+1i+1TVTV则：则： a aFIRSTOP(XFIRSTOP(Xi+1i+1) )，X Xi iaa如果如果X Xi iX Xi+1i+1VTVT则：则： a aLASTOP(XLASTOP(Xi i) )， a aX Xi+1i+12022-6-1926例例 5.6 表达式文法的算符优先关系表达式文法的算符优先关系 acc+ +- -* */ /( () )idid# #* */ /（）idid# # 2022-6-19275.2.3 算符优先分析算法算符优先分析算法n 原理原理n识别句柄并归约识别句柄并归约n各种优先关系存放在算符优先分析

18、表中各种优先关系存放在算符优先分析表中n利用利用识别句柄尾，利用识别句柄尾，利用识别句柄头，分析栈存识别句柄头，分析栈存放已识别部分，比较栈顶和下一输入符号的关系，放已识别部分，比较栈顶和下一输入符号的关系，如果是句柄尾，则沿栈顶向下寻找句柄头，找到后如果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出句柄，归约为非终结符。弹出句柄，归约为非终结符。2022-6-1928例例5.7 EE+T|E-T|T TT*F|T/F|F F(E)|id，试利用算符优先分析法对试利用算符优先分析法对id+id进行分析进行分析步骤步骤栈栈输入串输入串优先关系优先关系动作动作1#id1+id2#2# id1+id2

19、# id1移进移进id13#F+id2# id1 +用用Fid归约归约4#F+id2# 移进移进+5#F+ id2# 移进移进id26#F+F#+ id2 #用用Fid归约归约7#E# + #用用EE+T归约归约2022-6-1929问题问题n有时未归约真正的句柄（有时未归约真正的句柄（F）n不是严格的最左归约不是严格的最左归约n归约的符号串有时与产生式右部不同归约的符号串有时与产生式右部不同n仍能正确识别句子的原因仍能正确识别句子的原因nOPG未定义非终结符之间的优先关系，不能未定义非终结符之间的优先关系，不能识别由单非终结符组成的句柄识别由单非终结符组成的句柄n定义算符优先分析过程识别的定

20、义算符优先分析过程识别的“句柄句柄”为为最最左素短语左素短语LPP（Leftmost Prime Phase）2022-6-1930素短语与最左素短语素短语与最左素短语n什么是短语？当前我们要找什么样的短什么是短语？当前我们要找什么样的短语？语？至少有一个算符至少有一个算符n* and A+，至少含一个终结符，至少含一个终结符，且不含更小的含终结符的短语且不含更小的含终结符的短语,则称则称是句型是句型的相对于变量的相对于变量A的素短语的素短语(Prime Phrase)n句型的至少含一个终结符且不含其它素短句型的至少含一个终结符且不含其它素短语的短语语的短语2022-6-1931例例nEE+T

21、|T TT*F|F F(E)|id句型句型 T+T*F+i 的短语有的短语有T T*F i T+T*F T+T*F+i其中的素短语为其中的素短语为T*F iT*F为最左素短语，是被归约的对象为最左素短语，是被归约的对象问题：按照文法问题：按照文法EE+E|E*E|(E)|id，求求i+E*i+i的短语和素短语的短语和素短语2022-6-1932文法：文法：EE+E|E*E E(E)|id句型句型i+E*i+i的短语的短语2022-6-1933素短语与最左素短语素短语与最左素短语设句型的一般形式为设句型的一般形式为#N1a1 N2a2 Nnan # (Ni V,ai VT）它的最左素短语是满足下

22、列条件的最左子串它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1 Njaj Nj+1其中：其中：ai-1 ai,， aiai+1aj-1aj ， aj aj+12022-6-1934算符优先分析的实现算符优先分析的实现n系统组成系统组成n移进归约分析器移进归约分析器 + + 优先关系表优先关系表n分析算法分析算法n参照输入串、优先关系表，完成一系列归约，生参照输入串、优先关系表，完成一系列归约，生成语法分析树成语法分析树输出产生式输出产生式2022-6-1935算符优先分析算法算符优先分析算法 算法算法5.3 算符优先分析算法。算符优先分析算法。输入：文法输入：文法G=(V,

23、T, P, S)，输入字符串，输入字符串w和优先关系表和优先关系表;输出：如果输出：如果w是一个句子则输出一个分析树架子，否则指出错误是一个句子则输出一个分析树架子，否则指出错误;步骤：步骤：begin S1:=#; i:=1;repeat 将下一输入符号读入将下一输入符号读入R; if Si T then j:=i else j:=i-1; while Sj R do beginrepeat Q:=Sj;if Sj-1 T then j:=j-1 else j:=j-2until Sj Q;将将Sj+1Si归约为归约为N; i:=j+1;Si:=N end; if Sj R or SjR t

24、hen begin i:=i+1; Si:=R end else erroruntil i=2 and R=# end;2022-6-1936id+id*id 的分析过程的分析过程id + id * id #算符优先分析算符优先分析控制器控制器E idE idE idE idE idE idE E E E * * E EE E + EE E + E算符优先关系表算符优先关系表# id#+#id+#+#*+#id*+#*+#+#2022-6-19375.2.4 优先函数优先函数n为了节省存储空间（为了节省存储空间（n2 2n）和便于执行比较运算，）和便于执行比较运算，用两个优先函数用两个优先函数

25、f和和g，它们是从终结符号到整数的映，它们是从终结符号到整数的映射。对于终结符号射。对于终结符号a和和b选择选择f和和g，使之满足：，使之满足：n f(a)g(b)，如果如果a b。n损失损失n错误检测能力降低错误检测能力降低n如：如：id id不存在，但不存在，但f(id)g(id)可比较可比较2022-6-1938表表5.2 对应的优先函数：对应的优先函数：1) 构造优先函数的算法不是唯一的。构造优先函数的算法不是唯一的。2) 存在一组优先函数，那就存在无穷组优存在一组优先函数，那就存在无穷组优先函数。先函数。+-*/()id#f22440440g113350502022-6-1939优先

26、函数的构造优先函数的构造算法算法5.4 优先函数的构造。优先函数的构造。输入：算符优先矩阵输入：算符优先矩阵;输出：表示输入矩阵的优先函数，或指出其不存在输出：表示输入矩阵的优先函数，或指出其不存在;步骤：步骤：1. 对对 a T#，建立以，建立以fa和和ga为标记的顶点；为标记的顶点；2. 对对 a, b T#，若，若a b或者或者ab，则从，则从fa至至gb画一条有向画一条有向弧；若弧；若a b或者或者ab，则从，则从gb至至fa画一条有向弧；画一条有向弧；3. 如果构造的有向图中有环路，则说明不存在优先函数；如如果构造的有向图中有环路，则说明不存在优先函数；如果没有环路，则对果没有环路，

27、则对 a T#，将，将f(a)设为从设为从fa开始的最长开始的最长路经的长度，将路经的长度，将g(a)设为从设为从ga开始的最长路经的长度。开始的最长路经的长度。 2022-6-1940例例5.10 Ges :EE+T|T TT*F|F Fid+*id#+*id#+*id#f2440g1350根据根据Ges的优先矩阵建立的的优先矩阵建立的有向图和优先函数有向图和优先函数 Ges的优先矩阵的优先矩阵2022-6-19415.2.5 算符优先分析的出错处理算符优先分析的出错处理 栈顶的终结符号和当前输入符号之间不存在任何优栈顶的终结符号和当前输入符号之间不存在任何优先关系；先关系； 发现被发现被“

28、归约对象归约对象”，但该，但该“归约对象归约对象”不能满足不能满足归约要求。归约要求。n对于第种情况，为了进行错误恢复，必须修改栈、对于第种情况，为了进行错误恢复，必须修改栈、输入或两者都修改。输入或两者都修改。n对于优先矩阵中的每个空白项，必须指定一个出错对于优先矩阵中的每个空白项，必须指定一个出错处理程序，而且同一程序可用在多个地方。处理程序，而且同一程序可用在多个地方。n对于第对于第种情况，由于找不到与种情况，由于找不到与“归约对象归约对象”匹配匹配的产生式右部，分析器可以继续将这些符号弹出栈，的产生式右部，分析器可以继续将这些符号弹出栈，而不执行任何语义动作。而不执行任何语义动作。20

29、22-6-1942算符优先分析法小结算符优先分析法小结n优点优点n简单、效率高简单、效率高n能够处理部分二义性文法能够处理部分二义性文法n缺点缺点n文法书写限制大文法书写限制大强调算符之间的优先关系的强调算符之间的优先关系的唯一性唯一性n占用内存空间大占用内存空间大n不规范、存在查不到的语法错误不规范、存在查不到的语法错误n算法在发现最左素短语的尾时，需要回头寻找对算法在发现最左素短语的尾时，需要回头寻找对应的头应的头2022-6-19435.3 LR分析法分析法 5.3.1 LR分析算法分析算法nLR(kLR(k) )分析法可分析分析法可分析LR(kLR(k) )文法产生的语言文法产生的语言

30、nL L ：从左到右扫描输入符号：从左到右扫描输入符号nR R ：最右推导对应的最左归约：最右推导对应的最左归约nk k ：超前读入：超前读入k k个符号，以便确定归约用的产生式个符号，以便确定归约用的产生式n使用语言的文法描述内涵解决句柄的识别问题，从语言的使用语言的文法描述内涵解决句柄的识别问题，从语言的形式形式描述描述入手，为语法分析器的入手，为语法分析器的自动生成自动生成提供了前提和基础提供了前提和基础n分析器根据当前的状态，并至多向前查看分析器根据当前的状态，并至多向前查看k k个输入符号，个输入符号，就可以确定是否找到了句柄，如果找到了句柄，则按相就可以确定是否找到了句柄，如果找到

31、了句柄，则按相应的产生式归约，如果未找到句柄则移进输入符号，并应的产生式归约，如果未找到句柄则移进输入符号，并进入相应的状态进入相应的状态2022-6-1944LR语法分析器的总体结构语法分析器的总体结构动作表动作表action状态状态/符号栈符号栈输入缓冲区输入缓冲区分析表分析表2022-6-1945LR 分析表分析表：actions,a；gotos,X LR(0)、SLR(1)、LR(1)、LALR(1)将以不同的原则将以不同的原则构造这张分析表构造这张分析表约定：约定：sn:将符号将符号a、状、状态态n压入栈压入栈rn:用第用第n个产生个产生式进行归约式进行归约2022-6-1946LR

32、分析器的工作过程分析器的工作过程n书上的下式（格局）书上的下式（格局）(s0s1sm，X1X2 Xm ， aiai+1an#)n在这里表示为在这里表示为s0s1sm#X1Xm aiai+1an#2022-6-1947LR分析器的工作过程分析器的工作过程nIf(shift i) then 格局变为格局变为2022-6-1948s0s1sm#X1Xm aiai+1an#If actionsm,ai=acc then 分析成功分析成功If actionsm,ai=err then 出现语法错出现语法错If(Reduce i) then 表示用第表示用第i个产个产生式生式进行进行变为变为then 变为

33、变为2022-6-1949LR分析算法分析算法 算法算法5.5 LR分析算法。分析算法。输入：文法输入：文法G的的LR分析表和输入串分析表和输入串w;输出：如果输出：如果w L(G)，则输出，则输出w的自底向上分析，否则报错的自底向上分析，否则报错;步骤：步骤：1将将#和初始状态和初始状态S0压入栈，将压入栈，将w#放入输入缓冲区；放入输入缓冲区；2令输入指针令输入指针ip指向指向w#的第一个符号；的第一个符号；3令令S是栈顶状态，是栈顶状态，a是是ip所指向的符号所指向的符号;4repeat5if actionS,a=Si then /* Si表示移进表示移进a并转入状态并转入状态i*/6

34、begin7 把符号把符号a和状态和状态i先后压入栈；先后压入栈；8 令令ip指向下一输入符号指向下一输入符号9 end2022-6-1950 10elseif actionS,a=rkthen /* ri表示按第表示按第k个产生式个产生式A归约归约 */11 begin12 从栈顶弹出从栈顶弹出2*|个符号；个符号；13 令令S是现在的栈顶状态；是现在的栈顶状态；14 把把A和和gotoS,A先后压入栈中；先后压入栈中；15 输出产生式输出产生式 A16 end17elseif actionS,a= acc then18 return19else20 error();2022-6-1951例

35、例5.12文法文法1) SBB2) BaB3) Bb分析表分析表请跟随讲请跟随讲解，快速解，快速抄下右侧抄下右侧的表格！的表格！2022-6-19520236#BaB # action(6,#)=r2栈栈 输入输入 动作说明动作说明0# bab# action(0,b)=s404#b ab# action(4,a)=r30#B ab# goto(0,B)=202#B ab# action(2,a)=s3023#Ba b# action(3,b)=s40234#Bab # action(4,#)=r3023#BaB # goto(3,B)=62022-6-1953规范句型活前缀规范句型活前缀n分

36、析栈中内容分析栈中内容+剩余输入符号剩余输入符号=规范句型规范句型n分析栈中内容为某一句型的前缀分析栈中内容为某一句型的前缀n来自分析栈的来自分析栈的活前缀活前缀(Active Prefix)n不含句柄右侧任意符号的规范句型的前缀不含句柄右侧任意符号的规范句型的前缀n例：例：id + id * id 的分析中的分析中n句型句型 E + id . * id 和和 E + E * . id活前缀活前缀活前缀活前缀S*rmAw rm 12w 2022-6-1954规范句型活前缀规范句型活前缀n规范归约所得到的规范句型规范归约所得到的规范句型(Canonical Sentential Form)的活前

37、缀是出现在分析栈中的活前缀是出现在分析栈中的符号串，所以，不会出现句柄之后的任何的符号串，所以，不会出现句柄之后的任何字符，而且相应的后缀正是输入串中还未处字符，而且相应的后缀正是输入串中还未处理的终结符号串。理的终结符号串。n活前缀与句柄的关系活前缀与句柄的关系n包含句柄包含句柄 A .n包含句柄的部分符号包含句柄的部分符号A 1. 2 n不含句柄的任何符号不含句柄的任何符号A. 2022-6-19555.3.2 LR(0)分析表的构造分析表的构造nLR(0)项目项目从产生式寻找归约方法从产生式寻找归约方法n右部某个位置标有园点的产生式称为相应右部某个位置标有园点的产生式称为相应文法的文法的

38、LR(0)项目项目（Item）n例例 S.bBB SbB.B Sb.BB SbBB.n归约（归约（Reduce）项目）项目: SaBB.n移进（移进（Shift）项目：）项目：S.bBBn待约项目：待约项目：Sb.BB SbB.B2022-6-1956项目的意义项目的意义n用项目表示分析的用项目表示分析的进程进程( (句柄的识别状句柄的识别状态态) )n方法：在产生式右方法：在产生式右部加一园点以分割已部加一园点以分割已获取的内容和待获取获取的内容和待获取的内容：构成句柄的内容：构成句柄b a b BBBSS B . B B . a B2022-6-1957拓广拓广(Augmented)文法文

39、法n需要一个对需要一个对“归约成归约成S” 的表示（只有一个接受状态）的表示（只有一个接受状态）n文法文法 G= (V, T, P, S)的拓广文法的拓广文法 G：nG=（V S，T，P SS，S）nS Vn对应对应S.S（分析开始）和（分析开始）和SS.（分析成功）（分析成功）n例例5.13 0) SS1) SBB2) BaB3) Bb2022-6-1958构造识别构造识别G G的所有规范句型活前的所有规范句型活前缀的缀的DFADFAn问题：如何设计能够指导分析器运行，问题：如何设计能够指导分析器运行，并且能够根据当前状态（栈顶）确定句并且能够根据当前状态（栈顶）确定句柄柄归约对象的头归约对

40、象的头的装置的装置2022-6-1959项目集项目集 I 的闭包（的闭包（Closure）CLOSURE(I)=I B.| A .BI, BP 算法算法 J:=I;repeat J=JB.|A.BJ, BPuntil J不再扩大不再扩大项目集闭包的计算项目集闭包的计算2022-6-1960闭包之间的转移闭包之间的转移n后继项目（后继项目（Successive Item）nA.X的后继项目是的后继项目是AX.n闭包之间的转移闭包之间的转移ngo(I,X)=CLOSURE(AX.| A.XI2022-6-1961状态转移的计算状态转移的计算n确定在某状态遇到一个文法符号后的确定在某状态遇到一个文法

41、符号后的状态转移目标状态转移目标function GO(I, X);beginJ:=;for I中每个形如中每个形如A.X的项目的项目dobegin J:=JAX. end;return CLOSURE(J)end; 2022-6-1962识别拓广文法所有规范句型活前缀的识别拓广文法所有规范句型活前缀的DFAn识别文法识别文法G=（V，T，P，S）的拓广文法）的拓广文法G的所有规范句型活前缀的的所有规范句型活前缀的DFA :M=(C, VT, go, I0, C)nI0=CLOSURE(S .SnC=I0I| JC,XVT,I=go(J,X)称为称为G的的LR(0)项目集规范族项目集规范族(C

42、anonical Collection)2022-6-1963计算计算LR(0)项目集规范族项目集规范族beginC := closure( S.S); repeat for IC， X VT if go(I,X) & go(I,X) C then C=Cgo(I,X) until C不变化不变化end.2022-6-1964例例4-13SBBBaBBbI0:S.SS.BBB.aBB.bSBabBabBab核心项目核心项目Kernel Item2022-6-1965LR(0)分析表的构造算法分析表的构造算法算法算法5.6 LR(0)分析表的构造。分析表的构造。输入：文法输入：文法G=(

43、V, T, P, S)的拓广文法的拓广文法G ;输出：输出：G 的的LR(0)分析表，即分析表，即action表和表和goto表表;步骤：步骤：1.令令I0= CLOSURE(S .S)，构造，构造G 的的LR(0)项目集规范族项目集规范族C= I0,I1,In2让让Ii对应状态对应状态i，I0对应状态对应状态0，0为初始状态。为初始状态。3for k=0 to n do begin if A.a Ik & a T & GO(Ik, a)=Ij then actionk,a:=Sj; if A.B Ik & B V & GO(Ik, B)=Ij then got

44、ok,B:=j; if A. Ik & A为为G的第的第j个产生式个产生式then for a T# do actionk,a:=rj; if SS. Ik then actionk,#:=acc end;4上述到步未填入信息的表项均置为上述到步未填入信息的表项均置为error。 2022-6-1966LR(0)不是总有效的不是总有效的( S S ) 1) S A|B2) A aAc3) A a4) B bBd5) B b上下文无关文法上下文无关文法不是都能用不是都能用LR(0)方法进行方法进行分析的，也就是分析的，也就是说，说，CFG不总是不总是LR(0)文法文法.2022-6-19

45、67SABabAabBcd2022-6-1968项目集项目集 I 的相容的相容n如果如果 I 中至少含两个归约项目，则称中至少含两个归约项目，则称 I 有归约有归约归归约冲突（约冲突（Reduce/Reduce Conflict）n如果如果 I 中既含归约项目，又含移进项目，则称中既含归约项目，又含移进项目，则称 I 有有移进移进归约冲突（归约冲突（Shift/Reduce Conflict）n如果如果 I 既没有归约既没有归约归约冲突，又没有移进归约冲突，又没有移进归约归约冲突，则称冲突，则称 I 是相容的是相容的(Consistent)，否则称，否则称 I 是不是不相容的相容的n对文法对文

46、法G，如果，如果 IC,都是相容的，则称都是相容的，则称G为为LR(0)文法文法2022-6-1969SABabAabBcd2022-6-19705.3.3 SLR(1)分析表的构造算法分析表的构造算法 算法算法5.6 LR(0)分析表的构造。分析表的构造。输入：文法输入：文法G=(V, T, P, S)的拓广文法的拓广文法G;输出：输出：G的的LR(0)分析表，即分析表，即action表和表和goto表表;步骤：步骤：1.令令I0= CLOSURE(S.S)，构造，构造G的的LR(0)项目集规范族项目集规范族C= I0,I1,In2让让Ii对应状态对应状态i，I0对应状态对应状态0，0为初始

47、状态。为初始状态。3for k=0 to n do begin if A.a Ik & a T & GO(Ik, a)=Ij then actionk,a:=Sj; if A.B Ik&B V&GO(Ik, B)=Ij then gotok,B:=j; if A. Ik & A为为G的第的第j个产生式个产生式then for a FOLLOW(A) do actionk,a:=rj; if SS. Ik then actionk,#:=acc end;4上述到步未填入信息的表项均置为上述到步未填入信息的表项均置为error。 识别表达式文法的所有活前缀的

48、识别表达式文法的所有活前缀的DFA 拓广文法 0) 1) + 2) 2022-6-1972ETF(id+*ETF(idTF(idF()+*id2022-6-1973表达式文法的表达式文法的 LR(0)分析表含有冲突分析表含有冲突n在状态 2、9 采用归约，出现移进归约冲突ACTIONACTION 状状态态 id + * ( ) # id + * ( ) # 2 2 3 3 5 5 9 9 1010 1111 r2 r2 r2/s7 r2 r2 r2 r2 r2 r2/s7 r2 r2 r2 r4 r4 r4 r4 r4 r4 r4 r4 r4 r4 r4 r4 . . r6 r6 r6 r6

49、r6 r6 r6 r6 r6 r6 r6 r6 . . r1 r1 r1/s7 r1 r1 r1 r1 r1 r1/s7 r1 r1 r1 r3 r3 r3 r3 r3 r3 r3 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 r5 r5 r5 r5 r5 r5 r5 2022-6-1974表达式文法的表达式文法的SLR(1)分析表分析表n求非终结符的求非终结符的 FISRT 集集和和 FOLLOW 集集nFIRST( F ) = id, ( nFIRST( T ) = id, ( nFIRST( E ) = id, ( nFOLLOW( E ) = ), +, # nFOLLO

50、W( T ) = ), +, #, * nFOLLOW( F ) = ), +, #, * 2022-6-1975 si 表示移进到状态表示移进到状态i, ri 表示用表示用i号产生式归约号产生式归约A A C C T T I I O O N N G G O O T T O O 状状态态 i i d d + + * * ( ( ) ) # # E E T T F F 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 1 0 0 1 1 1 1 s s 5 5 s s 4 4 s s 6 6 a a c c c c r r 2 2 s s 7 7 r r 2 2

51、 r r 2 2 r r 4 4 r r 4 4 r r 4 4 r r 4 4 s s 5 5 s s 4 4 r r 6 6 r r 6 6 r r 6 6 r r 6 6 s s 5 5 s s 4 4 s s 5 5 s s 4 4 s s 6 6 s s 1 1 1 1 r r 1 1 s s 7 7 r r 1 1 r r 1 1 r r 3 3 r r 3 3 r r 3 3 r r 3 3 r r 5 5 r r 5 5 r r 5 5 r r 5 5 1 1 2 2 3 3 8 8 2 2 3 3 9 9 3 3 1 1 0 0 2022-6-1976SLR(1) 分析的特点

52、分析的特点n描述能力强于描述能力强于 LL(1) nSLR(1)还考虑还考虑Follow集中的符号集中的符号nLL(1) 仅考虑产生式的首符号仅考虑产生式的首符号nSLR(1) 文法：文法：SLR(1)分析表无冲突的分析表无冲突的CFG2022-6-1977SLR(1)分析的局限性分析的局限性n如果如果 SLR(1) 分析表仍有多重入口（移分析表仍有多重入口（移进归约冲突或归约归约冲突），则说进归约冲突或归约归约冲突），则说明该文法不是明该文法不是 SLR(1) 文法；文法；n说明仅使用说明仅使用 LR(0) 项目集和项目集和 FOLLOW 集集还不足以分析这种文法还不足以分析这种文法2022

53、-6-1978I0:S.SS.L=RS.RL.*RL.idR.LI1:SS.I2:SL.=RRL.LI3:SR.RI4:L*.RR.LL.*RL.idI5:Lid .*idI6:SL=.RR.L L.*RL.id=I7:L*R.RI8:RL.LI9:SL=R.R*LidS2022-6-1979SLR分析中的冲突分析中的冲突需要更强的分析方需要更强的分析方法法 I2 =S L.=R, R L. n输入符号为输入符号为 = 时，出现了移进归约冲突：时，出现了移进归约冲突： S L .=R I2 and go(I2,=)=I6 action2,= = Shift 6 R L . I2 and = F

54、OLLOW(R)=,# action2,= = Reduce R Ln说明该文法不是说明该文法不是SLR(1)文法，分析这种文法需要更多文法，分析这种文法需要更多的信息。的信息。2022-6-1980SLR分析中存在冲突的原因分析中存在冲突的原因nSLR（1）只孤立地考察输入符号是否属于归约项目）只孤立地考察输入符号是否属于归约项目A.相关联的集合相关联的集合FOLLOW（A），而没有考察符号），而没有考察符号串串所在规范句型的所在规范句型的“上下文上下文”。n所以试图用某一产生式所以试图用某一产生式A归约栈顶符号串归约栈顶符号串时，不仅时，不仅要向前扫描一个输入符号，还要查看栈中的符号串要向

55、前扫描一个输入符号，还要查看栈中的符号串，只有当只有当Aa的确构成文法某一规范句型的活前缀时才能的确构成文法某一规范句型的活前缀时才能用用A归约。归约。亦即要考虑归约的有效性：亦即要考虑归约的有效性：n问题：怎样确定问题：怎样确定Aa是否是文法某一规范句型的活前缀是否是文法某一规范句型的活前缀2022-6-19815.3.4 LR(1)分析表的构造分析表的构造nLR(0)不考虑后继符不考虑后继符(搜索符搜索符)，SLR(1)仅在归仅在归约时考虑后继符约时考虑后继符(搜索符搜索符)，因此，对后继符，因此，对后继符(搜搜索符索符)所含信息量的利用有限，未考虑栈中内容。所含信息量的利用有限，未考虑栈

56、中内容。n希望在构造状态时就考虑后继符希望在构造状态时就考虑后继符(搜索符搜索符)的作的作用：考虑对于产生式用：考虑对于产生式 A的归约，不同使用位的归约，不同使用位置的置的 A 会要求不同的后继符号会要求不同的后继符号2022-6-1982后继符后继符(搜索符搜索符)的概念的概念EE + T( E )T * F 不同的归约中有不同不同的归约中有不同的后继符。的后继符。 特定位置的后继符是特定位置的后继符是FOLLOW集的子集集的子集2022-6-1983LR(k) 项目项目n定义定义5.11n A.,a1a2ak为为LR（k）项目）项目，根据圆点所处，根据圆点所处位置的不同又分为三类：位置的

57、不同又分为三类：n归约项目归约项目: A.,a1a2akn移进项目：移进项目：A.a,a1a2akn待约项目：待约项目：A.B,a1a2akn利用利用LR(k)项目进行项目进行(构造构造)LR(k)分析分析(器器)，当，当k=1时，为时，为LR(1)项目，相应的分析叫项目，相应的分析叫LR(1)分分析析(器器)2022-6-1984LR(1) 项目的有效性项目的有效性n形式上形式上n 称称LR(1)项目项目A.,a对活前缀对活前缀=是有效的，如果存是有效的，如果存在规范推导在规范推导nS *Aw wn其中其中a为为w的首字符，如果的首字符，如果w=，则，则a=#n与与LR(0)文法类似，识别文

58、法全部活前缀的文法类似，识别文法全部活前缀的DFA的每的每一状态也是用一个一状态也是用一个LR(1)项目集来表示，为保证分析项目集来表示，为保证分析时，每一步都在栈中得到规范句型的活前缀，应使每时，每一步都在栈中得到规范句型的活前缀，应使每一个一个LR(1)项目集仅由若干个对相应活前缀有效的项项目集仅由若干个对相应活前缀有效的项目组成目组成2022-6-1985识别文法全部活前缀的识别文法全部活前缀的DFAnLR(1) 项目集族的求法项目集族的求法nCLOSURE（I）：求）：求I的闭包，目的是为了合并某的闭包，目的是为了合并某些状态，节省空间些状态，节省空间nGO（I，X）：转移函数）：转移

59、函数2022-6-1986闭包的计算闭包的计算nCLOSURE(I)的计算的计算n(核心位置：核心位置：A.B,a 扩展成扩展成闭包闭包)n同时考虑可能出现的后继符同时考虑可能出现的后继符nb FIRST( a ) 2022-6-1987闭包的计算闭包的计算n如果如果A.B,a对对=有效有效 /*即存在即存在S*Aaxax*/n假定假定ax*by，则对任意的，则对任意的B有：有：nB.，b对对=也是有效的，其中也是有效的，其中nbFIRST（a）2022-6-1988闭包的计算闭包的计算J:=I; repeat J=JB.,b|A.B,aJ, bFIRST(a)until J 不再扩大不再扩大

60、n当当+时，此时时，此时b=a叫继承的后继符，否则叫继承的后继符，否则叫自生的后继符叫自生的后继符2022-6-1989状态状态 I 和文法符号和文法符号 X 的转移函数的转移函数go(I,X) = closure(AX.,a|A.X,aI)2022-6-1990计算计算LR(1)项目集规范族项目集规范族C=I0I| JC，XVT，I=go(J,X)称为称为G的的LR(1)项目集规范族（算法：项目集规范族（算法：P185) beginC:= closure( S.S,#); repeat for IC， X VT if go(I,X) & go(I,X) C then C=Cgo(I,X) until C不变化不变化end.2022-6-1991识别活前缀的关于识别活前缀的关于LR(1) 的的DFAn识别文