我需要使用堆栈来实现递归下降解析器吗？

Question

我启动了递归下降解析器，到目前为止它工作得很好。解析输入后返回“ACCEPT”或“REJECT”。但是，我在网上和另一本教科书上看到他们正在“使用 PDA 进行自上而下的解析”。所以，我只是想确认这只是解析器编码的另一种方式，而不是方式。我的解析器看起来像这样：

public class Parser {

private int n = 0;
private Tokens token = Main.TokenList.get(n);

public Parser() {
        Boolean bool = parse_Program();
        if (bool){
            System.out.println("ACCEPT");
        }else System.out.println("REJECT");

}

Boolean parse_Program(){
    if (!parse_DeclarationList()){
         return false;
    }
    return true;
}

private boolean parse_DeclarationList() {
    if (!parse_Declaration()){
        return false;
    }
    if(!parse_DeclarationListPrime()){
          return false;
    }
    return true;
}

private boolean parse_DeclarationListPrime() {
        if (token.getContents().equals("int") || token.getContents().equals("void") || token.getContents().equals("float")) {
            if (!parse_Declaration()) {
                return false;
            }else return true;
        }else if (token.getContents().equals("$")){
            return true;
        }

    return false;
}


private boolean parse_Declaration() {
    if (!parse_TypeSpecifier()){
        return false;
    }
    if (token.getType().equals("ID")){
        Accept();
    }else return false;

    if (!parse_DDD()){
        return false;
    }
    return true;
}

private boolean parse_DDD() {
    if (token.getContents().equals("(")){
        Accept();
        if(!parse_params()){
            return false;
        }
        if (token.getContents().equals(")")){
            Accept();
            if (!parse_compoundStmt()){
                return false;
            }else return true;
        }
    }else if (token.getContents().equals(";") || token.getContents().equals("[")){
        if (!parse_varDeclarationPrime()){
            return false;
        }else return true;
    }
    return false;
}

private boolean parse_compoundStmt() {
    if (token.getContents().equals("{")){
        Accept();
        if (!parse_localDeclarations()){
            return false;
        }
        if (token.getContents().equals("}")){
            Accept();
            return true;
        }
    }
    return false;
}

private boolean parse_localDeclarations() {
    if (!parse_localDeclarationsPrime()){
        return false;
    }else return true;
}

private boolean parse_localDeclarationsPrime() {
    if (!parse_varDeclaration()){
        return false;
    }
    return true;
}

private boolean parse_params() {
   if (token.getContents().equals("int") || token.getContents().equals("void") || token.getContents().equals("float")) {
        if (getNextToken().getContents().equals(")") && token.getContents().equals("void")) {
            Accept();
            return true;
        } else {
            if (!parse_paramList()) {
                return false;
            } else return true;
        }
    }
    return false;
}

private Tokens getNextToken() {
    Tokens nextToken = Main.TokenList.get(n+1);
    return nextToken;
}

private boolean parse_paramList() {
    if (!parse_param()){
        return false;
    }
    if (!parse_paramListPrime()){
        return false;
    }
    return true;
}

private boolean parse_paramListPrime() {
    if (token.getContents().equals(",")){
        Accept();
        if (!parse_param()){
            return false;
        }
        if (!parse_paramListPrime()){
            return false;
        }
        return true;
    }else if (token.getContents().equals(")")){
        return true;
    }
    return false;
}


private boolean parse_param() {
    if (token.getContents().equals("int") || token.getContents().equals("void") || token.getContents().equals("float")){
        Accept();
        if (token.getType().equals("ID")){
            Accept();
            if (!parse_paramPrime()){
                return false;
            }else return true;
        }
    }
    return false;
}

private boolean parse_paramPrime() {
    if (token.getContents().equals("[")){
        Accept();
        if (token.getContents().equals("]")){
            Accept();
            return true;
        }
    }else if (token.getContents().equals(")")){
        return true;
    }
    return false;
}

private boolean parse_varDeclaration() {
    if (!parse_TypeSpecifier()){
        return false;
    }
    if (token.getType().equals("ID")){
        Accept();
    }else
        return false;
    if (!parse_varDeclarationPrime()){
        return false;
    }
    return true;
}

private boolean parse_varDeclarationPrime() {
    if (token.getContents().equals(";")){
        Accept();
        return true;
    }else if (token.getContents().equals("[")){
        Accept();
        if (token.getType().equals("NUM")){
            Accept();
            if (token.getContents().equals("]")){
                Accept();
                if (token.getContents().equals(";")){
                    Accept();
                    return true;
                }
            }
        }
    }
    return false;
}

private void Accept() {
    try {
        if ((n + 1) <= Main.TokenList.size() - 1) {
            token = Main.TokenList.get(++n);
        } else {
            token.setContents("$");
        }
    }catch (Exception e){

    }
}

private boolean parse_TypeSpecifier() {
    if (token.getContents().equals("int") || token.getContents().equals("float") || token.getContents().equals("void")){
        Accept();
        return true;
    }
    return false;
}

这是课本上的：

Answer 1

自上而下的解析需要某种解析器堆栈。递归下降解析的要点是将调用堆栈用作解析器堆栈。因此，您应该考虑将教科书中的算法视为递归下降的替代方法。

递归下降是一种流行的解析解决方案，但在像 C（或 C++）这样不能检测堆栈溢出（或不能可靠地检测到它）的语言中可能会出现问题。在这种情况下，您可能希望为生产解析器使用专用的解析器堆栈，特别是在以下情况下：

• 您在多线程应用程序中运行解析器（以便堆栈很小）；

• 无论您正在解析什么，都应该具有深层嵌套（也许它是树状数据结构）；

• 您正在解析未经验证的输入，并且担心攻击者提供过度嵌套的输入；

• 您还没有努力最小化堆栈帧的大小，也许是因为您对动态内存分配过敏。

一般来说，您应该避免递归下降，并在预期最大调用堆栈深度可能超过可用堆栈大小的任何上下文中使用显式堆栈。

或者，您可以使用解析器生成器来生成具有受控堆栈大小的解析器。