编译原理实用教程 杨德芳 第5章 自底向上优先分析技术

《编译原理实用教程 杨德芳 第5章 自底向上优先分析技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章自底向上优先分析技术本章学习目标自顶向下分析法是从文法的识别符开始，试图推导出输入符号串；自底向上分析方法与自顶向下的分析方法完全相反，它从输入符号串出发，试图归约到文法的识别符。本章要点：自顶向下分析法的基本原理简单优先分析技术算符优先分析法优先函数5.1自底向上分析方法从语法分析的角度考虑，自底向上的语法分析过程就是以输入符号串为语法树的末端结点符号串，试图向着根结点方向向上构造语法树，使识别符号正是语法树的根结点。5.1.1自底向上分析的基本思想基本思想是：对输入符号串自左向右进行扫描，并将输入符逐个移进一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个

2、句型的句柄或可归约串，就用该产生式的左部非终结符代替相应右部的文法符号串，称这一步为归约。重复这一过程直到归约到栈中只剩文法的开始符号则为分析成功，就确认该输入串为文法的句子。例5.1给出文法AaBbBBb

3、b给定某个符号串“abbb”，判定该输入串是否合法。步骤分析栈句柄输入串动作1#abbb#移进2#abbb#移进3#abbbb#用Bb归约4#aBbb#移进5#aBbBbb#用BBb归约6#aBb#移进7#aBbaBb#用AaBb归约8#A#接受abB（a）abBbB（b）AabBbBb（c）图5-1语法树的构造在上例中的移进—归约过程中的第7步中，栈顶中出

4、现的符号可以认为是Bb或aBb,在归约时是用Bb还是aBb，就要作出选择，如果选择Bb，则归约的结果是aA，aA就不能再归约，必须退回重新选择，选择aBb作为可归约串。由此可见，在“移进—归约”过程中，选择哪一个符号串进行归约是至关重要的。对于这个可归约串，在不同的语法分析过程中有不同的称呼，在简单优先分析中称为“句柄”，在算符优先分析中称为“素短语”。5.1.2移进—归约方法一个移进—归约分析器设置一个符号栈和一个输入缓冲区。当输入符号串为，分析开始时，栈和输入缓冲区的格式为：符号栈的栈底为#，输入符号串为#，其中#作为输入串的结束符。对进行分析时，将的符号从左

5、到右逐个移进符号栈，一旦栈顶符号串与某一个产生式右部相匹配成为一个可归约串时，则将此符号串归约为一个非终结符，这个非终结符是该产生式的左部符号，当栈顶又形成一个可归约串时，则又可将此符号串归约为某个产生式左部非终结符，的符号继续逐个移进符号栈。重复这个过程，将出现如下格式：符号栈的栈底为#Z，输入符号串为#。例5.2设文法为ZABAaAb

6、abBbB

7、c对于输入符号串aabbcc的分析过程如表5-2所示的移进归约过程，移进—归约过程用算法实现的流程图见图5-2所示。：步骤符号栈输入符号栈操作1#aabbc#2#aabbbc#移进3#aabbbc#移进4#aabbb

8、c#移进5#aAbbc#归约6#aAbbc#移进7#Abc#归约8#Abc#移进9#Abc#移进10#AbB#归约11#AB#归约12#Z#归约顺序扫描输入符号并依次移进栈栈顶部的符号串是否构成一句柄？YN进行一次归约输入串扫描完否？noY栈中仅有开始符号？noerror输入串合法，报告分析报告出口图5-2移进-归约过程5.2简单优先分析技术自底向上优先分析分为简单优先分析法和算符优先分析法两大类。简单优先分析法的基本思想是对一个文法按一定的规则求出该文法所有的符号包括终结符和非终结符之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。而算符优

9、先分析的基本思想则是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系，由于算符优先分析不考虑非终结符之间优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符名，因而算符优先归约不是规范归约。说明>代表优先级高于<代表优先级低于=代表优先级低于简单优先分析准确、规范，但分析效率较低，实际价值不大，而算符优先分析则相反，它不是规范归约，但分析速度快，适应于表达式的分析。下面我们重点讲述简单算符优先分析技术，在下一节介绍算符优先分析法。简单优先分析法是按照文法符号的优先关系确定句柄，包括任意两个文法符号之间的优先关系、如何构造优先关系表，如何进行语

10、法判断和编写语法分析程序。5.2.1优先关系在讲述算符优先分析之前，先介绍一种关系，称之为优先关系。设X和Y为文法G中的符号，可以是终结符或非终结符。在简单优先分析方法中，可以定义三种简单优先关系。（1）优先性等于X＝Y表示X和Y的优先关系相等。满足优先关系等于的定义为：当且仅当G存在产生式规则即AXY。（2）优先性低于X+Y。（3）优先性高于X>Y表示X的优先性比Y的优先性高。当且仅当在G中存在产生式规则即ABD，且B=>+