如何解析这个语法？

Question

我想在 java 中为以下语法创建一个递归后代解析器（我已经设法创建了标记）。这是语法的相关部分：

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

我已经编写了解析 numeric_expression 的代码（假设如果令牌无效，return 为 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 具有 "expression"作为开始生产。

我的问题是：

如果我得到一个表达式令牌，如何识别是调用parseNumericExpr()还是parseArgList()（上面没有提到的方法）？

Answer 1

为了编写递归下降解析器，您需要适当的自顶向下语法，通常是 LL(1) grammar, although it's common to write the grammar using EBNF operators, as shown in the example grammar on Wikipedia's page on 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 }

最后一个 expression 规则试图捕捉赋值运算符的常用语法（关联到右边，而不是左边），但它遇到了一个经典的问题地址 .我认为我对这个问题没有比三年前写的更好的答案了，所以我希望它仍然有用。

如何解析这个语法？

How to parse this grammar?

java

grammar

parsing