编译原理 课件 第三章 语法分析3.ppt

1、3.4自下而上语法分析，牙齿部分为1 .要熟悉自下而上语法分析的基本思想和基本概念。2.运算符首先理解语法分析3。掌握方向盘的定义和判定4。理解规范归属过程和LR分析过程的实现5。了解LR语法分析的实现过程，示例回顾：简单的归化过程，语法设置Abcde，语法树的自下而上构建过程，文章分析：AB BCDE Abcde Aacde Aacde Acbes，最右侧的推导，注意：每个回归都是句柄，3.4.1如果重复牙齿过程，直到堆栈中只剩下语法的起始符号，分析就会成功。这被称为“转入-回药”方法。从语法树的角度来看：从语法树的树叶开始逐步构建配置分析树，直到形成根节点。是推理的逆过程。“移动-减少”分

2、析、移动-减少分析器使用分析堆栈和输入缓冲区。1，文章表示法：堆栈内容输入缓冲区内容#当前文章模式#，2，分析器结构，“移动-减少”分析的堆栈实现“移动-减少”分析器使用保留堆栈和输入符号字符串W的缓冲区。分析器的初始状态是：堆栈输入W操作过程。从左到右将字符串W的符号移动到堆栈中，在堆栈顶部形成可还原字符串(如句柄)时，就承诺了。牙齿减少可能会持续很多次，直到堆栈顶部不再出现控制柄。然后是堆栈输入S，2)折叠：当堆栈顶部符号字符串形成可折叠字符串(例如句柄)时，直接折叠(即，将堆栈顶部的句柄替换为结果左侧的非终结器)。3)接受：在堆栈底部只有“#”和开始符号，输入也是在到达右端符号“#”时识

3、别符号字符串是句子，表示分析成功的特殊情况。4)发生错误：堆栈顶部的内容与输入符号相反。也就是说，如果识别器发现输入符号字符串不是句子，则会出错。注：决定转入和归药的依据是什么？堆栈顶部是否显示可收拢的符号字符串。修剪语法树以演示复合，S，AB，AAB，BD，SAACBE AB | B BD，合同是将堆栈顶部的符号字符串替换到语法生成表达式的左侧。合同可以多次重复，也可以继续移动。如果最终可以归于成文法的起始符号，那么分析是成功的。否则，将出现错误。牙齿方法通常通过最右侧的导数得到，因为它总是用非终止符替换文章模式最左侧的可还原字符串。核心：如何标识可收拢的符号字符串？徐璐通过不同的自下而上分

