简单优先分析法

    前几天上了关于简单优先分析法的一节课,当时心情暴躁,什么也听不进去,听完就更暴躁了。刚刚又上了一遍课,觉得老师讲得通俗易懂,决定分享一下。

    首先我们应该知道一些基本的表示方式

因为符号不易打出,我暂且用=,>,<符号代替他们的优先关系。虽然这三个符号和我们的算数符号类似,只是多了一个点,但是他们还是有写区别的。比如如果有a<b(这里是算术符号),那么b>a,但是如果a的优先性大于b,b的优先性不一定小于a。话不多说,切入正题吧。

判断符号的优先关系的三个标准如下:

 

 如果有这么一条表达式A->...XY...,那么我们可以判断X的优先性等于Y。

  

 

如果有表达式A->...XB,B经过n(n>=1)次推导可以变成以字符Y开头的字符串,那么可以判断X的优先性小于Y。

 

如果有表达式A->...BD...,B经过n(n>=1)次推导可以变成以X结尾的字符串,D经过m(m>=0)次推导可以变成以Y开头的字符串,那么我们可以确定X的优先性大于Y。

知道了上面三个判断方法,我们来看一下下面这个简单的例子。

         

=关系:很显然,bA是连在一起的,按照上面的判断方法,我们可以知道b=A,往后判断还有,A=b(=BA=aa=)

<关系:按照上面第二条判断法则,找到形如A->...XB...的表达式,其中B需经过至少一次推导得到以Y开头的字符串,才能得出X<Y的结论。S->bAb,很显然S->...bA...,A经过至少一次推导可以得到以   (,a  开头的字符串,所以有b<(b<a。虽然S->...Ab...,但是这里的b并不能经过至少一次推导来得出别的字符串,所以不存在<关系。我们还可以得到   (<A(<((<a   (B经过一次推导得到A开头的字符串,经过两次推导得到(和a开头的字符串)。

>关系:看第一条式子S->bAb,也就是说S->...Ab...,A至少经过一次推导可以得到  B,a,)结尾的字符串,所以有B>ba>b)>b ,继续判断还有B>aa>a)>a

       

    

我们用一个矩阵来表示它们的优先关系

 

其中我们规定  :

① # = #  。

②S经过n(n>=0)次推导可以得到以X开头的字符串,那么我们规定   # < X。(S可以推导出S,b开头的字符串,所以#<S,#<b)

③S经过n(n>=0)次推导可以得到以X结尾的字符串,那么我们规定   X > #。

怎样用简单优先分析法来分析语句呢

现在给定一条语句#b(Aa)b#,两个#分别表示这条语句的开始和结束符号。

①#入栈

②#<b,b入栈

③b<(,(入栈

④(<A,A入栈

⑤A=a,a入栈

⑥a=),)入栈

⑦)>b,开始出栈,直到遇到第一个<为止,即),a,A出栈

⑧寻找可以推出Aa)的左部,即B,(=B,B入栈

⑨B>b,此时B,(出栈,

⑩ 寻找可以推出(B的左部,即A,b=A,A入栈

11A=b,b入栈

12 b>#,b,A,b出栈

13 找到可以推出bAb的左部,即S

14  #<S,S入栈,此时已经找到句子的句尾,且栈中除了#,只有一个开始符号S,分析结束。

我们什么时候才可以用简单优先分析法来分析一条语句呢。答案是:这个文法必须是简单分析文法。

  

(1)很好理解,如果两个符号有大于 1种的优先关系,那么在分析时会出错。

(2)如果有两个产生式的右部相同,那么在寻找左部时,会出错。

      

        

 

         

原文地址:https://www.cnblogs.com/xianxianxian/p/12858556.html