Recursive Descent Interpreter

[shadow29014]

Guys Im kinda new to programing. I have an assignment which I have now idea on what to do. Im asked to rewrite a Simple Recursive Descent Interpreter implementing it using a list class without using templates and facilites from the standard template library. Since #include <list> is part of the standard template library it is confusing on how to use a list class without using #include <list>. Thank You For You Help =)

Here is the Source Codes:
//************************** interpreter.cpp ***********************

#include <cctype>
#include "interpreter.h"

double Statement::findValue(char *id) {
IdNode tmp(id);
IdNode::iterator i = find(idList.begin(),idList.end(),tmp);
if (i != idList.end())
return i->value;
else issueError("Unknown variable");
return 0; // this statement will never be reached;
}

void Statement::processNode(char* id ,double e) {
IdNode tmp(id,e);
IdNode::iterator i = find(idList.begin(),idList.end(),tmp);
if (i != idList.end())
i->value = e;
else idList.push_front(tmp);
}

// readId() reads strings of letters and digits that start with
// a letter, and stores them in array passed to it as an actual
// parameter.
// Examples of identifiers are: var1, x, pqr123xyz, aName, etc.

void Statement::readId(char *id) {
int i = 0;
if (isspace(ch))
cin >> ch; // skip blanks;
if (isalpha(ch)) {
while (isalnum(ch)) {
id[i++] = ch;
cin.get(ch); // don't skip blanks;
}
id[i] = '\0';
}
else issueError("Identifier expected");
}

double Statement::factor() {
double var, minus = 1.0;
static char id[200];
cin >> ch;
while (ch == '+' || ch == '-') { // take all '+'s and '-'s.
if (ch == '-')
minus *= -1.0;
cin >> ch;
}
if (isdigit(ch) || ch == '.') { // Factor can be a number
cin.putback(ch);
cin >> var >> ch;
}
else if (ch == '(') { // or a parenthesized expression,
var = expression();
if (ch == ')')
cin >> ch;
else issueError("Right paren left out");
}
else {
readId(id); // or an identifier.
if (isspace(ch))
cin >> ch;
var = findValue(id);
}
return minus * var;
}

double Statement::term() {
double f = factor();
while (true) {
switch (ch) {
case '*' : f *= factor(); break;
case '/' : f /= factor(); break;
default : return f;
}
}
}

double Statement::expression() {
double t = term();
while (true) {
switch (ch) {
case '+' : t += term(); break;
case '-' : t -= term(); break;
default : return t;
}
}
}

void Statement::getStatement() {
char id[20], command[20];
double e;
cout << "Enter a statement: ";
cin >> ch;
readId(id);
strcpy(command,id);
for (int i = 0; i < strlen(command); i++)
command[i] = toupper(command[i]);
if (strcmp(command,"STATUS") == 0)
cout << *this;
else if (strcmp(command,"PRINT") == 0) {
readId(id);
cout << id << " = " << findValue(id) << endl;
}
else if (strcmp(command,"END") == 0)
exit(0);
else {
if (isspace(ch))
cin >> ch;
if (ch == '=') {
e = expression();
if (ch != ';')
issueError("There are some extras in the statement");
else processNode(id,e);
}
else issueError("'=' is missing");
}
}

//************************** interpreter.h ***********************

#ifndef INTERPRETER
#define INTERPRETER

#include <iostream>
#include <list>
#include <algorithm> // find()

using namespace std;

class IdNode {
public:
IdNode(char *s = "", double e = 0) {
id = strdup(s);
value = e;
}
bool operator== (const IdNode& node) const {
return strcmp(id,node.id) == 0;
}
private:
char *id;
double value;
friend class Statement;
friend ostream& operator<< (ostream& out, const IdNode& r) {
out << r.id << " = " << r.value << endl;
return out;
}
};

class Statement {
public:
Statement() {
}
void getStatement();
private:
list<IdNode> idList;
char ch;
double factor();
double term();
double expression();
void readId(char*);
void issueError(char *s) {
cerr << s << endl; exit(1);
}
double findValue(char*);
void processNode(char*, double);
friend ostream& operator<< (ostream& out, const Statement& s) {
list<IdNode>::const_iterator i = s.idList.begin();
for ( ; i != s.idList.end(); i++)
out << *i;
out << endl;
return out;
}
};

