ll1语法分析器c++

LL(1)语法分析器是一种自顶向下的语法分析器，可以用于判断一个输入字符串是否符合给定的文法规则。在C++中，可以使用递归下降算法实现LL(1)语法分析器。

下面是一个简单的LL(1)语法分析器C++代码示例：

#include <iostream>
#include <string>

using namespace std;

string input;   // 输入字符串
int pos = 0;    // 当前读取位置

// 判断当前字符是否为指定字符
bool match(char c) {
    if (pos < input.length() && input[pos] == c) {
        pos++;
        return true;
    }
    return false;
}

// 文法规则：E -> T E'
bool E() {
    return T() && E_prime();
}

// 文法规则：E' -> + T E' | ε
bool E_prime() {
    int temp_pos = pos; // 记录位置
    if (match('+') && T() && E_prime()) {   // 匹配 + T E'
        return true;
    }
    pos = temp_pos; // 回溯到上一个位置
    return true;    // 匹配 ε
}

// 文法规则：T -> F T'
bool T() {
    return F() && T_prime();
}

// 文法规则：T' -> * F T' | ε
bool T_prime() {
    int temp_pos = pos; // 记录位置
    if (match('*') && F() && T_prime()) {   // 匹配 * F T'
        return true;
    }
    pos = temp_pos; // 回溯到上一个位置
    return true;    // 匹配 ε
}

// 文法规则：F -> ( E ) | i
bool F() {
    if (match('(') && E() && match(')')) {  // 匹配 ( E )
        return true;
    }
    return match('i');  // 匹配 i
}

int main() {
    cout << "请输入要分析的字符串：" << endl;
    cin >> input;

    if (E() && pos == input.length()) { // 判断是否符合规则且已经到达字符串末尾
        cout << "输入字符串符合规则！" << endl;
    }
    else {
        cout << "输入字符串不符合规则！" << endl;
    }

    return 0;
}

在上面的代码中，我们定义了四个文法规则：E -> T E'、E' -> + T E' | ε、T -> F T'、T' -> * F T' | ε、F -> ( E ) | i。其中，E、E'、T、T'、F分别代表不同的非终结符，+、*、(、)、i分别代表不同的终结符。

在函数match()中，我们判断当前位置上的字符是否为指定字符，若是，则将位置后移一位并返回true，否则返回false。而在各个文法规则的函数中，我们通过调用match()函数来匹配相应的终结符或非终结符，从而判断输入字符串是否符合给定的文法规则。如果符合规则，最后判断pos是否已经到达字符串末尾，如果是，则说明输入字符串符合规则，否则不符合规则。

需要注意的是，在递归下降算法中，存在回溯现象，即在某些情况下，当前所匹配的字符并不符合当前文法规则，需要回溯到上一个位置重新匹配。因此，我们在函数E_prime()和T_prime()中记录当前位置，以便在需要回溯时返回到上一个位置。