一、对于文法G(S):

S → bMb

M → (L|a

L → Ma)

1. 写出句型b(Ma)b的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语和句柄。

 

二、设有文法 G[S] 为：

S → a|b|(A)

A → SdA|S

(1)完成算符优先关系表. 并判断 G[S] 是否为算符优先文法。

(2 ）给出句型（ SdSdS) 的短语、直接短语、句柄、素短语和最左素短语。

（ 3) 给出输入串 (adb)# 的分析过程。

 

三、文法 G[P] ： P → aPb|Q

Q → bQc|bSc

S → Sa|a

请构造它的 SLR （1）分析表，并说明它是不是 SLR （1）文法。

 

一.解答：

1. (4分)

 S=>bMb=>b(Lb=>b(Ma)b

2. (4分)

短语:  Ma)，  (Ma)， b(Ma)b

直接短语:  Ma)

句柄:  Ma)

 

二【解答】

I）先求文法G[S]的FIRSTVT集和LASTVT集：

    由s→a|b|(A)得：FIRSTVT(S)={a,b,(）；

    由A→Sd…得：FIRSTVT(A)={d}；又由A→S…得：FIRSTVT(S) c FIRSTVT(A),即FIRSTVT(A)={d,a,b,（｝；

    由S→a|b|(A)得：LASTVT(S)＝｛a，b，)｝；

    由A→…dA得：LASTVT(A)={d},又由A→S得：LASTVT(S) c LASTVT(A),即

LASTVT(A)={d,a,b,)｝。

    构造优先关系表方法如下：

    ①对P→…ab…，或P→…aQb…，有a=b；

    ②对P→…aR…，而b∈FIRSTVT(R)，有a< P>

    ③对P→…Rb…，而a∈LASTVT (R)，有a>b。

    由此得到：

    ①由S→(A)得：（=）；

    ②由S→(A…得：（< P>

    由A→…dA得：d<（；< P>

    ③由S→…A)得：LASTVT(A)＞），即：d>),a>),b＞），）＞）；

    由A→Sd…得：LASTVT(S）＞d，即：a>d,b＞d,）＞d；

    此外，由#S#得：＃=＃；

    由＃< P>

    由LASTVT(S）＞＃得：d>＃，a>#,b>＃，）＞＃。

最后得到算符优先关系表，见表3.7。

由表3.7可以看出，任何两个终结符之间至多只满足=、＜、＞三种优先关系之一，故G[S]为算符优先文法。

(2)为求出句型(SdSdS)的短语、直接短语、句柄，我们先画出该句型对应的语法树，

如图3.11所示。  

 

由图3.11得到：

        短语：S，SdS，SdSdS,(SdSdS)

        直接短语：S

        句柄（即最左直接短语）：S

    可以通过分析图3.11的语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符（中间可有一个非终结符）之间的优先关系。确定优先关系的原则是：

    ①同层的优先关系为=；

    ②不同层时，层次离树根远者优先级高，层次离树根近者优先级低（恰好验证了优先关系表的构造算法）；

    ③在句型ω两侧加上语句括号“＃”,即＃ω＃，则有＃＜ω和ω＞＃，由此我们得到句型的优先关系如图3.12所示。 

而最左素短语就是该句型中所找到的最左边的那个素短语，即最左素短语必须具备3个

条件。

    ①至少包含一个终结符（是否包含非终结符则按短语的要求确定）。

    ②除自身外不得包含其他素短语（最小性）。

    ③在句型中具有最左性。

因此，由图3.12得到的SdS为句型（SdSdS）的素短语，它同时也是该句型的最左素短语。

(３)输入串(adb)＃的分析过程见表3.8

为便于分析，同时给出了(adb)#的语法树，如图3.13所示。

三【解答】

将文法G[P]拓广为G[P`]：

G[P`]的DFA如图4.23所示

G[P`]的FOLLOW集如下图所示

最后得到SLR（1）分析表，见表4.20

由于SLR（1）分析表中不存在冲突，故文法G[P`]是SLR（1）文法。