Converting BNF grammar rules into actual C++ functions/code

Question

I'm trying to create a recursive descent parser. So far I have all the foundation set, I just need to properly implement a few functions to enforce the grammar. I thought everything was right, it looks it, but I guess my Aop, Expr, or Term function is doing something wrong. Sometimes the input stream gets cut off and things aren't recognized. I don't see how though.

Is there any site or source that explains this more in depth, with code examples? Everything I've seen is very generic, which is fine, but I'm stuck on implementation.

NOTE: Edit April 17 2016: My functions were pretty much alright and well structured for the context of my program. The problem I was having, and didn't realize, was that at certain instances when I called getToken I "ate up" characters from the input stream. Sometimes this is fine, other times it wasn't and the input stream needed to be reset. So I simply add a small loop in cases where I needed to put back strings char by char. E.G:

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;
    }

So with that being said, I pretty much was able to edit my program accordingly and everything worked out once I saw what was eating up the characters.

This is the grammar :

  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

Here's the main program with all of the functions: http://pastebin.com/qMB8h8vE

The functions that I seem to be having the most trouble with is AssignmentOperator(Aop), Expression(Expr), and Term. I'll list them here.

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;
}

Please indent your code (in a way which corresponds with the structure) if you want people to read it. — rici, Apr 13 '16 at 02:20
See my SO answer on how to write recursive descent parsers: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 — Ira Baxter, Apr 13 '16 at 20:36

score 1 · Answer 1 · answered Apr 13 '16 at 23:53

In order to write a recusrive descent parser, you need to convert your grammar into LL form, getting rid of left recursion. For the rules

Term::= Term STAROP Primary | Primary

you'll get something like:

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

this then turns into a function something like:

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;
}

Note that you're going to need a peekToken function to look ahead at the next token without consuming it. Its also possible to use getToken + ungetToken to do the same thing.

Thank you for the information. I'm going to try to implement this tomorrow and see if it works out. I'm still leary about my Aop function, but this adds some well needed info. I also did take into consideration left recursion, so I converted the BNF to EBNF, but that didn't seem to help me as much as I"d like. Either way, thank you. — Abe, Apr 14 '16 at 01:44

Converting BNF grammar rules into actual C++ functions/code

1 Answers1