Разбор рекурсивного спуска

Question

Я искал какой-нибудь совет / помощь по моему заданию.Так как это для класса, я не прошу никого буквально выписывать ответы для меня, но мне действительно нужна помощь с моим фактическим кодированием.

Вопрос:

Подумайтеследующая грамматика BNF:

A -> I = E  
E -> T + E | T - E | T  
T -> F * T | F / T | F  
F -> P ^ F | P  
P -> I | L | (E)  
I -> a | b | ... | y | z  
L -> 0 | 1 | ... | 8 | 9  

Используя технику, описанную в классе, реализует синтаксический анализатор рекурсивного спуска, который распознает строки на этом языке.Ввод должен быть из файла с именем input.dat, а вывод - в консоль.Пример сеанса может выглядеть следующим образом:

Строка, прочитанная из файла: a=a+b-c*d Строка "a=a+b-c*d" на языке.Строка, прочитанная из файла: a=a**b++c Строка "a=a**b++c" не на языке.

Вы должны реализовать проект на ОБА Java и C ++!Реализации, которые не включают решения на обоих языках, в лучшем случае получат половину кредита.Чтобы упростить задачу, вам не придется обрабатывать пробелы при разборе строки, т.е. «» и similiar являются недопустимыми символами в этом языке.

Правильный связанный пример с другой грамматикой:

// * <assign> => <id> = <expr>
// *     <id> => a | b | c
// *   <expr> => <lit> + <lit> | <lit> - <lit>
// *    <lit> => 0 | ... | 9 | (<expr>)

#include <iostream>

using std::cout;
using std::endl;

bool assign(void);
bool id(void);
bool expr(void);
bool lit(void);

char *c;

int main(int argc, char *argv[]) {

    c = argc == 2 ? argv[1] : (char *)"";

    if (assign() && *c == '\0') {
        cout << "The string \"" << argv[1] << "\" is in the language." << endl;
    }
    else {
        cout << "The string \"" << argv[1] << "\" is not in the language." << endl;
    }

    return 0;
}

bool assign(void) {

    if (id()) {
        if (*c == '=') {
            ++c;
            if (expr()) {
                return true;
            }
        }
    }

    return false;
}

bool id(void) {

    if (*c >= 'a' && *c <= 'c') {
        ++c;
        return true;
    }

    return false;
}

bool expr(void) {

    if (lit()) {
        if (*c == '+' || *c == '-') {
            ++c;
            if (lit()) {
                return true;
            }
        }
    }

    return false;
}

bool lit(void) {

    if (*c >= '0' && *c <= '9') {
        ++c;
        return true;
    }
    else {
        if (*c == '(') {
            ++c;
            if (expr()) {
                if (*c == ')') {
                    ++c;
                    return true;
                }
            }
        }
    }

    return false;
}

Моя настоящая работа на данный момент: (Я сейчас опускаю чтение из файла txt, хочусначала запустите грамматику) edit1: Проблема в том, что ни одна из строк не отображается в виде допустимых строк в языке.К сожалению, даже простая строка, такая как a = b, должна проходить почти по всем правилам производства, поэтому я не могу указать, где я ошибаюсь

//A -> I = E 
//E -> T + E | T - E | T 
//T -> F * T | F / T | F 
//F -> P ^ F | P 
//P -> I | L | (E) 
//I -> a | b | ... | y | z 
//L -> 0 | 1 | ... | 8 | 9 

#include <iostream>

using namespace std;

bool A(void);
bool E(void);
bool T(void);
bool F(void);
bool P(void);
bool I(void);
bool L(void);

char *c;

int main(int argc, char *argv[]){

     c = argc == 2 ? argv[1] : (char *)"";

    if (A() && *c == '\0') {
        cout << "The string \"" << argv[1] << "\" is in the language." << endl;
    }
    else {
        cout << "The string \"" << argv[1] << "\" is not in the language." << endl;
    }

    return 0;
}

bool A(void){

    if( I() )
    {
        if ( *c == '=' ){
            ++c;
            if ( E() )
            return true;
        }
    }

    return false;
}

bool E(void){

    if( T() ){
        if ( *c == '+' || *c == '-' ){
                ++c;
                if ( E() )
                return true;
        }
    }
    else
    if ( T() ){
        ++c;
        return true;
    }

    return false;
}

bool F(void){

    if( P() ){
        if( *c == '^')
        ++c;
        if( F() )
        return true;
    }
    else
    if ( P() ){
        ++c;
        return true;
    }

    return false;

}

bool I(void){

    if ( *c >= 'a' && *c <= 'z'){
        ++c;
        return true;
    }

    return false;

}

bool L(void){

    if ( *c >= '0' && *c <= '9' ){
    ++c;
    return true;
    }

    return false;
}

bool P(void){

    if ( I() ){
        ++c;
        return true;
    }
    else
    if ( L() ){
        ++c;
        return true;
    }
    else
    if ( *c == '(' ){
            ++c;
            if ( E() ){
                    if ( *c == ')' ){
                        ++c;
                        return true;
                    }
            }
    }

    return false;
}

bool T(void){

    if( F() ){
        if ( *c == '*' || *c == '/' ){
                ++c;
                if ( T() )
                return true;
        }
    }
    else
    if ( F() ){
        ++c;
        return true;
    }

    return false;
}

Answer 1

Я думаю, что у вас есть общая проблема с обнаружением таких вещей, как

E = T + E | T - E | T

Когда вы ищите T(), и он терпит неудачу, вы пытаетесь снова искать T().Вы допустили эту ошибку и в большинстве других функций.

Правильная реализация для E() будет ( обновлена ​​после комментария Криса ):

if (T())
{
   if (c == '+' || c == '-')
   {  
      ++c;
      return E();
   }
   return true;
}
return false;

Давайте рассмотрим пример: «a = (3)»

A() -> I() возвращает true -> c == '=' -> E() -> T() возвращает true при разборе 3 после вызова P(), который завершается вызовом E() снова -> сейчас c == ')', поэтому нам нужно вернуть true в E(), в противном случае, если мы вернем false, здесь остановится в P()

Надеюсь, это не слишком запутанно, но здесь трудно выразить это.Лучше всего, если вы нарисуете дерево разбора на листе бумаги для его визуализации.

Обновите снова : у вас похожая ситуация в T() и F()