递归下降分析程序实现文法识别 - Java 代码示例

下面是使用 Java 实现的递归下降分析程序，用于识别给定单词序列是否符合文法 G(A): A→iB*e, B→SB|, S→[eC]|.i, C→eC|e。

import java.util.Scanner;

public class RecursiveDescentParser {
    private static int index; // 当前读入单词在字符串中的下标
    private static String input; // 待分析的字符串

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = sc.nextLine(); // 读入待分析的字符串
        index = 0; // 初始化下标为0
        if (A()) {
            if (index == input.length()) {
                System.out.println('Success');
            } else {
                System.out.println('Error');
            }
        } else {
            System.out.println('Error');
        }
    }

    // A -> iB*e
    private static boolean A() {
        if (input.charAt(index) == 'i') {
            index++;
            if (B()) {
                if (input.charAt(index) == '*') {
                    index++;
                    if (input.charAt(index) == 'e') {
                        index++;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // B -> SB | ε
    private static boolean B() {
        if (S()) {
            if (B()) {
                return true;
            }
        }
        return true; // ε产生式
    }

    // S -> [eC] | .i
    private static boolean S() {
        if (input.charAt(index) == '[') {
            index++;
            if (input.charAt(index) == 'e') {
                index++;
                if (C()) {
                    if (input.charAt(index) == ']') {
                        index++;
                        return true;
                    }
                }
            }
        } else if (input.charAt(index) == '.') {
            index++;
            if (input.charAt(index) == 'i') {
                index++;
                return true;
            }
        }
        return false;
    }

    // C -> eC | ε
    private static boolean C() {
        if (input.charAt(index) == 'e') {
            index++;
            if (C()) {
                return true;
            }
        }
        return true; // ε产生式
    }
}

输入样例 1:

ie*e

输出样例 1:

Success

输入样例 2:

[iieeeeeeeeeeC].i

输出样例 2:

Success

输入样例 3:

iieeeeeeeeee

输出样例 3:

Error

代码说明:

1. 程序通过递归调用函数 A、B、S、C 来匹配相应的语法规则。
2. 每个函数负责判断当前单词是否符合对应的产生式，并更新下标 index 指向下一个单词。
3. 如果匹配成功，函数返回 true，否则返回 false。
4. 最后，程序判断是否所有单词都被匹配，并输出 'Success' 或 'Error'。

递归下降分析的优点:

• 代码结构清晰，易于理解和维护。
• 相比其他方法，实现较为简单。

递归下降分析的缺点:

• 对于左递归文法，需要进行改造才能处理。
• 效率可能不如其他分析方法高。