简单优先文法的定义 对于上述情况,规定 情况1:s>t;情况2:s=t;情况3:s<t 4.s和均不在句柄中,由于s和t在a中相邻出现,则一定 存在另一句型,使得s和t合上述三种情况之 注意这种优先关系是不对称的 对于在任何句型中都不相邻出现的符号对规定两个 符号之间无关系 定义4.1若一文法G的任何两个符号之间至多存在一 种优先关系,且任意两个不同的产生式无相同的右部, 则称G为简单优先文法
6 简单优先文法的定义 对于上述情况，规定 情况1: s>t; 情况2: s=t; 情况3: s<t 4. s和t均不在句柄中,由于s和t在中相邻出现，则一定 存在另一句型，使得s和t符合上述三种情况之一. • 注意,这种优先关系是不对称的! • 对于在任何句型中都不相邻出现的符号对,规定两个 符号之间无关系. 定义4.1 若一文法G的任何两个符号之间至多存在一 种优先关系,且任意两个不同的产生式无相同的右部, 则称G为简单优先文法
简卓优先文举例 例44考虑文法G[E]:E→E1,E1E1T1T1T1→>T; T→T*FF;F→>(E) 由文法的产生式可直接看出: E1=+,+=T1,T=*,*=F,(=E,E=) 考查句型E+及T(E1T)的最右推导 ●E=>E>E1T>E1+工=>ET=>E1T=>E+E ●=>E+(逆序为最左归约,划线部分为句柄) E=>E1>工=>牌多>T*>T(E)=>T*(E1T 不难看出,+,+F,+以及:气(<E1 E),T1)
7 简单优先文法举例 例4.4 考虑文法G’[E]: E→E1；E1→E1+T1 |T1；T1→T； T→T*F | F；F→(E) | i 由文法的产生式可直接看出: E1 = +, +=T1，T = *，* = F，(=E，E=) 考查句型 E1+i*i 及 T*(E1+T1 )的最右推导： E=>E1=>E1+T1=>E1+T =>E1+T*F =>E1+T*i =>E1+F*i =>E1+i*i （逆序为最左归约，划线部分为句柄） E=> E1=> T1=> T =>T*F => T*(E) =>T*(E1 ) =>T*(E1+T1 ) 不难看出, +<i, i>*, +<F, F>*, *<i, +<T,以及: *<(, (<E1 , E1>), T1>)
文法GE]的简单优先矩阵 可把文法的全部优先关系用一矩阵来表示例如前面 所给文法GE相应的优先矩阵为 E「E1T1「TF EE TTF+
8 E E1 T1 T F + * ( ) i E = E1 = > T1 > > T > = > F > > > + = < < < < * = < < ( = < < < < < < ) > > > i > > > 文法G’[E]的简单优先矩阵 可把文法的全部优先关系用一矩阵来表示.例如前面 所给文法G’[E]相应的优先矩阵为:
二、简单优先分析的算法 有了优先关系矩阵,就能很容易得找到一个规范句型 的句柄:依次查看当前句型X1X2…Xm相邻两个符号的 优先关系,一旦出现X+k>x1++1,x+即为句柄的尾符号, 然后从X*开始向左反向查看已扫描过的符号,直到发 现x11<X1即为句柄的头符号 可以证明,X到X之间的符号串Xx*1…,X恰好构 成了当前句型的句柄 特别地,对于任意符号X,有#<X,并且X>#
9 二、简单优先分析的算法 有了优先关系矩阵，就能很容易得找到一个规范句型 的句柄：依次查看当前句型X1X2…Xm相邻两个符号的 优先关系,一旦出现Xi+k>Xi+k+1, Xi+k即为句柄的尾符号, 然后从Xi+k开始向左反向查看已扫描过的符号,直到发 现Xi-1<Xi ,Xi即为句柄的头符号. 可以证明, Xi到Xi+k 之间的符号串Xi Xi+1…Xi+k恰好构 成了当前句型的句柄. 特别地，对于任意符号Xi，有#<Xi，并且Xi>#
程序4-4简单优先分彻驱动程序 int parser(void) if(LeftSide /Leftside!=0 int i=0, k=0, r; stack 0=# means the production exists * r=a k++l; j;stacki=Leftside dot int j, Leftside; Else There is no production while(!IsHigher Than(stackil, r)) which matches the right side *7 Rstack++ir; r=a[k++; if(i==2 &&r==#&& stacki STARTSYSBOL) return SUCcesS: while( Is lowerThan(stacklj 1, stackljD)j-i else return ERROR; Leftside= 3 while(1); RightsideofA Production 3/*end of parser * (stackljl, stack i, i-j+1);
10 程序4-4 简单优先分析驱动程序 int parser(void){ int i=0,k=0,r;stack[0]='#'; r=a[k++]; do{ int j,LeftSide; while(!IsHigherThan(stack[i],r)) {stack[++i]=r;r=a[k++];} j=i; while(!IsLowerThan (stack[j- 1], stack[j])) j--; LeftSide= RightSideOfAProduction (stack[j],stack[i],i-j+1); if(LeftSide){ /*LeftSide!=0 means the production exists */ i=j;stack[i]=LeftSide; }else /* There is no production which matches the right side */ if(i==2 && r=='#' && stack[i] == STARTSYSBOL) return SUCCESS; else return ERROR; } while (1); } /* end of parser */