设文法G[S]:S→A|S-A，A→A+B|B ，B→b 。（共7分） 试给出句型B+B-b的语法树，并写出全部短语，简单(直接)短语，素短语和句柄。

以下是句型B+B-b的语法树：

      S
    /   \
   S     A
  / \   / \
 A   - A   B
 |     |   |
 A     B   b
 |         |
 B         B
 |         |
 b         b

其中，短语包括：S、S-A、A+B、A、A+B、B-b、A、B和b。

简单短语包括：A+B、A、B-b、A、B和b。

素短语包括：B、A和b。

句柄为：B。

相关问题

给出文法G(E):E→a | b | (T) T->cT' |ET' T'->+E |*E | ε 的预测分析程序

以下是文法G(E):E→a | b | (T) T->cT' | ET' T'->+E |*E | ε的预测分析程序：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 10

char stack[SIZE]; //定义栈
int top = -1; //栈顶指针初始化为-1

void push(char c) { //入栈操作
    top++;
    stack[top] = c;
}

void pop() { //出栈操作
    top--;
}

char get_top() { //获取栈顶元素
    return stack[top];
}

void error() { //错误处理函数
    printf("Error\n");
    exit(0);
}

int is_terminal(char c) { //判断是否为终结符
    if(c == 'a' || c == 'b' || c == 'c' || c == '+' || c == '*' || c == '(' || c == ')' || c == '$') {
        return 1;
    }
    return 0;
}

int get_index(char c) { //获取索引值
    if(c == 'a') {
        return 0;
    } else if(c == 'b') {
        return 1;
    } else if(c == 'c') {
        return 2;
    } else if(c == '+') {
        return 3;
    } else if(c == '*') {
        return 4;
    } else if(c == '(') {
        return 5;
    } else if(c == ')') {
        return 6;
    } else if(c == '$') {
        return 7;
    }
}

char table[6][8][3] = { //预测分析表
    { {"a", ""}, {"b", ""}, {"c", ""}, {"", ""}, {"", ""}, {"(T)", ""}, {"", ""}, {"", ""} },
    { {"", ""}, {"", ""}, {"cT'", ""}, {"", ""}, {"", ""}, {"ET'", ""}, {"", ""}, {"", ""} },
    { {"a", ""}, {"b", ""}, {"cT'", ""}, {"", ""}, {"", ""}, {"(T)", ""}, {"", ""}, {"", ""} },
    { {"", "+E"}, {"", "", ""}, {"", "", ""}, {"+E", ""}, {"*E", ""}, {"", ""}, {"", "ε"}, {"", "ε"} },
    { {"", "ε"}, {"", "ε"}, {"", "*E"}, {"+E", ""}, {"*E", ""}, {"", ""}, {"", "ε"}, {"", "ε"} },
    { {"a", ""}, {"b", ""}, {"cT'", ""}, {"", ""}, {"", ""}, {"(T)", ""}, {"", ""}, {"", ""} }
};

int main() {
    char input[SIZE];
    printf("请输入要分析的字符串：");
    scanf("%s", input);
    strcat(input, "$"); //在输入字符串末尾加上结束符"$"
    push('$');
    push('E');
    int i = 0;
    while(input[i] != '\0') { //遍历输入字符串
        if(get_top() == '$' && input[i] == '$') {
            printf("Success\n");
            break;
        } else if(get_top() == input[i]) {
            pop();
            i++;
        } else if(is_terminal(get_top())) {
            error();
        } else {
            int row = get_top() - 'E'; //获取行号
            int col = get_index(input[i]); //获取列号
            if(strcmp(table[row][col], "") == 0) {
                error();
            } else if(strcmp(table[row][col], "ε") == 0) {
                pop();
            } else {
                char* str = table[row][col];
                int len = strlen(str);
                pop();
                int j;
                for(j = len - 1; j >= 0; j--) {
                    push(str[j]);
                }
            }
        }
    }
    return 0;
}

注：在该程序中，使用了一个栈来模拟预测分析表中的栈操作，使用了一个预测分析表来判断下一步要进行的操作，其中行号和列号分别为非终结符的编号和终结符的编号。

设正规文法G[S]: S→bS|aA|ε A→bA|aB B→aS|bB 试构造一- 个正规式R，使得L(G[S])=L(R)

根据正规文法的定义，我们可以将 G[S] 转化为正则表达式的形式，具体步骤如下：

1. 将 G[S] 转化为 G'[S']，其中 S' 是一个新的非终结符，且 S' → S。

2. 消除 G'[S'] 中的 ε 规则。由于 G'[S'] 中存在 ε 规则，因此我们需要将其消除。具体地，我们可以先求出 G'[S'] 的所有非终结符可以推导出的 ε 集合，然后依次将这些非终结符从 G'[S'] 的产生式中删除 ε，并将删除后的产生式加入到 G'[S'] 中，直到 G'[S'] 中不存在 ε 规则为止。

根据 G'[S'] 的产生式，可以得到以下的 ε 集合：

ε(S') = {ε}

ε(A) = {ε}

ε(B) = {ε}

根据这些 ε 集合，我们可以依次进行如下的操作：

S' → S | ε

A → aB | bA | a

B → bB' | aS

B' → bB' | ε

最终得到消除 ε 规则后的 G'[S']：

S' → S | bS

A → aB | bA | a

B → bB' | aS

B' → bB' | b

3. 消除 G'[S'] 中的单一产生式。由于 G'[S'] 中存在单一产生式，即 S' → S，因此我们需要将其消除。具体地，对于每个非终结符 X，将其所有可以推导出的符号串替换为 X 的直接产生式中的所有符号串，并将替换后的产生式加入到 G'[S'] 中。重复这个过程，直到 G'[S'] 中不存在单一产生式为止。

根据 G'[S'] 的产生式，可以得到以下的直接产生式：

S' → S | bS

A → aB | bA | a

B → bB' | aS

B' → bB' | b

根据这些直接产生式，我们可以依次进行如下的操作：

S' → aB | bA | a | bB' | bS

A → aB | bA | a

B → bB' | aS

B' → bB' | b

4. 将 G'[S'] 转化为正则表达式。由于 G'[S'] 中的所有产生式都是形如 X → αYβ 的形式，其中 α 和 β 是正则表达式，因此我们可以根据这些产生式构造出一个正则表达式 R，使得 L(R) = L(G'[S'])。

根据 G'[S'] 的产生式，可以得到以下的正则表达式：

S' → aB | bA | a | bB'*bS

A → aB | bA | a

B → bB'*aS

B' → b*B

将这些正则表达式合并，得到最终的正则表达式：

R = a(b*B)*a + (b*B)*b(a(b*B)*a + a)*b(B'*b*B)*

综上所述，正规式 R 为 a(b*B)*a + (b*B)*b(a(b*B)*a + a)*b(B'*b*B)*，满足 L(G[S])=L(R)。