Homework 4

$3.1$文法：
S → ( L ) ∣ a L → L , S ∣ S F o l l o w ( S ) = { ， , ) , $ } F o l l o w ( L ) = { ， , ) } S→(L)|a\\ L→L,S|S\\ Follow(S)=\{，,),\$\}\\Follow(L)=\{，,)\} S→(L)∣aL→L,S∣SFollow(S)={，,),$}Follow(L)={，,)}

1

$(1)$习题$3.8$，其中$(b)$给出递归下降语法分析程序。

$3.8:$
$(a)$消除习题$3.1$文法的左递归
消除左递归得到
$$\begin{gathered} S\to (L)|a \\ L\to S{L}^{\prime } \\ {L}^{\prime }\to ,S{L}^{\prime }|ϵ \end{gathered}$$
$(b)$为$(a)$的文法构造预测分析器

F i r s t ( S ) = { ( , a } F i r s t ( L ) = F i r s t ( S ) = { ( , a } F i r s t ( L ′ ) = { ， , ϵ } F o l l o w ( L ) = { ) } F o l l o w ( L ′ ) = F o l l o w ( L ) + { $ } = { ) , $ } F o l l o w ( S ) = F i r s t ( L ′ ) − { ϵ } + F o l l o w ( L ) + F o l l o w ( L ′ ) + { $ } = { ， , ) , $ } \begin{aligned} First(S)&=\{(,a\}\\ First(L)&=First(S)=\{(,a\}\\ First(L')&=\{，,\epsilon\}\\ Follow(L)&=\{)\}\\ Follow(L')&=Follow(L)+\{\$\}=\{),\$\}\\ Follow(S)&=First(L')-\{\epsilon\}+Follow(L)+Follow(L')+\{\$\}=\{，,),\$\}\\ \end{aligned} First(S)First(L)First(L′)Follow(L)Follow(L′)Follow(S)​={(,a}=First(S)={(,a}={，,ϵ}={)}=Follow(L)+{$}={),$}=First(L′)−{ϵ}+Follow(L)+Follow(L′)+{$}={，,),$}​

	$($	$)$	$,$	$a$	$＄$
$S$	$S\to (L)$			$S\to a$
$L$	$L\to S{L}^{\prime }$			$L\to S{L}^{\prime }$
$L^{\prime }$		$L^{\prime }\to ϵ$	$L^{\prime }\to ,S{L}^{\prime }$		$L^{\prime }\to ϵ$

递归下降程序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 1e3;
char str[N];
int ind = 0;
void S();// S->(L)|a;
void L();// L->SX
void X();// X-> ,SX|ε
int main() {
    int len;
    int m;
        printf("请输入要分析的串：");
        scanf("%s", str);
        len = strlen(str);
        str[len] = '#';
        str[len + 1] = '\0';
        S();
        if (str[ind] == '#')
            printf("正确语句！\n");
        else {
            printf("分析失败!\n");
        }
    return 0;
}
void L() {// L->SX
        S();
        X();
}
void X() {// X-> ,SX|ε
    if (str[ind] == ',') {
        ind++;
        S();
        X();
    }
}
void S() {// S->(L)|a;
    if (str[ind] == 'a') {
        ind++;
    } else if (str[ind] == '(') {
        ind++;
        L();
        if (str[ind] == ')') {
            ind++;
        } else {
            printf("分析失败!\n");
            exit(0);
        }
    } else {
        printf("分析失败!\n");
        exit(0);
    }
}

2

$(2)$习题$3.11$，并描述该文法产生的语言。
$3.11$:
构造下面文法的$LL(1)$分析表
S → a B S ∣ b A S ∣ ϵ A → b A A ∣ a B → a B B ∣ b     F i r s t ( S ) = { a , b , ϵ } F i r s t ( A ) = { a , b } F i r s t ( B ) = { a , b } F o l l o w ( S ) = { $ } F o l l o w ( A ) = { a , b , $ } F o l l o w ( B ) = { a , b , $ } S→aBS|bAS|\epsilon\\ A→bAA|a\\ B→aBB|b\\ \ \\ \ \\ \begin{aligned} First(S)&=\{a,b,\epsilon\}\\ First(A)&=\{a,b\}\\ First(B)&=\{a,b\}\\ Follow(S)&=\{\$\}\\ Follow(A)&=\{a,b,\$\}\\ Follow(B)&=\{a,b,\$\}\\ \end{aligned} S→aBS∣bAS∣ϵA→bAA∣aB→aBB∣b  First(S)First(A)First(B)Follow(S)Follow(A)Follow(B)​={a,b,ϵ}={a,b}={a,b}={$}={a,b,$}={a,b,$}​

	$a$	$b$	$＄$
