Преобразование правил грамматики BNF в реальные функции / код C++

Question

Я пытаюсь создать парсер рекурсивного спуска. Пока у меня есть все основы, мне просто нужно правильно реализовать несколько функций для применения грамматики. Я думал, что все было правильно, это выглядит, но я думаю, мой Aop, Expr, или же Term Функция делает что-то не так. Иногда входной поток отключается, а вещи не распознаются. Я не понимаю, как, хотя.

Есть ли какой-либо сайт или источник, который объясняет это более подробно, с примерами кода? Все, что я видел, очень общее, и это хорошо, но я застрял в реализации.

ПРИМЕЧАНИЕ: редактировать 17 апреля 2016 года. Мои функции были в значительной степени хорошо и хорошо структурированы для контекста моей программы. Проблема, с которой я столкнулся и не осознавал, заключалась в том, что в некоторых случаях, когда я вызывал getToken, я "съел" символы из входного потока. Иногда это нормально, а иногда - нет, и входной поток необходимо сбросить. Поэтому я просто добавляю небольшой цикл в тех случаях, когда мне нужно было возвращать строки char на char. НАПРИМЕР:

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, избавившись от левой рекурсии. По правилам

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 сделать то же самое.