c++ - 将 BNF 语法规则转换为实际的 C++ 函数/代码

Question

我正在尝试创建一个递归下降解析器。到目前为止，我已经有了所有的基础，我只需要正确地实现一些函数来强制语法。我认为一切正常，看起来是这样，但我想我的 Aop、Expr 或 Term 函数做错了什么。有时输入流会被切断，无法识别。我不知道如何。

是否有任何网站或资源可以通过代码示例更深入地解释这一点？我所看到的一切都非常通用，这很好，但我坚持执行。

注意:编辑 2016 年 4 月 17 日:我的函数非常好，并且针对我的程序上下文结构良好。我遇到但没有意识到的问题是，在某些情况下，当我调用 getToken 时，我从输入流中“吃掉”了字符。有时这很好，有时则不然，需要重置输入流。因此，我只是在需要逐个字符地放回字符串的情况下添加一个小循环。例如:

if(t.getType() !=Token::EQOP)
    {
        //cout<<"You know it" << endl;
        int size = t.getLexeme().size();


        while(size>0)
        {
        br->putback(t.getLexeme().at(size-1));
        size--;
        }

        return ex;
    }

因此，话虽如此，我几乎能够相应地编辑我的程序，一旦我看到是什么在吞噬角色，一切都会顺利进行。

这是语法:

  Program::= StmtList
  StmtList::= Stmt | StmtList
  Stmt::= PRINTKW Aop SC | INTKW VAR SC | STRKW VAR SC | Aop SC
  Expr::= Expr PLUSOP Term | Expr MINUSOP Term | Term
  Term::= Term STAROP Primary | Primary
  Primary::= SCONST | ICONST | VAR | LPAREN Aop RPAREN

这是具有所有功能的主程序:http://pastebin.com/qMB8h8vE

我似乎遇到最多麻烦的函数是 AssignmentOperator(Aop)、Expression(Expr) 和 Term。我会在这里列出它们。

ParseTree* Aop(istream *br)
{
    ParseTree * element = Expr(br);
    if(element!=0)
    {
        if(element->isVariable())
        {
            Token t= getToken(br);

            if(t==Token::EQOP)
            {                   
                cout<<"No" << endl;
                ParseTree * rhs = Aop(br);
                if(rhs==0)
                    return 0;
                else
                {
                    return new AssignOp(element, rhs);
                }
            }
            else
            {
                return element;
            }
        }
    }

    return 0;
}

ParseTree* Expr(istream *br)
{
    ParseTree * element = Term(br);
    if(element!=0)
    {
        Token t=getToken(br);
        if(t==Token::MINUSOP || t==Token::PLUSOP)
        {
            if(t==Token::PLUSOP)
            {
                ParseTree* rhs = Expr(br);
                if(rhs==0)
                    return 0;
                else
                {
                    return new AddOp(element, rhs);
                }
            }

            if(t==Token::MINUSOP)
            {
                ParseTree* rhs = Expr(br);
                if(rhs==0)
                    return 0;
                else
                {
                    return new SubtractOp(element, rhs); //or switch the inputs idk
                }
            }
        }
        else
        {
            return element;
        }
    }

    return 0;
}

ParseTree* Term(istream *br)
{
    ParseTree *element = Primary(br);

    if(element!=0)
    {
        Token t=getToken(br);
        if(t==Token::STAROP)
        {
            ParseTree* rhs =Term(br);
            if(rhs==0)
                return 0;
            else
            {
                return new MultiplyOp(element, rhs);
            }
        }
        else
        {
            return element;
        }
    }

    return 0;
}

Answer 1

为了编写递归下降解析器，您需要将语法转换为 LL 形式，去掉 left recursion .对于规则

Term::= Term STAROP Primary | Primary

你会得到类似的东西:

Term ::= Primary Term'
Term' ::= epsilon | STAROP Primary Term'

然后这会变成一个类似这样的函数:

ParseTree *Term(istream *br) {
    ParseTree *element = Primary(br);
    while (element && peekToken(br) == Token::STAROP) {
        Token t = getToken(br);
        ParseTree *rhs = Primary(br);
        if (!rhs) return 0;
        element = new MulOp(element, rhs); }
    return element;
}

请注意，您将需要一个 peekToken 函数来预测下一个标记而不使用它。也可以使用 getToken + ungetToken 来做同样的事情。