$S$	$S\to aBS$	$S\to bAS$	$S\to ϵ$
$A$	$A\to a$	$A\to bAA$
$B$	$B\to aBB$	$B\to b$

该文法产生一个空串或者$a,b$数量相等的$ab$串。

3

$(3)$为习题$3.1$文法构造$SLR(1)$分析表。
拓广文法
$$\begin{array}{rl}& S^{\prime }\to S\\ & S\to (L)\\ & S\to a\\ & L\to L,S\\ & L\to S\end{array}$$

该文法的$LR(0)$项目集规范族：
$$\begin{gathered} \begin{array}{rl}{I}_0:& \\ & S^{\prime }\to \cdot S\\ & S\to \cdot (L)\\ & S\to \cdot a\\ & \\ & \end{array}\begin{array}{rl}{I}_1:& \\ & S^{\prime }\to S\cdot \\ & \\ & \\ & \\ & \end{array}\begin{array}{rl}{I}_2:& \\ & S\to (\cdot L)\\ & L\to \cdot L,S\\ & L\to \cdot S\\ & S\to \cdot (L)\\ & S\to \cdot a\end{array} \\ \begin{array}{rl}{I}_3:& \\ & S\to a\cdot \\ & \\ & \end{array}\begin{array}{rl}{I}_4:& \\ & S\to (L\cdot )\\ & L\to L\cdot ,S\\ & \end{array}\begin{array}{rl}{I}_5:& \\ & L\to S\cdot \\ & \\ & \end{array} \\ \begin{array}{rl}{I}_6:& \\ & S\to (L)\cdot \\ & \\ & \end{array}\begin{array}{rl}{I}_7:& \\ & L\to L,\cdot S\\ & S\to \cdot (L)\\ & S\to \cdot a\end{array}\begin{array}{rl}{I}_8:& \\ & L\to L,S\cdot \\ & \\ & \end{array} \\ \begin{array}{r}\end{array} \end{gathered}$$

$SLR(1)$分析表：

	$($	$)$	$a$	$,$	$＄$	$S$	$L$
$0$	$s2$			$s3$		$1$
$1$	$s2$			$s3$	$acc$
$2$						$1$	$4$
$3$		$r3$		$r3$	$r3$
$4$	$s5$			$s6$
$5$		$r5$		$r5$
$6$		$r2$		$r2$	$r2$
$7$	$s2$		$s3$			$7$
$8$		$r4$		$r4$

4

$(4)$习题$3.21、3.22、3.25$。
$3.21$:
$(a)$证明下面文法是$LL(1)$文法，但不是$SLR(1)$文法。
$$\begin{gathered} S\to AaAb|BbBa \\ A\to ϵ \\ B\to ϵ \end{gathered}$$
根据$LL(1)$文法定义， F i r s t ( A a A a ) = { a } , F i r s t ( B b B b ) = { b } First(AaAa)=\{a\},First(BbBb)=\{b\} First(AaAa)={a},First(BbBb)={b}
$First(AaAa)\cap First(BbBb)=\varphi$，所以该文法是$LL(1)$文法。
根据$SLR(1)$分析，存在如下状态
$$\begin{array}{rl}I:& \\ & S\to \cdot AaAb\\ & S\to \cdot BbBa\\ & A\to ϵ\cdot \\ & B\to ϵ\cdot \end{array}$$
此时，由于 F o l l o w ( A ) = F o l l o w ( B ) = { a , b } Follow(A)=Follow(B)=\{a,b\} Follow(A)=Follow(B)={a,b}，所以若输入符号为$aorb$则无法判断是将$ϵ$归约成 $A$还是$B$，出现归约-归约冲突，所以不是$SLR(1)$文法。

