计算机编译原理第04(4)章

《计算机编译原理第04(4)章》由会员分享，可在线阅读，更多相关《计算机编译原理第04(4)章（23页珍藏版）》请在装配图网上搜索。

1、Reading Fun,Sub topics go here,*,4.4.4,算符优先分析算法的设计,对于算符优先分析法，它虽然是一种自下而上的语法分析方法，但它并不是,一种规范归约,的分析方法。,4.4.4,算符优先分析算法的设计,这是因为在算符优先文法中，仅在终结符号之间定义优先关系而未对非终结符定义优先关系，从而无法使用优先关系表去识别由单个非终结符组成的可归约串，这也就是说，算符优先分析法不是用,句柄,来刻画可归约串，而是用,最左素短语,来刻画可归约串的。,4.4.4,算符优先分析算法的设计,1.,最左素短语,所谓句型的,素短语,是指这样一种短语，它至少包含一个终结符，并且除自身之外，

2、不再包含其它的素短语。句型最左边的素短语称,最左素短语,。,4.4.4,算符优先分析算法的设计,例如，有文法,G E,E,E+T|T,T T,*,F|F,F (E)|id,求该文法句型,T+T*F+id,的素短语和最左素短语。,首先给出句型,T+T,*,F+id,的语法树,见,下图,:,4.4.4,算符优先分析算法的设计,其短语有：,T+T,*,F+id,T+T,*,F,T,T,*,F,id,由素短语定义可知,T,*,F,和,id,是素短语。,T,*,F,为最左素短语。,注意,：,T,是该句型的句柄，而不是素短语。,E,E,+,T,E +T F,T T *F id,4.4.4,算符优先分析算法

3、的设计,2,.,识别句型最左素短语的方法,由算符文法的定义可知，算符优先文法的任何句型都没有相邻的两个非终结符。,其句型总可以表示成：,$N,1,a,1,N,2,a,2,N,n,a,n,N,n+1,$,其中每个,N,i,为非终结符或空,a,i,为终结符,（,1in,）,4.4.4,算符优先分析算法的设计,对算符优先文法,G,有如下定理：,一个算符优先文法,G,的任何句型的最左素短语是满足下列条件的最左子串,:,N,i,a,i,N,i+1,a,i+1,a,j,N,j+1,a,i-1,a,i,.,6.3.3,算符优先分析算法的设计,需要指出的是出现在,a,i,左端的非终结符,N,i,和,a,j,右

4、端的非终结符,N,j+1,是属于素短语的。,这是由于算符文法的任何句型中终结符和非终结符相邻时含终结符的短语必含相邻非终结符。,4.4.4,算符优先分析算法的设计,对上述句型,$T+T,*,F+id$,写成算符优先分析形式为：,a,i,a,i+1,a,j-1,a,j,=,.,=,.,a,j,a,j+1,.,a,i-1,a,i,.,$N,1,a,1,N,2,a,2,N,3,a,3,a,4,$,因有,$+,*,+$,.,.,.,故由最左素短语定理有,N,2,a,2,N,3,即,T,*,F,是,最左素短语。,4.4.4,算符优先分析算法的设计,根据最左素短语的定理,，最左素短语中的终结符号具有相同的

5、优先关系，并且，由于最左素短语中的符号是当时最先要归约的串，其优先关系先于最左素短语之外的符号，所以,我们使用一个用于存放文法符号的先进后出栈，并利用优先关系表，可以确定最左素短语是否已形成来决定分析器的动作,。,3.,算符优先分析程序的设计,4.4.4,算符优先分析算法的设计,基本思想,:,$,t,1,t,3,t,j+1,t,2,t,j,t,i+1,t,n,$,符号栈,优先关系,t,i,尾,头,最左素短语,3.,算符优先分析程序的设计,.,=,.,.,.,.,a,j,a,j+1,a,i,a,i,a,j-1,a,j,=,.,=,.,返回图,4.4.4,算符优先分析算法的设计,下面给出算符优先分

6、析算法,。,输入：输入符号串,W,和优先关系表。,输出：若,W,是正确的句子，则接收，,否则输出错误信息。,方法：执行下图算法。,栈置初值,K,1,SK,$,当前输入符号读入,a,SK,是终结符？,j,K,Y,j,K1,N,S j,是终结符？,Q,S j ,j,j-1,Y,S j+1SK,是最左素短语,K,j+1,SK,N,Y.,K=2,且,a=$?,结束,Y,N,SK,a,K,K+1,Y,error,N,j,j-1,N,S j a?,.,S j,a?,或,S j,a?,N,.,=,.,Y,S j Q?,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.

7、,.,=,.,.,.,.,.,归约,id,$,移进,$,.,归约,$,.,$,=,.,结束,$,id,+id$,移进,.,.,$N,+,id$,移进,.,归约,4.4.6,算符优先分析法的局限性,由于算符优先分析法跳过了所有单非产生式之间的归约，这样算符优先分析比规范归约要快得多，这既是优点也是缺点。,由于忽略非终结符在归约过程中的作用，可能导致把本来不是句子的输入串误认为是文法句子。,4.4.6,算符优先分析法的局限性,设有算符优先文法,A A;D|D,D D(E)|F,F a|(A),E E+A|A,6.3.6,算符优先分析法的局限性,该文法对应的算符优先关系表如下表所示。,；,a,+,(

8、,),$,;,a,+,(,),$,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,=,.,=,.,4.4.6,算符优先分析法的局限性,对输入串,(a,a),进行算符优先分析,其结果能正确地进行归约。,但是，从该文法推导不出,(a,a),。,即输入串,(a,a),不是文法句子。,当然，算符优先分析的这种局限性可以从技术上加以弥补。,Transitional Page,Backdrops:,-These are full sized backdrops,just scale them up!,-Can be Copy-Pasted out of Templates for use anywhere!,,