#endif

//************************** useInterpreter.cpp ***********************

#include "interpreter.h"

int main() {
Statement statement;
cout << "The program processes statements of the following format:\n"
<< "\t<id> = <expr>;\n\tprint <id>\n\tstatus\n\tend\n\n";
while (true) // This infinite loop is broken by exit(1)
statement.getStatement(); // in getStatement() or upon finding
return 0; // an error.
}

Again, Thank You ALL very much.

[Bazzy]

That's easy: you need to create your own list class which implements the used std::list methods

[shadow29014]

for example i need .end and .begin from #include <list> instead of using #include <list> im going to create a function end and begin inside my class IdNode then implement it into my my interpreter.cpp so that my end and begin functions does the same thing as .end and .begin from #include <list>.

Is my interpretation right?
Pls correct me if im wrong.
Thanks a lot =)

[Bazzy]

.end and .begin should be found in a list class, that is what you should make.

[shadow29014]

so instead of putting the begin and end functions in the class IdNode, i have to create a class list which includes the functions end and begin and implement it so that the class IdNode can acess #include <list> functions which are implemented in the class List.

For example:

//************************** interpreter.h ***********************

class list
{
public:
void end;
void begin;
}

//inserted before class IdNode and after using namespace std

//************************** interpreter.cpp ***********************

void list :: end ()
{
//some code here
}

void list :: begin ()
{
//some code here
}

//inserted befre double Statement:: findValue and after #include "interpreter.h"

**************************************************************************

Is my understanding correct?
Should the same method be true to #include <algorithm> since the code uses some functions present in the #include <algoritm> ?
If its true do i have to make an algorithm class?
Again thanks =)

[Bazzy]

The problem seems to say that you can't use STL, so you'll have to implement algorithm functions
If the list class should be STL-like you have to have a layout like this:

class Node // Maybe you can merge this class with IdNode
{
    Node *previous;
    Node *next;
    IdNode data;
};
class Iterator
{
    Node *node;
};
class List
{
          Node *head, *tail;
     public:
          Iterator begin();
          Iterator end();
};


/////////////////////////////////////////////


Iterator List::begin()
{
    // return an iterator containing the head
}

Iterator List::end()
{
    // return an iterator containing the tail
}

PS: use [code][/code] tags to make code look nicer on the forum

[shadow29014]

When added the classes and implementation on the codes a lot of error occured.
Such as:
'list is not a template'
'const_iterator' is not a member of 'list'
'iterator' is not a member of 'list'
'const class IdNode' has no member 'end'
'const class IdNode' has no member 'push_front'
Some errors I can understand but these i dont. Can you please explain what these error messages mean Thanks =)

Here are the new codes:

//**************************  interpreter.cpp   ***********************

#include <cctype>
#include "interpreter.h"

Iterator list :: begin()
{
}

Iterator list :: end()
{
}

Iterator list :: get()
{
}

Iterator list :: push_front()
{
}

Iterator list :: putback()
{
}

double Statement::findValue(char *id) {
    IdNode tmp(id);
    list<IdNode>::iterator i = find(idList.begin(),idList.end(),tmp);
    if (i != idList.end())
         return i->value;
    else issueError("Unknown variable");
    return 0;  // this statement will never be reached;
}

void Statement::processNode(char* id ,double e) {
    IdNode tmp(id,e);
    list<IdNode>::iterator i = find(idList.begin(),idList.end(),tmp);
    if (i != idList.end())
         i->value = e;
    else idList.push_front(tmp);
}

// readId() reads strings of letters and digits that start with
// a letter, and stores them in array passed to it as an actual
// parameter. 
// Examples of identifiers are: var1, x, pqr123xyz, aName, etc.

void Statement::readId(char *id) {
    int i = 0;
    if (isspace(ch))
         cin >> ch;       // skip blanks;
    if (isalpha(ch)) {
         while (isalnum(ch)) {
             id[i++] = ch;
             cin.get(ch); // don't skip blanks;
         }
         id[i] = '\0';
    }
    else issueError("Identifier expected");
}