$3.22$:
证明下面文法是$LALR(1)$文法，但不是$SLR(1)$文法。
$$\begin{gathered} S\to Aa|bAc|dc|bda \\ A\to d \end{gathered}$$
该文法存在一个状态，$[S\to d\cdot c],[A\to d\cdot ]$出现在同一个项目集中，因为 F o l l o w ( A ) = { a , c } Follow(A)=\{a,c\} Follow(A)={a,c}，所以当 输入符号为$c$时，无法判断进行$[S\to d\cdot c]$移进还是$[A\to d\cdot ]$规约,出现移进-归约冲突，所以不是$SLR(1)$文法。

除上述冲突，同理还存在一个$[S\to bd\cdot a],[A\to d\cdot ]$的移进-归约冲突，但这两个冲突，在规范$LR(1)$情况下不存在，因为只有输入符号为$a$时，才进行$d$到$A$的归约操作，所以此文法是$LR(1)$文法，且此文法的规范$LR(1)$项目集中任意项目的搜索符只能为$＄ora$，所以不存在同心的$LR(1)$项目集，所以此文法也是$LALR(1)$文法。

$3.25$:
一个非$LR(1)$的文法如下：
$$\begin{gathered} L\to MLb|a \\ M\to ϵ \end{gathered}$$
请给出所有含移进-归约冲突的规范$LR(1)$项目集，以说明该文法确实不是$LR(1)$的。
以下项目集存在移进-归约冲突，即输入符号为$a$时，无法判断进行移进$a$还是进行$ϵ$规约，所以该文法不是$LR(1)$的。
$$\begin{array}{rl}{I}_0:& \stackrel{M}{⟶}\\ & L^{\prime }\to \cdot L,\$\\ & L\to \cdot MLb,\$\\ & L\to \cdot a,\$\\ & M\to \cdot ,a\end{array}\begin{array}{rl}{I}_2:& \stackrel{M}{⟶}\\ & L\to M\cdot Lb,\$\\ & L\to \cdot MLb,b\\ & L\to \cdot a,b\\ & M\to \cdot ,a\end{array}\begin{array}{rl}{I}_5:& \\ & L\to M\cdot Lb,b\\ & L\to \cdot MLb,b\\ & L\to \cdot a,b,b\\ & M\to \cdot ,a\end{array}$$

5

$(5)$为以下文法构造$LR(1)$分析表：
$$\begin{array}{rl}& S\to aS\\ & S\to A\\ & A\to aAb\\ & A\to \end{array}$$
拓广文法
$$\begin{array}{rl}& S^{\prime }\to S\\ & S\to aS\\ & S\to A\\ & A\to aAb\\ & A\to ϵ\end{array}$$
该文法的$LR(1)$项目集规范族为

$$\begin{gathered} \begin{array}{rl}{I}_0:& \\ & S^{\prime }\to \cdot S,\$\\ & S\to \cdot aS,\$\\ & S\to \cdot A,\$\\ & A\to \cdot aAb,b\\ & A\to \cdot ϵ,b\\ & \end{array}\begin{array}{rl}{I}_1:& \\ & S^{\prime }\to S\cdot ,\$\\ & \\ & \\ & \\ & \\ & \end{array}\begin{array}{rl}{I}_2:& \\ & S\to a\cdot S,\$\\ & S\to \cdot aS,\$\\ & S\to \cdot A,\$\\ & A\to \cdot aAb,b/\$\\ & A\to \cdot ϵ,b/\$\\ & A\to a\cdot Ab,b\end{array} \\ \begin{array}{rl}{I}_3:& \\ & S\to A\cdot ,\$\\ & \end{array}\begin{array}{rl}{I}_4:& \\ & S\to aS\cdot ,\$\\ & \end{array}\begin{array}{rl}{I}_5:& \\ & A\to aA\cdot b,b\\ & \end{array} \\ \begin{array}{rl}{I}_6:& \\ & A\to aAb\cdot ,b\end{array} \end{gathered}$$
$LR(1)$分析表为：

	$a$	$b$	$＄$	$S$	$A$
$0$	$s2$	$r5$		$1$	$3$
$1$			$acc$
$2$	$s2$	$r5$	$r5$	$1$	$3$
$3$			$r3$
$4$		$r2$
$5$		$s6$
$6$			$r4$