6-自底向上优先分析法.ppt

第6章自下而上优先分析法，6.1的概要，从左到右扫描分析的符号串，输入符号堆栈，堆栈顶部的符号串形成某个句型的句柄或可约列(与某个生成式的右部对应)后，代替该右部的语法符号，使用该生成式的左部非终结符号汇总成识别符号。 在分析过程中，每次总结的是最左边的简短短语(或其他短语)。 从语法树的观点出发，将输入符号作为树的末端节点，在根节点方向构筑语法树。 另外，所讨论的前提与从上到下的技术一样，没有考虑符号的具体构成方案。 认识过程从左向右，从下向上进行。 一般采用规则摘要。 所有步骤都概括了句柄(例外除外)。 采用6.1概述、基本方法、移入-合同方法。 要存储聚合符号，请使用堆栈。 在分析过程中，识别程序不断地移动到符号中。 移动的符号暂时存储在堆栈中。 一旦所填入的(通过和约得到的)符号串包括句柄，该句柄就被合并成对应的非终止符号。 另外，参照教科书P102例6.1、6.1的概要，基本的方法(续)是合同中的动作有4种，读入一个符号并将其汇集到堆栈中。 约束：当堆栈中的部分形成方向盘(堆栈顶部的符号序列)时，约束方向盘。 受理：堆栈中的符号只有#和识别符号时，输入符号也到达末尾时，执行受理动作。 错误处理：识别程序发现输入符号串不是句子时，会发生错误，调用错误处理模块。 6.1概述，示例I * iii * iie :3360=ie * ie * ie * ie * iie :3360=ie * ie * ie * ee :5360=e * eeee 3:=ee语法ge e 33330 e|(e )输入符号串： i*I处理未处理句型句柄规则，不使用此页面，在例子的解释中堆栈中符号堆栈的上部无法处理时，进行移动操作。 发现堆栈上部的分形成了方向盘，就预约那个方向盘。 把手堆叠起来，把得到的非终结符号堆叠起来。 在输入是句子的情况下，堆栈内的符号(从下到上)和未处理的符号构成句子类型。 例子发现方向盘和归纳是人为干预的结果。 不是实际可行的技术，而是技术模板。 如何找到不使用此页面的基本问题，直接签约的简单短语？ 也就是说，您如何认识到堆栈顶端的符号串形成了手柄？ 什么时候签约？把找到的简单短语汇总成哪个非终结符号？ 如何选择合适的生成公式来签订合同？ 概括为什么，6.1的概要，2个方法，简单优先分析法：求出这个语法的所有符号(终止符号和非终止符号)之间的优先关系，根据这个关系决定归约过程的句柄。 规范合同。 分析准确的规范，但效率差，不实用。 运算符优先分析法：规定运算符间的优先关系，也就是说只考虑终止符号间的优先关系，不考虑非终止符号的优先关系。 不是规范的归约。 分析速度快，适用于公式的分析。 基本思想，6.1概况，6.2简单优先分析法，思路：每次看到句型中相邻的两个符号，就判定句柄的末尾。 然后，反方向找出方向盘的头部。 找到方向盘。 优先关系和书的写法不同。 等效于： sisj在目的地： sisj之后： sisj注意： 22222222222222222222222 sjsi :当时，仅通过UVW，v和w分别满足V=Sj*W=Si，并且si是终止符号。 另外，优先关系的例子，语法： SbAbA(B|aBAa )语言：bab，b(aa)b，b(aa)a)b，可以从语法树导出部分优先关系。 优先矩阵可以将优先关系记入一个矩阵，得到优先矩阵。(将矩阵设为关系的表现形式)，=，#b(aa)a)b#，把手：a约为a，#b(aa)a)b#，=，把手：Aa约为b，#b(Ba)b#，=，把手：(B约为a，识别过程(续)，#b(Bb#，=)，把手3360 (ba ) b #，=) 手柄：Aa )约为b，#b(Aa)b#，=，手柄：Aa )约为b，#bAb#，=，手柄：bAb约为s，#b(Bb#，=，手柄：(B约为a，优先关系的结构根据优先关系的结构定义(定义6.1 )，我们立即构建(1)=的构造：按规则的右部直接处理，对于右部X1X2Xn全部设为Xi=Xi 1。 根据(2)的结构：通过定义，SjSi得到存在规则USjV，即Sj=V、头(v )= sk|v=sk = si-1、Si2、Sin。Sj，Si1Si2Sin，(3)关系的结构：定义，SjSi表示：存在规则UVW中的V=W TAIL(V)=Sl|V=Sl=Sj1，Sj2，Sjm。 头部(w )= sk|w=sk = si 1，Si2，Sin。Sj1、Si1Si2Sin、Sjm，简单优先关系矩阵(表)、语法： sBaba(b|abaa ) head (a )= (a head (b )= (aa tail (a )= a ) b )，优先关系的冲突在优先矩阵中出现值不唯一的要素、单纯优先语法，如果满足定义6.2语法，词汇表的任意两个符号之间至多成立一个优先关系。 任何两个规则式的右部都不同。 这个语法叫做简单优先语法。 第一点保证可以识别方向盘。 第二点保证可以决定归属于哪个非终结符号。 定理6.4，简单的优先级语法是无意义的，并且任何语法类型SmSn的唯一句柄都满足Sj-1Sj=Sj 1=Sj 2=Si-1=SiSi 1的最左侧子符号串SjSj 1Sj 2Si-1Si。 定理6.4的证明首先用反证法证明任何句型的句柄是唯一的。 句型中必定存在句柄，如果该句柄必须满足SJ-1SJ=SJ1=SJ2=si-1=sisi1(句柄1 )，则与其对应的约束(称为约束过程2 )不一定将上述句柄约束为一个整体。 在归约过程2中，如果第一次将方向盘Sj-1和Si 1的中间符号St归约为方向盘(方向盘2 )的一部分(下一页)，则定理6.4的证明(续)，如果t=j-1，则为方向盘1，Sj-1Sj； 手柄2，Sj-1=Sj或sj-1sj； 矛盾！ 如果t=i 1，则手柄1、sisi1手柄2、sisi1或Si=Si 1。 当i=ty时，在y中也不包括相邻的非终止符号。 假设x=wUv，y=wuv。 因为x中不包含相邻的2个非终结符号，所以没有不与w和v相邻的非终结符号。 根据运算符语法的定义，u中也不包含相邻的非终结符。 根据假设，w的末尾不是非终止符号(否则包括与x相邻的非终止符号)。 类似地，v的起始符号也不是非终止符号。 根据以上可知，在y中不存在相邻的非终止符号。 定理6.6和6.7的证明假设w=xvy是语法的句型，v是对于v的短语。 xVy也是句型。 如果有两个与w相邻的符号TU，t在v，u不在v。 u是y的首字母。 因此，在xVy中存在2个相邻的非终端符号VU。 与定理6.5矛盾。 定理6.7的证明与定理6.6相似。 另外，运算符优先关系，定义6.5语法g是一个运算符语法，Tj和Ti定义了两个任意的终止符号，u、v、WVN运算符的优先关系：在语法g中仅存在u:30=tji或u :30=tji这样的形式的规则： u:30=tjv这样的规则是语法g v=ti或v=wti这种形式的规则只存在于语法g中，V=Tj或V=TjW这种形式的规则只存在于语法g中。、运算符优先关系的直观意义，运算符优先分析技术的基本思想，通过终端符号间的优先关系，决定句型的句柄。对于句型 n1 t1 ni-1 ti-1 ni ti NJ TJ NJ1 TJ1 NK tk NK1，满足关系ti-1titi 1=TJTJ 1的最左侧子符号串是约束事件。 优先关系示例语法： z :30=ee :30=t|eett :30=f|t * ff :30=(e )|I等价关系： () zeetefizeete * fet * (e )et * (et ) zeee te te t fe t (e )表示得到以下关系：I，铿锵铿锵锵锵6关系和的构造中，需要引入FIRSTTERM和LASTTERM这2个辅助关系。 如果存在规则u:30=t或u:30=vtulasttermt并且仅存在规则u 336030=t或u:30=TV、FIRSTTERM关系的结构，则FIRSTTERM不是FIRSTTERM的传输闭包。 UFIRSTTERM T表示t是u经过几个步骤导出的单词的第一个终止符号。 结构算法在步骤UFIRSTTERMT中为UFIRSTTERMT .步骤2:u:3360=v，在VFIRSTTERM T中为UFIRSTTERMT。 步骤3 :重复步骤2，直到进程收敛。 LASTTERM的构造算法，LASTTERM不是LASTTERM的传递闭包。 ULASTTERM S表示u经过几个步骤导出的字符的末尾符号是s。 对于步骤ULASTTERMT，生成算法为ULASTTERMT。 步骤2:u:30=v，如果是VLASTTERM T，则为ULASTTERM T。 步骤3 :重复步骤2，直到收敛为止。 关系与关系的构造，关系的构造：卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡，识别算子优先句法类型，算子优先分析技术在分析过程中，非终结符号是“看不见”。 因此，单规则中不能对应运算符优先技术。 6.7定义元素句子是满足以下条件的句子： (1)包括至少一个终止符号： (2)该短语不包括符合初始条件的较小短语。 另外，在词素短语的实例中，短语是T*F、T*F、T*F，最左边的t和I。 其中，词素短语是T*F，I。 T*F、T*F不是短语，因为它们包含T*F。 t不是素句。 因为它不包含终结符。 定理6.8，定理6.8 :句型 n1 t1 ni-1 ti-1 ni ti NJ TJ NJ1 TJ NK tk NK1中关系ti-1titititititititititititi 65 编译器不考虑具体符号的名称，只考虑其含义。 需要处理词素短语的语义处理子例程。 在使用算符优先技术的过程中，可以用相同的符号n表示通过合同获得的非终止符号，并且也可以执行分析过程。 识别算法的流程图，开始、i=1； Si=#，r=下一个symbol，SiVT或Si=#，j=i-1，j=i，SjR，no，i=i 1； Si=R，a，n，y，y，识别算法流程图(续)，a，Q=Sj； 在j=j-1，SjVT，j=i-1，Sju=w且从u到w的导出过程中，只使用u:30=w这样的单一规则。 u、w是非终结符号。 优先级函数可以用于、实用算子优先级分析技术来代替优先级矩阵。 优先函数的求解方法与