Java 中的递归下降解析器

我想在序言中说这是我三年级编程语言课的家庭作业，我正在寻求一些帮助。我的作业如下：

截止日期：2013年2月22日晚上11点55分
提交：请将以下内容上传到CMS。

1. 源代码
2. 程序执行的屏幕截图，包括您使用的输入文件

使用您喜欢的任何编程语言编写递归下降解析器来解析由以下 EBNF 描述生成的语言。您的解析器应该检测输入程序是否有任何语法错误。它不必指定错误是什么以及错误在哪里。

<program>   begin <stmt_list> end
<stmt_list>  <stmt> {;<stmt_list>}
<stmt>    <assign_stmt> | <while_stmt>
<assign_stmt>  <var> = <expr>
<var>  identifier  (An identifier is a string that begins with a letter followed by 0     or more letters and digits)
<expr>  <var> { (+|-) <var>}           
<while_stmt>   while (<logic_expr>)  <stmt>
<logic_expr> ® <var> (< | >) <var>  (Assume that logic expressions have only less than     or greater than operators)

看起来很有趣的符号只是指向右侧的箭头。

我现在的问题比编程更符合逻辑：在我的第一次尝试中，我读入整个输入程序，将其保存到一个字符串中，然后解析该字符串并将每个符号转换为终端、expr 或其他符号你。

我最终发现这种方式行不通，因为，A：我不认为它是RDP，B：许多非终端由多于1个语句组成。

我放弃了这种方法，并决定在浪费更多时间编程之前，我将伪所有内容。我的新想法是为每个非终结符创建 1 个方法，然后逐个符号地解析输入字符串，希望在这些方法之间进行。这种方法看起来很合乎逻辑，但当我开始编写伪代码时，我对自己需要做什么感到非常迷失和困惑。我将如何完成这段代码？

以下是 RDP 的一些伪代码：

intputString;

public void parseProgram (Symbol.typeIsProgram) {
    if getNextSymbol == "begin" {
        if (intputString.substring (inputString.length()-3,
                inputString.length()) == "end") {
            Symbol stmt_lsit = new Symbol (intputString)
            parseStmt_list(stmt_list);              
        } else {
            Out "error, prog must end with end"
        }
    } else {
        Out "error, prog must begin with begin"
    }   
}

public void parseStmt_list (Stmbol.typeIsStmt_list) {
    symbol = getNextSymbol;
    if (Symbol.typeIsVar) {
        parseVar(symbol)
    } else if (Symbol.typeIsWhile)  {
        // weve only capture if the first word return is a while, we dont have the whole while statement yet
        ParseWhile_stmt(symbol)
    } else { }
}

public void parseStmt () { }
public void parseAssign_stmt () { }
public void parseVar () { }
public void parseExpr () { }
public void parseWhile_stmt () { }
public void parseLogic_expr () { }

public Symbol getNextSymbol() {
    //returns the next symbol in input string and removes it from the input string
}

仅供参考，我的解析器的示例输入程序是。

begin 
total = var1 + var2; 
while (var1 < var2) 
while ( var3 > var4)
var2 = var2 - var1 
end

根据这个特定的分配，可以以函数方式使用字符串处理。

尝试这个算法：

1. 检查，该行以begin并以end
2. 如果是 - 将剩余的字符串拆分为;并对每个部分（语句）执行以下步骤
3. 检查语句是否包含= or while子串
4. 对于分配检查，您可以将输入拆分为+ or -并针对每个部分检查可变条件（字母数字内容）
5. 一会儿 - 检查( and )并递归处理括号之间及其之后的两个字符串
6. 最后，对于按子字符串分割的逻辑表达式< or >，并检查零件是否是变量（字母数字）

也许，这不是非常灵活的解决方案，但据我所知，它对于您的任务来说是可以接受的。

EDIT:

我发现这个任务很有趣，并尝试编写一个完整的解决方案。

public enum Parser {
PROGRAM {
    void parse(String s) throws ParseException {
        s = s.trim();
        if (s.startsWith("begin") && s.endsWith("end")) {
            STATEMENT_LIST.parse(s.substring(5, s.length() - 3));
        } else {
            throw new ParseException("Illegal begin/end");
        }
    }
},

STATEMENT_LIST {
    void parse(String s) throws ParseException {
        String[] parts = s.trim().split(";");
        for (String part : parts) {
            STATEMENT.parse(part.trim());
        }
    }
},

STATEMENT {
    void parse(String s) throws ParseException {
        if (s.startsWith("while")) {
            WHILE.parse(s.substring(5));
        } else if (s.contains("=")) {
            ASSIGNMENT.parse(s);
        } else {
            throw new ParseException("Illegal statement: " + s);
        }
    }
},

WHILE {
    void parse(String s) throws ParseException {
        int i = s.indexOf("(");
        int j = s.indexOf(")");
        if (i != -1 && j != -1) {
            LOGICAL.parse(s.substring(i + 1, j).trim());
            STATEMENT.parse(s.substring(j + 1).trim());
        } else {
            throw new ParseException("Illegal while: " + s);
        }
    }
},

ASSIGNMENT {
    void parse(String s) throws ParseException {
        int i = s.indexOf("=");
        if (i != -1) {
            VARIABLE.parse(s.substring(0, i).trim());
            EXPRESSION.parse(s.substring(i + 1).trim());
        }
    }
},

EXPRESSION {
    void parse(String s) throws ParseException {
        String[] parts = s.split("\\+|-");
        for (String part : parts) {
            VARIABLE.parse(part.trim());
        }
    }
},

LOGICAL {
    void parse(String s) throws ParseException {
        int i;
        if (s.contains("<")) {
            i = s.indexOf("<");
        } else if (s.contains(">")) {
            i = s.indexOf(">");
        } else {
            throw new ParseException("Illegal logical: " + s);
        }

        VARIABLE.parse(s.substring(0, i).trim());
        VARIABLE.parse(s.substring(i + 1).trim());
    }
},

VARIABLE {
    void parse(String s) throws ParseException {
        if (!s.matches("^[a-zA-Z][a-zA-Z0-9]*$")) {
            throw new ParseException("Illegal variable: " + s);
        }
    }
};

abstract void parse(String s) throws ParseException;

public static void main(String[] args) {
    try {
        PROGRAM.parse("begin \n" +
                "total = var1 + var2; \n" +
                "while (var1 < var2) \n" +
                "while ( var3 > var4)\n" +
                "var2 = var2 - var1 \n" +
                "end");
        System.out.println("OK");
    } catch (ParseException e) {
        System.out.println(e.getMessage());
    }
}
}

class ParseException extends Exception {
public ParseException(String message) {
    super(message);
}
}