const char *p[]={ "", "D->TL", "T->i", "T->f", "L->L,x", "L->x" }; 1.消除左递归 2.构造First和Follow集合 3.构造LL(1)分析表 4.是不是LL(1)文法 5.编程实现

1. 消除左递归:

原始文法为:

D -> TL
T -> i | f
L -> L,x | x

将其转化为无左递归的文法:

D -> TL
T -> iR | fR
R -> ,xR | ε
L -> xS
S -> R | ,xS

2. 构造First和Follow集合:

First(D) = {i, f}
First(T) = {i, f}
First(R) = {ε, ,}
First(L) = {x}
First(S) = {ε, ,}
Follow(D) = {$}
Follow(T) = {L}
Follow(R) = {L}
Follow(L) = {)}
Follow(S) = {)}

3. 构造LL(1)分析表:

| i | f | x | , | ( | ) | $
-----+-------+-------+-------+-------+-------+-------+-------
D | TL | TL | | | | |
T | iR | fR | | | | |
R | | | ε | ,xR | ε | ε | ε
L | | | xS | | | |
S | ε | ε | | ,xS | | ) | )

4. 是否是LL(1)文法:

通过观察LL(1)分析表可以发现，每个非终结符的每个产生式的First集合与Follow集合之间没有交集，因此该文法是LL(1)文法。

5. 编程实现:

以下是该文法的LL(1)分析程序的示例代码（使用C++语言实现）：

#include <iostream>
#include <string>
using namespace std;

const char *p[] = {"", "D->TL", "T->iR", "T->fR", "R->,xR", "R->ε", "L->xS", "S->R", "S->,xS", "S->ε"};

char M[6][7][3] = {
    {"", "", "", "", "", "", ""},
    {"TL", "TL", "", "", "", "", ""},
    {"iR", "fR", "", "", "", "", ""},
    {"", "", "ε", ",xR", "ε", "ε", "ε"},
    {"", "", "xS", "", "", "", ""},
    {"", "", "ε", "", "", "", ""},
};

string input;

int getVN(char c) {
    if (c == 'D') return 1;
    if (c == 'T') return 2;
    if (c == 'R') return 3;
    if (c == 'L') return 4;
    if (c == 'S') return 5;
    return 0;
}

int getVT(char c) {
    if (c == 'i') return 0;
    if (c == 'f') return 1;
    if (c == 'x') return 2;
    if (c == ',') return 3;
    if (c == '(') return 4;
    if (c == ')') return 5;
    if (c == '$') return 6;
    return -1;
}

void analyze() {
    input += '$';
    int i = 0, j = 0, k = 0;
    char stack[100] = {'$', 'D'};
    while (stack[0] != '$') {
        char c = stack[0];
        if (c == input[i]) {
            i++;
            for (int l = 0; l < k; l++) {
                stack[l] = stack[l + 1];
            }
            k--;
        } else if (getVN(c)) {
            int vn = getVN(c);
            int vt = getVT(input[i]);
            if (M[vn][vt][0] == '\0') {
                cout << "Error!" << endl;
                return;
            }
            for (int l = 0; l < k; l++) {
                stack[l] = stack[l + 1];
            }
            k--;
            if (M[vn][vt][0] != 'ε') {
                for (int l = strlen(M[vn][vt]) - 1; l >= 0; l--) {
                    stack[k++] = M[vn][vt][l];
                }
            }
        } else {
            cout << "Error!" << endl;
            return;
        }
    }
    cout << "Success!" << endl;
}

int main() {
    cout << "Please input the string to be analyzed:" << endl;
    cin >> input;
    analyze();
    return 0;
}