double Statement::factor() {
    double var, minus = 1.0;
    static char id[200];
    cin >> ch;
    while (ch == '+' || ch == '-') {      // take all '+'s and '-'s.
        if (ch == '-')
            minus *= -1.0;
        cin >> ch;
    }
    if (isdigit(ch) || ch == '.') {      // Factor can be a number
         cin.putback(ch);
         cin >> var >> ch;
    }
    else if (ch == '(') {                  // or a parenthesized expression,
         var = expression();
         if (ch == ')')
              cin >> ch;
         else issueError("Right paren left out");
    }
    else {
         readId(id);                          // or an identifier.
         if (isspace(ch))
             cin >> ch;
         var = findValue(id);
    }
    return minus * var;
}

double Statement::term() {
    double f = factor();
    while (true) {
        switch (ch) {
            case '*' : f *= factor(); break;
            case '/' : f /= factor(); break;
            default  : return f;
        }
    }
}

double Statement::expression() {
    double t = term();
    while (true) {
        switch (ch) {
            case '+' : t += term(); break;
            case '-' : t -= term(); break;
            default  : return t;
        }
    }
}

void Statement::getStatement() {
    char id[20], command[20];
    double e;
    cout << "Enter a statement: ";
    cin  >> ch;
    readId(id);
    strcpy(command,id);
    for (int i = 0; i < strlen(command); i++)
	command[i] = toupper(command[i]);
    if (strcmp(command,"STATUS") == 0)
         cout << *this;
    else if (strcmp(command,"PRINT") == 0) {
         readId(id);
         cout << id << " = " << findValue(id) << endl;
    }
    else if (strcmp(command,"END") == 0)
         exit(0);
    else {
         if (isspace(ch))
             cin >> ch;
         if (ch == '=') {
              e = expression();
              if (ch != ';')
                   issueError("There are some extras in the statement");
              else processNode(id,e);
         }
         else issueError("'=' is missing");
    }
}

//**************************  interpreter.h   ***********************

#ifndef INTERPRETER
#define INTERPRETER

#include <iostream>
//#include <list>
//#include <algorithm> // find()

using namespace std;

class IdNode {
public:
    IdNode(char *s = "", double e = 0) {
        id = strdup(s);
        value = e;
    }
    bool operator== (const IdNode& node) const {
        return strcmp(id,node.id) == 0;
    }
private:
    char *id;
    double value;
    friend class Statement;
    friend ostream& operator<< (ostream& out, const IdNode& r) {
        out << r.id << " = " << r.value << endl;
        return out;
    }
};

class Node
{
      Node *previous;
      Node *next;
      IdNode data;
};

class Iterator
{
      Node *node;
};

class list
{
      Node *head, *tail;
      public:
             Iterator begin ();
             Iterator end ();
             Iterator get ();
             Iterator push_front ();
             Iterator putback ();
}

class Statement {
public:
    Statement() { 
    }
    void getStatement();
private:
    IdNode idList;
    char  ch;
    double factor();
    double term();
    double expression();
    void readId(char*);
    void issueError(char *s) { 
        cerr << s << endl; exit(1); 
    }
    double findValue(char*);
    void  processNode(char*, double);
    friend ostream& operator<< (ostream& out, const Statement& s) {
        list<IdNode>::const_iterator i = s.idList.begin();
        for ( i != s.idList.end(); i++;)
            out << *i;
        out << endl;
        return out;
    }
};

#endif 

No changes were done to useInterpreter.cpp

Thanks a lot for your time and effort =)

[Bazzy]

You need to include all the used members of std::list ( also the typedefs to iterator and const_iterator ) or modify useInterpreter.cpp
What you must do is replace all the occurrences of list<IdNode> to list ( the name of your class )
And you are declaring idList as IdNode but using it as a list

[shadow29014]

when I chaged all occurences of list<IdNode> to list
error messages says that

In function `std::ostream& operator<<(std::ostream&, const Statement&)': 
`list' has not been declared
`const_iterator' undeclared (first use this function) ot been declared 
 expected `;' before "i" 
`i' undeclared (first use this function) 
'const class IdNode' has no member named 'end' 
At global scope: 
multiple types in one declaration  

These error messages seems to be for interpreter.h

`list' has not been declared 
 missing template arguments before "i" 
 expected `;' before "i"
 i' undeclared (first use this function) 
 'class IdNode' has no member named 'end' 
 In member function `void Statement::processNode(char*, double)': 
