如何解析这个语法？

Question

如何解析这个语法？

4

我希望您能用Java创建一个递归下降解析器来处理以下语法（我已经创建了标记）。这是语法的相关部分：

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

我已经编写了解析numeric_expression的代码（假设无效的标记将返回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 以“表达式”为起始产生式。

我的问题是：

如何识别是否调用 parseNumericExpr（）或 parseArgList（）（以上未提及的方法），如果我获得一个表达式标记？

- Dhyey Shah

你好，只是想澄清一下，这是你的完整语法定义吗？你在代码中似乎使用了UnaryOperatorAST，但是一元运算符表达式似乎不是你语法中的构建块。 - Paul Benn

1

这个问题太宽泛了，实际上包含了很多问题。请将您的问题集中在一个具体的问题上，并记住这不是一个代码审查网站。 - Joakim Danielson

@JoakimDanielson 我已经澄清了，麻烦您确认一下。 - Dhyey Shah

@PaulBenn，没有提到完整的语法，只是其中一部分。 - Dhyey Shah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

为了编写递归下降解析器，您需要一个合适的自顶向下语法，通常是LL(1)语法，尽管使用EBNF操作符编写语法是常见的，就像维基百科上关于递归下降语法的页面上所示的示例语法一样。

不幸的是，您的语法不是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规则是试图捕获赋值运算符的通常语法（它们从右边关联，而不是从左边关联），但它遭受了一个经典问题，这个高度相关的问题已经解决。我认为我没有比三年前写的更好的答案，所以希望它仍然有用。