由底向上语法分析.ppt

《由底向上语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/7/251第五章自底向上的语法分析2021/7/252内容5.1自底向上的分析方法简介5.2算符优先分析法5.3LR分析2021/7/253自底向上的分析方法简介自底向上的语法分析器除“接受”外，一般有两种动作：移进，将一个位于输入带上的最前面的终极符移入符号栈，符号栈中可以有符号，非终极符和一些其它的状态信息；2.归约，将栈顶的符号串α利用产生式A→α归约为非终极符自底向上的语法分析器有时也称为移进-规约分析器。2021/7/254归约（Reduction）推导的相反过程叫归约如果Su1u2…un-1un是最右推

2、导，则它的逆向过程：unun-1…u2u1S,被称为规范规约/最左归约。2021/7/255规约的例子给定文法G:SaAcBeAb

3、AbBd句子abbcde的推导为:SSacABeaAbcdeabbcdedAbb规范规约为:aAbcdeaAcdeSacABedAbbaAcBeSaAcBeaAcdeabbcdebAbdaABcSe2021/7/256自底向上的语法分析存在中的问题1如果句型存在有多个子串与一产生式右部相匹配，该选择哪一个进行规约？选择位于句型最左边的那一个子串。Why?因为分析器是从左向

4、右扫描的。Answer:2021/7/257回顾:短语与句柄w是uAv相对于A的短语，当且仅当A+w,这是一棵根为A的子树。w是uAv相对于A的直接短语，当且仅当Aw,这是一棵高度为1的子树。句柄是句型的最左直接短语。设G是一个CFG,uAv是G的一个句型即S+uAv,那么：2021/7/258句柄?是否匹配产生式右部的的最左子串一定是句柄？Answer:不,可能是，也可能不是。2021/7/259句柄的例子给定文法G:SvarL:TLid,L

5、idTreal句子varid,id:real的语法树如下：varidLL:TS

6、realid,看位于最左边的“id”它显然不是一个句柄，虽然它匹配了产生式Lid的右部。id它是句柄吗?2021/7/2510问题2:如何识别句柄？试探。当子串与某个产生式的右部匹配时，将其视为句柄，如果分析失败，则回溯。对文法做一些限制，这样可以根据规则来识别句柄，例如算符优先文法(OperatorPrecedenceGrammar，OPG）识别句柄是移进-规约分析器的主要任务，它可以用如下方法实现：2021/7/2511OPG的基本思想每一个运算符均有其优先级。当两个运算符相邻，则优先级高的先计算。表达式中所的操作数均被运算符隔

7、开。OPG的基本思想来源于算术表达式的计算。在算术表达式中：2021/7/2512运用算符优先级的例子G[E]：EE＋E

8、E－E

9、E*E

10、E/E

11、(E)

12、i这是一个二义文法，但如规定*和/的优先级比+和-的高时，只有一棵语法树。对于句子“i-i+i*(i-i)”，我们有如下的归约：2021/7/2513i-i+i*(i-i)<=E-i+i*(i-i)<=E-E+i*(i-i)<=E+i*(i-i)<=E+E*(i-i)<=E+E*(E-i)<=E+E*(E-E)<=E+E*(E)<=E+E*E<=E+E<=E*的优先级比+高运用算符

13、优先级的例子2021/7/2514算符文法与算符优先文法定义5.1若文法G的产生式右部不含两个VN符相邻的情况,则称G为算符文法.G的VT符被称为算符可以证明,算符文法不会含有两个VN符相邻的句型常见语言不一定是算符文法,但可容易地对其进行改造。例PASCAL中的循环语句:<循环语句><循环子句><语句><循环子句>for<变量>:=<循环表>do<语句>可将其改为<循环语句>for<变量>:=<循环表>do<语句><循环表><表达式>to<表达式>2021/7/2515OPG定义G中没有产生式(如：X)，也没有含连续的

14、非终极符的产生式。对于任意的终极符对(a,b)，最多只有下面的一种关系a＜b,a＝b,a＞b,它们分别表示a的优先级低于，等于，高于b的优先级。一个CFGG是OPG,当且仅当:2021/7/2516优先性的实质ab：a比b先归约2021/7/2517什么时候a=b?a=b,当且仅当a和b同时归约于是,a和b应该是在同一个句柄中相邻。PaQb……P…ab…orP…aQb...于是有:a=b当且仅当G中有产生式，形如:2021/7/2518什么时候a>b?a>b,当且仅当a先于b归约。a在位

15、于b前的R的短语中。a在短语R的最右边：.R+…aorR+…aQ于是a和b是邻居。R短语的根,应该是b的邻居或者b跟随于R。R和b在同一个产生式中,如：P…Rb…,因为在OPG中没有后继的非终极符。PRb………Wa