4、析算法徐璐不同的算法对可还原字符串徐璐有不同的定义，但在分析过程中都有共同的特征。也就是说，边缘向内，进行边药()。(David aser，Northern Exposure(美国电视电视剧，英语)，specification down:使用句柄定义可还原字符串运算符。使用最左侧的子面域定义可还原字符串。自下而上语法分析主要有三种茄子简单的优先级分析(规范减少)语法：根据特定原则规定语法符号的优先关系。运算符优先级分析(非标准返回)指定运算符之间的优先级关系。LR分析方法(规格减少)LR(0)、LR(1)、SLR(1)和LALR(1)。，规范归约相关概念复习，语法G，开始符号S，S=xy的话，

5、xy是语法G的文章模式，x，y是任意符号字符串。文章xy的语法，相对于非终结器A(如果S=xAy存在而A=存在)。如果S=xAy且具有a，则为相对于a的文章xy的直接球体。一个文章图案最左侧的直接球体称为手柄。文章模式语法直接语法句柄*、*、*、*、*、注3360使用规范减少算法，每个合同部分都是解析为句柄的字符串。因此，规格回归中的重要问题将转换为标识句柄的方法。练习语法如下： EE T | T TT * F | F F F(E)| id分析输入字符串id*id，提供文章“移动-减少”解析过程。堆栈输入缓冲区操作# id id*id#移动#id id*id#减少Fid #F id*id#减少

6、TF #T id*id#减少ET #E id*id#移动# 转至E=E T=E T * f=E T * id=E f * id=E id * id=T id * id=f id * id=id id * id，转至回归分析期间出现的问题以上实例9 收阖-收阖冲突具有两个可选处理码，用于收阖堆叠顶部符号。例如，在上述步骤12)中，您可以使用TF承诺，或按TT*F承诺。在各种分析方法中处理冲突的技术不同！3.4.2运算符优先级分析，运算符优先级分析的想法源于表达式分析，利用相邻终止符号之间的关系寻找可还原字符串。将文章模式中的结束符号视为“运算符”，并通过运算符之间的优先级关系确定文章模式中的“可

7、收缩字符串”。在一个符号字符串中，两个相邻的结束符号A和B之间只能有四个茄子优先级关系，其中(1) a，B优先级相同，记录为a b。(2) a优先于b，写为a b。(3) a优先级低于b，记录为a b。(4) a和B不能相邻。也就是说，牙齿字符串不是文章模式(出现错误)。如果上述四种茄子关系都不能同时成立，可以根据终止符号之间的归约关系进行句法分析。附注：在整个合约过程中起决定性作用的是连接两个终结器的优先关系。1，运算符语法：上/下相关语法G，没有P，没有P.QR.如果(P，Q，R是非终结器)，则G是运算符语法。2，定义运算符优先级关系：假设GS是没有算术的运算符语法。对于所有终结器A和B对

8、：a b，对于GS，P.ab.或P.aQb.只有存在的情况下(相同的生产方式)；g表示P.Rb.具有的生成表达式，R=.a或R=.aQ (ab相邻)，运算符优先语法，yes语法ge:ee | e * e | (e)，因为ee，EE*E有*，而ee * e，EE有*，所以运算符优先语法不是，3 .运算符优先语法运算符方法G的终止符a，b之间可能没有优先级关系。如果有优先关系，大部分情况下其中一个成立，G就是运算符优先语法。以表格格式表示运算符优先级关系表的配置，以及每个结束符号的优先级关系。这些表格称为优先顺序表格。配置优先级关系表的方法根据定义的手动计算使用算法，F(E)中的(=)，yes语法

9、ge 3360 ee T | T TT * F | F F F F(E)| I查找运算符优先级表。终结器#、终结器#、终结器#和与其他终结器A相关的关系： # #、GE的运算符优先级关系表：优先级表中的空部分是无效关系。同一终结器之间的优先级关系不一定是这样的。如果有A b，则不一定有b a(没有传递性)。运算符优先级仅定义相邻运算符之间的优先级关系。a，b相邻时，b，a不一定相邻。a，b之间可能没有优先关系。，描述，1，FIRSTVT集合定义：每个非终止符P，FIRSTVT(P)=a|P=a.或P=Qa.针对、aVT、Q VN，根据以下两个茄子规则配置first生成的PR.如果有牙齿并且有a

10、FIRSTVT(R)，则位于a FIRSTVT(P)中。2，LASTVT集合定义：LASTVT(P)=a|P=.a或P=P.aQ、aVT、Q VN和以下两个茄子规则构成LASTVT集合：生成P时生成的P.R如果有牙齿并且有aLASTVT (R)，则为a LASTVT (P)。3，如果每个FIRSTVT和LASTVT集(而不是配置优先级关系表终结点)已知，则可以配置优先级关系表。在生成式的右侧.应收帐款.如果，则每个bFIRSTVT(R)都有a b。在生成式的右侧.如果存在Rb，则每个aLASTVT(R)集都有a b。如果生成格式等于Pab或PaQb，则存在ab。示例3.11语法ge:ee t

11、| t TT * f | f f f (e) | I试验性地配置运算符优先级表。配置FIRSTVT集。(1)根据规则，EE为first vt(E)=；在TT*中，first vt(T)=*；F(和Fi中的FIRSTVT(F)=(，I；(2)根据规则，FIRSTVT(F )=(，I和TF为FIRSTVT(T)=*，(，I；FIRSTVT(T)=*，(，I和ET得到FIRSTVT(E)=，*，(，I)。配置LASTVT集。(1)根据规则，E T中的last vt(E)=；在T*F中，last vt(T)=*；F)和Fi中的LASTVT(F)=)，I；(2)根据规则，LASTVT(F )=)，I和T

12、F为LASTVT(T)=*，)，I；LASTVT(T)=*，)，I和ET得到LASTVT(E)=，*，)，I。ee TT TT * ff (e) | i，3，配置优先级关系表。(1)根据规则，“(e)”得到()。(2)根据规则，E T表示FIRSTVT(T)，即*，(，I；在T*F中，输入* FIRSTVT(F)或*(，I；F(E (FIRSTVT(E)，即(，*，(，I；(3)根据规则，EE为LASTVT(E)，即*，)，I；在TT*中，LASTVT(T) *，即*，)，I *；FE)得到LASTVT(E)，即*，)，I)。GE中的运算符优先级关系表：此外，#E#中的# # #；# FIRS

13、TVT(E)或#，*，(，I；LASTVT(E) #，即*，)，i #。通过比较终结符之间的优先级关系，实现了运算符优先级分析的设计。根据优先级分析的原理：解析器的任务是继续移动到输入符号，识别可还原字符串，并签订合同。问题：如何识别可还原字符串？分析的基本方法：根据优先级关系“上”识别可还原字符串的结尾，根据优先级关系“下”识别可还原字符串的头。分析堆栈保留标识的部分，比较堆栈顶部与下一个输入符号的关系，如果是可折叠字符串的末尾，则沿着堆栈顶部查找可折叠字符串的头部，找到后弹出，将其分类为非终结符。附注：各种优先关系已经存在于优先关系表中。分析输入字符串：I I # # # # # # #

14、# # # # E #，表达式语法ge : ee t | t TT * f | f f f f(E)| I，如您所见，每个回归都不是句柄最左侧的小球：表示文章图案最左侧的小球。回忆：怎么找到小球和最左边的小球？是表达式语法的文章模式：T * F I查找球体、子球体和最左侧的子球体。ee TT tT * Ff (e) | I，短语I，T * F，T * F I像素短语：I，T * F最左边的像素短语：T * F，运算符语法g之一Ai VT)# n1a 1 n1.ai-1ai、aiai 1；摘要：运算符优先级分析过程文章模式的通用格式： # N1 A1 N2 A2.NNA NNNNN1 #(其中ai是终结点，Ni是可选的非终结点)从左到右扫描每个符号，然后依次查看运算符优先级表并继续移动，直到找到满足ai ai 1的终结点。从Ai开始向左扫描，直到找到满足关系aj-1 aj的终结点。牙齿时的NJAJ NJ1 AJ1.子字符串(如NIAI NI 1)是最左边的像素，必须约定。分析进程结束：分析堆栈中的#S，输入字符串为#。，k=1；sk=#；Do将以下输入符号读取为a:if(sk Vt)j=k else j