懂视

要证明一个文法是SLR(1)文法,但不是LL(1)文法,是不是要分SLR和LL来分析说明呢?

2024-10-25 05:52:46

是。

一、例如:证明下列文法是LL(1)文法但不是SLR(1)文法

S->AaAb|BbBaA->ᵋ(空值)B->ᵋ(空值)

1、首先该文法无左递归存在,没有公共左因子。

其次:对于S→AaAb|BbBaFIRST(AaAb)={a}FIRST(BbBa)={b}

FIRST(AaAb)∩FIRST(BbBa)=Φ

所以该文法是LL(1)文法.

2、证明该文法不是SLR的。

文法的LR(0)项目集规范族为:

I0={S’→.SS→.AaAbS→.BbBaA→.B→.}

I1={S’→S.}

I2={S→A.aAb}

I3={S→B.bBa}

I4={S→Aa.AbA→.}

I5={S→Bb.BaB→.}

I6={S→AaA.b}

I7={S→BbB.a}

I8={S→AaAb.}

I9={S→BbBa.}

考察I0:

FOLLOW(A)={a,b}FOLLOW(B)={a,b}FOLLOW(A)∩FOLLOW(B)={a,b}

产生规约-规约冲突,所以该文法不是SLR(1)文法。

二、构造LR(1)自动机(没有需要合并的状态):

没有状态存在冲突,因而是LALR(1)文法。

构造LR(0)自动机:在状态I6,由于’a’∈FOLLOW(A),因而对于SLR(1)分析而言,存在移进-归约,所以这一文法不是SLR(1)文法。

扩展资料:

它通过两种方法做到这一点。首先,它在一个移进之前先考虑输入记号以确保存在着一个恰当的DFA。其次,使用构造的非终结符的Follow集合来决定是否应执行一个归约。令人吃惊的是,先行的这个简单应用的能力强大得足以分析几乎所有的一般的语言构造。

定义:SLR(1)分析算法(SLR(1)parsingalgorithm)。令s为当前状态(位于分析栈的顶部)。则动作可定义如下:

若状态s包含了格式A→a.Xb的任意项目,其中X是一个终结符,且X是输入串中的下一个记号,则动作将当前的输入记号移进到栈中,且被压入到栈中的新状态是包含了项目A→aX.b的状态。

参考资料来源:百度百科-SLR(1)分析