编译原理电子课件教案-第6章-自底向上优先分析法.pptx

1,第六章自底向上优先分析法,2,本章内容,引子：自底向上分析的一般原理6.1自底向上优先分析概述6.2简单优先分析法（了解）6.3算符优先分析法,3,一、自底向上分析的基本思想对输入串从左到右扫描，并逐个移入栈中。边移入边分析，一旦栈顶符号串形成某个句型的可归约串（它对应某产生式右部），就用该产生式左部的非终极符号代替它，完成进一步归约。重复这一过程直到归约到栈中，只剩下开始符号和右边界符#，成功。否则，报错。,引子:自底向上分析的一般原理,4,例.(p94)(1)SaAcBe(2)Ab(3)AAb(4)Bd,对输入串abbcde#语法分析走一遍动作。符号栈输入串0#abbcde#1#abbcde#2#abbcde#用Ab归约3#aAbcde#4#aAbcde#用AAb归约5#aAcde#6#aAcde#7#aAcde#用Bd归约8#aAcBe#9#aAcBe#用SaAcBe归约10#S#,5,二、自底向上分析的关键,如何精确定义可归约串并识别。对可归约串(p23)的不同定义形成不同的自下而上分析方法：1.在规范归约分析中，用句柄来刻画可归约串(LR,简单优先)2.在算符优先分析中，是用最左素短语来刻画可归约串。根据识别可归约串的不同方法，也形成不同的自下而上分析法。简单优先分析法和LR分析法都是规范归约分析法（句柄可归约串），但它们识别句柄的方法不同：1.LR分析法是根据历史、现实、展望三者信息来确定栈顶符号串是否形成句柄2.简单优先分析法是根据文法符号之间的优先关系来确定句柄。,6,6.1自底向上优先分析法概述,1.简单优先分析法：对一文法求出所有符号之间的优先关系，并据此确定句柄（规范归约）2.算符优先分析法：只考虑算符之间的优先关系，不考虑VN的优先关系。只要找到可归约串就归约，并不考虑归约到哪个非终极符。,7,6.2简单优先分析法（了解）,6.2.1优先关系X=YiffAXYXYiffABD且BX和DY例6.2SbAb,A(B|a,BAa)(1)相等：b=A，A=b，(=B，A=a，a=)(2):由SbAb,A(B|a及BAa），可得Bb，Baab，aa)b，)a,+,+,+,8,6.2.2简单优先文法的定义,一、定义简单优先文法满足两个条件（1）任意两个文法符号之间最多只有一种优先关系成立（2）在G中任意两个产生式没有相同的右部（归约唯一）分析：栈顶为aiaiai+1归约（已形成句柄）,9,二、简单优先分析法,步骤：构造文法的优先关系矩阵，将G规则保存，设置符号栈S（1）将输入串a1,a2,an#逐个移入符号栈S中，直到栈顶符号aiai+1为止。（2）栈顶ai为句柄尾，由此向左在栈中找句柄开头符号ak（找到ak-1+(-)*(满足左结合)#故由定理，N2a2N3即T*F是最左素短语,31,3.算符优先分析算法,算符优先分析时自底向上的分析，也为自左向右归约，它不是规范归约算符优先分析的关键：如何找最左素短语NiaiNi+1ai+1NjajNj+1，即满足：ai-1aj+1在当前句型中存在符号串的符号个数与该素短语的符号个数相等，非终极符对应NK(k=i,j+1)，不管符号名是什么，终极符对应ai,aj,名字与实际名一样，位置也一致，才有可能形成素短语。,32,在分析过程中设置一个符号栈S，存放归约或待形成最左素短语的符号串，a存放当前读入符号归约成功的标志是：读到句子结束符#。栈中归约到只剩下#N。在归约时要检查是否有对应规则的右部与Sj+1Sk相符，若有才可归约。,3.算符优先分析算法,33,6.3.6算符优先分析法的局限(p115),虽然，算符优先分析法比规范归约快得多，因为算符优先分析法跳过了所有非终结符之间的归约。这既是它的优点，也是缺点。因为：忽略VN在归约工程中的作用，存在