5、已知语言写出相应的文法：（10分） (1) 已知语言L={WaWr | W 属于(0 | a)*，Wr表示W的逆}，试构造相应的上下文无关文法。 (2) 已知语言L={1n0m1m0n | m>0, n>=0}，试构造相应的上下文无关文法。 (3) 已知语言L={ anbnambm | m>=0, n>0}，试构造相应的上下文无关文法。

(1) 文法的产生式如下：

S → aSa | bSb | ε

其中，S为起始符号，ε表示空串。

(2) 文法的产生式如下：

S → 1S0 | A
A → 1A0 | B
B → ε | 1B0

其中，S为起始符号，ε表示空串。

(3) 文法的产生式如下：

S → aSb | C
C → aC | bC | D
D → bD | ε

其中，S为起始符号，ε表示空串。

相关问题

编译原理：已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法

要判断该文法是否是SLR(1)文法，需要进行以下步骤：

1. 构造该文法的LR(0)自动机，并求出LR(0)项集族和对应的转移表。

2. 对每个LR(0)项集，求出它的闭包和GOTO集合。

3. 对于每个非终结符A和每个终结符a，求出它们的FOLLOW集。

4. 对于每个LR(0)项集I和每个终结符a，求出ACTION[I, a]和GOTO[I, A]的值。

5. 判断文法是否是SLR(1)文法。对于每个LR(0)项集I和每个终结符a，如果ACTION[I, a]和GOTO[I, A]同时存在冲突，且冲突中至少有一项是移进-归约冲突，那么该文法就不是SLR(1)文法。

下面是具体的步骤：

1. 构造LR(0)自动机：

起始状态：[S' -> .A] （S'是起始符号）
状态1：[A -> .fAa, A -> .fAg]
状态2：[A -> f.Aa, A -> f.Ag]
状态3：[A -> fA.a, A -> fAg.]
状态4：[A -> fAg.]
状态5：[A -> fA.a]
状态6：[A -> f.Ag]
状态7：[A -> b.]

2. 对每个LR(0)项集，求出它的闭包和GOTO集合：

闭包({[S' -> .A]}) = {[S' -> .A], [A -> .fAa, A -> .fAg]}
GOTO({[S' -> .A]}, f) = {[A -> f.Aa, A -> f.Ag]}
GOTO({[S' -> .A], [A -> .fAa, A -> .fAg]}, a) = {[A -> fA.a]}
GOTO({[S' -> .A], [A -> .fAa, A -> .fAg]}, g) = {[A -> fAg.]}
GOTO({[A -> f.Aa, A -> f.Ag]}, a) = {[A -> fA.a]}
GOTO({[A -> f.Aa, A -> f.Ag]}, g) = {[A -> fAg.]}
GOTO({[A -> fA.a]}, a) = {}
GOTO({[A -> fAg.]}, a) = {}
GOTO({[A -> fA.a]}, g) = {[A -> f.Ag]}
GOTO({[A -> f.Ag]}, a) = {}
GOTO({[A -> f.Ag]}, g) = {[A -> fAg.]}

3. 对于每个非终结符A和每个终结符a，求出它们的FOLLOW集：

FOLLOW(A) = {a, g}
FOLLOW(f) = {a, g}
FOLLOW(g) = {a, b}

4. 对于每个LR(0)项集I和每个终结符a，求出ACTION[I, a]和GOTO[I, A]的值：

ACTION[{[S' -> .A]}, f] = {[A -> f.Aa, A -> f.Ag]}
ACTION[{[S' -> .A], [A -> .fAa, A -> .fAg]}, a] = {[A -> fA.a]}
ACTION[{[S' -> .A], [A -> .fAa, A -> .fAg]}, g] = {[A -> fAg.]}
ACTION[{[A -> f.Aa, A -> f.Ag]}, a] = {[A -> fA.a]}
ACTION[{[A -> f.Aa, A -> f.Ag]}, g] = {[A -> fAg.]}
ACTION[{[A -> fA.a]}, a] = {[A -> fAa]}
ACTION[{[A -> fA.a]}, g] = {[A -> f.Ag]}
ACTION[{[A -> f.Ag]}, a] = {}
ACTION[{[A -> f.Ag]}, g] = {[A -> fAg.]}

GOTO集合已经在步骤2中求出。

5. 判断文法是否是SLR(1)文法：

根据步骤4中求出的ACTION和GOTO，可以看出该文法没有移进-归约冲突，但存在归约-归约冲突（ACTION[{[A -> fA.a]}, a]和ACTION[{[A -> fAg.]}, a]同时存在）。因此，该文法不是SLR(1)文法。

已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法

首先，我们需要构造该文法的 LR(0)自动机。

LR(0)自动机的状态集合如下：

| 状态 | 项目集 |
| :-----: | :----------------: |
| I0 | A→•fAa |
| | A→•fAg |
| | A→•b |
| I1 | A→f•Aa |
| | A→f•Ag |
| I2 | A→fA•a |
| I3 | A→fA•g |
| I4 | A→•fAa |
| | A→•fAg |
| | A→•b |
| | A→f•Aa |
| | A→f•Ag |
| I5 | A→fA•a |
| I6 | A→fA•g |
| I7 | A→fAa• |
| I8 | A→fAg• |

接下来，我们需要构造该文法的 SLR(1)分析表。

| 状态 | a | b | f | g | $ |
| :---------: | :-----: | :-----: | :----: | :----: | :----: |
| 0 | s2 | s3 | s4 | s5 | |
| 1 | | | r3 | r3 | r3 |
| 2 | | | r2 | r2 | r2 |
| 3 | | | r1 | r1 | r1 |
| 4 | s2 | s3 | s4 | s5 | |
| 5 | | | s6 | s7 | |
| 6 | | | r5 | r5 | r5 |
| 7 | | | r4 | r4 | r4 |
| 8 | | | r6 | r6 | r6 |

其中，s表示移入状态，r表示规约状态，数字表示将要转移到的状态。

可以发现，该文法存在移入-规约冲突和规约-规约冲突，因此该文法不是 SLR(1)文法。