java - 如何解析这个语法？

Question

我想在java中为以下语法创建一个递归后代解析器(我已经成功创建了标记)。这是语法的相关部分:

expression ::= numeric_expression | identifier | "null" 
identifier ::= "a..z,$,_"
numeric_expression ::= ( ( "-" | "++" | "--" ) expression )
      | ( expression ( "++" | "--" ) )
      | ( expression ( "+" | "+=" | "-" | "-=" | "*" | "*=" | "/" | "/=" | "%" | "%=" ) expression )
arglist ::= expression { "," expression } 

我已经编写了用于解析numeric_expression的代码(假设如果 token 无效，则返回null):

    NumericAST<? extends OpAST> parseNumericExpr() {
        OpAST op;
        if (token.getCodes() == Lexer.CODES.UNARY_OP) { //Check for unary operator like "++" or "--" etc
            op = new UnaryOpAST(token.getValue());

            token = getNextToken();
            AST expr = parseExpr();        // Method that returns expression node.
            if (expr == null) {
                op = null;
                return null;
            } else {
                if (checkSemi()) {
                    System.out.println("UNARY AST CREATED");
                    return new NumericAST<OpAST>(expr, op, false);
                }
                else {
                    return null;
                }
            }
        } else {   // Binary operation like "a+b", where a,b ->expression
            AST expr = parseExpr(); 
            if (expr == null) {
                return null;
            } else {
                token = getNextToken();
                if (token.getCodes() == Lexer.CODES.UNARY_OP) {
                    op = new UnaryOpAST(token.getValue());
                    return new NumericAST<OpAST>(expr, op, true);
                } else if (token.getCodes() == Lexer.CODES.BIN_OP) {
                    op = new BinaryOpAST(token.getValue());
                    token = getNextToken();

                    AST expr2 = parseExpr();
                    if (expr2 == null) {
                        op = null;
                        expr = null;
                        return null;
                    } else {
                        if (checkSemi()) {
                            System.out.println("BINARY AST CREATED");
                            return new NumericAST<OpAST>(expr, op, expr2);
                        }
                        else {
                            return null;
                        }

                    }
                } else {
                    expr = null;
                    return null;
                }
            }
        }
    }

现在，如果我得到像 ++ 这样的一元运算符，我可以直接调用此方法，但我不知道如何识别其他语法，从相同的产生式开始，例如 arglist 和 numeric_expression 以“表达式”作为开始生产。

我的问题是:

如果我获得表达式 token ，如何识别是否调用 parseNumericExpr() 还是 parseArgList()(上面未提及的方法)？

Answer 1

为了编写递归下降解析器，您需要一个适当的自顶向下语法，通常是 LL(1) grammar ，尽管使用 EBNF 运算符编写语法很常见，如维基百科页面上 recursive descent grammars 上的示例语法所示。

不幸的是，你的语法不是 LL(1)，你提出的问题是这个事实的结果。 LL(1) 语法具有这样的属性:解析器始终可以通过仅检查下一个输入标记来确定要使用哪个产生式，这对语法提出了一些严格的限制，包括:

• 同一个非终结符的两个产生式不能以相同的符号开头。
• 任何产生式都不能是左递归的(即右侧的第一个符号是定义的非终结符)。

下面是对语法的一个小的重新排列，它将起作用:

-- I added number here in order to be explicit.
atom       ::= identifier | number | "null" | "(" expression ")"
-- I added function calls here, but it's arguable that this syntax accepts
-- a lot of invalid expressions
primary    ::= atom { "++" | "--" | "(" [ arglist ] ")" }
factor     ::= [ "-" | "++" | "--" ] primary
term       ::= factor { ( "*" | "/" | "%" ) factor }
value      ::= term { ( "+" | "-" ) term }
-- This adds the ordinary "=" assignment to the list in case it was
-- omitted by accident. Also, see the note below.
expression ::= { value ( "=" | "+#" | "-=" | "*=" | "/=" | "%=" ) } value
arglist    ::= expression { "," expression }

最后一个表达式规则试图捕获赋值运算符的常用语法(与右侧关联，而不是与左侧关联)，但它遇到了 highly related question 的经典问题解决。我认为我对这个问题没有比三年前写的更好的答案，所以我希望它仍然有用。