递归下降分析程序：判断单词序列是否符合文法

本文介绍一个使用递归下降分析方法判断单词序列是否符合给定文法的程序。

文法规则

假设给定的文法为：

G(A):
A→iB*e
B→SB|e
S→[eC]|.i
C→eC|e

程序实现

以下是该文法的递归下降分析程序：

#include <iostream>
#include <string>

using namespace std;

string word;  // 存储输入的单词序列
int pos;  // 当前处理的单词在序列中的位置

bool match(char c) {  // 匹配一个字符，如果匹配成功则返回true，否则返回false
    if (pos < word.length() && word[pos] == c) {
        pos++;
        return true;
    }
    else {
        return false;
    }
}

bool A() {  // 分析A → iB*e
    if (match('i')) {
        if (B()) {
            if (match('*')) {
                if (match('e')) {
                    return true;
                }
            }
        }
    }
    return false;
}

bool B() {  // 分析B → SB | e
    int oldPos = pos;
    if (S()) {
        if (B()) {
            return true;
        }
    }
    pos = oldPos;
    return true;
}

bool S() {  // 分析S → [eC] | .i
    int oldPos = pos;
    if (match('[')) {
        if (match('e')) {
            if (C()) {
                if (match(']')) {
                    return true;
                }
            }
        }
    }
    pos = oldPos;
    if (match('.')) {
        if (match('i')) {
            return true;
        }
    }
    return false;
}

bool C() {  // 分析C → eC | e
    if (match('e')) {
        if (C()) {
            return true;
        }
        else {
            return false;
        }
    }
    return true;
}

int main() {
    cout << "请输入单词序列：";
    cin >> word;
    pos = 0;
    if (A() && pos == word.length()) {
        cout << "Success" << endl;
    }
    else {
        cout << "Error" << endl;
    }
    return 0;
}

程序解释

match函数 用于匹配一个字符，如果当前处理的单词和该字符相同，则将pos加1，表示已经匹配成功；否则返回false，表示匹配失败。
A、B、S、C 分别对应文法中的四个非终结符。它们的实现方式类似，都是尝试匹配某些字符或调用其他的非终结符。
主函数 中，先读入单词序列，然后调用A进行分析。如果A分析成功并且pos已经到达单词序列的结尾，则说明该单词序列符合该文法的要求，输出“Success”；否则输出“Error”。

使用方法

将上述代码保存为一个C++文件（例如：grammar.cpp）。
使用编译器编译该文件，例如：g++ grammar.cpp -o grammar
运行可执行文件，例如：./grammar
输入单词序列，程序将判断该单词序列是否符合文法的要求，并输出结果。

总结

本文介绍了一个简单的递归下降分析程序，它可以用于判断单词序列是否符合给定的文法。该程序代码清晰易懂，并附有详细的注释解释。