//same error messages appear with an extra
 'class IdNode' has no member named 'push_front' 

These error messages are for interpreter.cpp


I do not understand why list is undeclared since it was declared as a class in interpreter.h and the missing template arguments before "i" .
I kind of get why "i" is not declard and needs ";" before it since "list" is undeclared.
How should I link class IdNode and class list so that class IdNode acess to 'end' and 'push_front'

Can you please elaborate more on the typedefs to iterator and const_iterator since im still bit confused on what they do.

=) Thanks So Much

[Bazzy]

You need to #include a header to use what's inside it

[shadow29014]

so i have to make a list class in a new header file and not inside interpreter.h so that the classes in interpreter.h can access the members of the list class.
Is that it?

Should the class Node and class Iterator be in the new header file with the list class or in the interpreter.h?

I tried creating a new header file but is seems that there are more error comapred to only having one header file

[Bazzy]

no
You need to #include

[shadow29014]

Thanks =) I sovled it it was a really silly mistake

I still get some error messages in interpreter.h such as:

 In function `std::ostream& operator<<(std::ostream&, const Statement&)': 
 `const_iterator' is not a member of `list' 
 expected `;' before "i" 
 `i' undeclared (first use this function) 
 'const class IdNode' has no member named 'end'  

And in interpreter.cpp:

 In member function `double Statement::findValue(char*)': 
 `iterator' is not a member of `list' 
 expected `;' before "i" 
 `i' undeclared (first use this function) 
 'class IdNode' has no member named 'end' 
 In member function `void Statement::processNode(char*, double)': 
// same error message
 'class IdNode' has no member named 'push_front' 

In order for the 'const_iterator' and 'iterator' to be a members of the list class should i declare it inside the list class? What kind of data type should they be?
Another question, how can class IdNode acess the members 'push_front' and 'end' which is in the list class

=)Thanks

[Bazzy]

Add typedef Iterator iterator; inside list
And you'll have to provide Iterator the operators ++ *(unary) -> !=
A const_iterator is an iterator that won't modify the object it's pointing to

[shadow29014]

=) Thanks a LOT
most errors are now gone but some new ones came up and i dont understand them

//for interpreter.cpp
base operand of `->' has non-pointer type `Iterator' 
//for interpreter.h
 no `operator++(int)' declared for postfix `++', trying prefix operator instead 
 no match for 'operator++' in '++i' 
 no match for 'operator*' in '*i' 
// The 'class IdNode' has no member named 'push_front'/'end'/'begin' error is still present though in both interpreter.h and interpreter.cpp 

Any idea on how to include the members of list class to IdNode? Is it possible to declare the members of the list class needed to IdNode class?
It seems that i have to overload some operators. How does it work, i only know how to overload arithmetic operators. Do they work the same way?

TY =)

[Bazzy]

1) Quoting myself: And you'll have to provide Iterator the operators ++ *(unary) -> !=

2) Use inheritance or members with the same name

[shadow29014]

Sorry i didnt quite understand. So i have to add operatiors to my iterator class for example

class Iterator
{
      IdNode *node;
      Iterator operator++
      Iterator operator*
      Iterator operator (unary)
      Iterator operator ->
      Iterator operator != 
// and not as operators ++ *(unary) -> !=
};

[Bazzy]

Iterator &operator ++
IdNode &operator *
IdNode *operator ->
bool operator !=

http://www.cplusplus.com/reference/std/iterator/ForwardIterator/
http://www.cplusplus.com/doc/tutorial/classes2/

[shadow29014]

Thanks =) its solved now
but an error occured which i do not understand
could not convert `(&i)->Iterator::operator++(0)' to `bool'
What does that mean?

I tried using inheritance and creating memers with the same name for the error messages

 'const class IdNode' has no member named 'end' /'begin' // for interpreter.h 
'class IdNode' has no member named 'push_front'/'end'/'begin' //for interpreter.cpp 

but they did not work.
On the other hand, something weired happened a header file stl_algo.h appeared which isnt part of my project file?
Any ideas why the header file appeared?

Still thanks a lot =)

[Bazzy]

I guess it's line 73 of interpreter.h you posted above for ( i != s.idList.end(); i++;) should be for ( ; i != s.idList.end(); i++) ( the first part is empty as you moved the declaration outside the for )