A recursive parser help

Question

I'm supposed to write this c++ that take in 01 and on. for example: 01010101 but not 0,1,10,011,110. Can someone help me figure out what I need to do to fix the problem. Sorry guys the code isn't working right.I pushed ctrl+k and posted the code but everything wasn't in place.

What I was trying to do is that when some enter 1 than it prints invalid. if they enter 0 it prints invalid, if the enter 10 it prints invalid, if they enter 01 it prints valid, if the enter 0101 it prints valid. So 0 always have to come first and always follow by 1. another example: 0101010101 prints valid

Thanks Seth :). I removed the links

[From seth.arnold: I removed commented-out code and indented the code to follow some kind of logical pattern. Feel free to replace this with your code if you wish, indent each line by four spaces to properly format it.]

#include <iostream>
#include<stdlib.h>  // for the exit(1) function
using namespace std;

char text[300];
char ToBeChecked;

char lexical(); //identify the characters
void SProd();
void BProd();


int main(){
    cout<<"Enter some strings only 1 and 0 (max. 300 characters"<<endl;
    cin>>text;

    ToBeChecked = lexical(); //identify the character; find the first letter and give it to ToBeChecked
    SProd();

    if(ToBeChecked == '\0')
        cout<<"Valid"<<endl;
    else
        cout<<"Invalid"<<endl;

    cin.get();
    return 0;
}

char lexical(){
    static int index = -1;   //a memory box named index with a value of -1; is static so it won't change.
                             //is -1 because -1 to 1 is 0; everything move on to next one
    index++; //update index
    return text[index]; //return the value of index
}

void SProd(){
    if(ToBeChecked != '0' ) {
        cout<<"Invalid"<<endl;
        exit(1);
    }
    else{
        BProd();
        ToBeChecked = lexical();
    }
}

void BProd(){
    if(ToBeChecked != '1')
    {
        cout<<"Invalid"<<endl;
        exit(1);
    }
    else
        SProd();

    ToBeChecked = lexical();
}

Answer 1

#include <iostream>
//#include<stdlib.h>  // for the exit(1) function
using namespace std;

char text[300];
char ToBeChecked;

char lexical(); //identify the characters
void SProd();
void BProd();


int main(){
    cout<<"Enter some strings (max. 300 characters"<<endl;
    cin>>text;

    ToBeChecked = lexical(); //identify the character; find the first letter and give it to ToBeChecked
    SProd();

    if(ToBeChecked == '\0')
        cout<<"Valid"<<endl;
        else
        cout<<"Invalid"<<endl;
    cin.get();
    return 0;
}

char lexical(){
    static int index = -1;   //a memory box named index with a value of -1; is static so it won't change.
                            //is -1 because -1 to 1 is 0; everything move on to next one
    index++; //update index
    return text[index]; //return the value of index
}

void SProd(){
    if(ToBeChecked != 'a' ) {
       BProd();
       ToBeChecked = lexical();
      }
}

void BProd(){
    if(ToBeChecked == 'b'){
        ToBeChecked = lexical();
        SProd();
    }
}

Answer 2

Have a look in Bjorn Stroustroup's book Programming Principles and Practice using c++ chapter 6-7.

You will have to write the grammar, you need to know how to:

1. Distinguish a rule from a token
2. Put one rule after another (sequencing)
3. Express alternative patterns (alternation)
4. Express a repeating pattern (repetition)
5. Recognize the grammar rule to start with

For example - you will have to have a token class:

    class Token {
public:
    char kind;        // what kind of token
    double value;     // for numbers: a value 
    Token(char ch)    // make a Token from a char
        :kind(ch), value(0) { }    
    Token(char ch, double val)     // make a Token from a char and a double
        :kind(ch), value(val) { }
};

Then Token stream class:

class Token_stream {
public: 
    Token_stream();   // make a Token_stream that reads from cin
    Token get();      // get a Token (get() is defined elsewhere)
    void putback(Token t);    // put a Token back
private:
    bool full;        // is there a Token in the buffer?
    Token buffer;     // here is where we keep a Token put back using putback()
};

Identify default constructor for Token stream:

Token_stream::Token_stream()
:full(false), buffer(0)    // no Token in buffer
{
}

Then create a putback() function, you will need that to put back the character you read from the iostream if it is of interest to you, and function who specializes in extraction of that particular character will be called:

void Token_stream::putback(Token t)
{
    if (full) throw std::runtime_error("putback() into a full buffer");
    buffer = t;       // copy t to buffer
    full = true;      // buffer is now full
}

Then in Token::get() you will have to make the rules what is important to you and what you want to include, omit or throw error:

Token Token_stream::get()
{
    if (full) {       // do we already have a Token ready?
        // remove token from buffer
        full=false;
        return buffer;
    } 

    char ch;
    cin >> ch;    // note that >> skips whitespace (space, newline, tab, etc.)

    switch (ch) {
    case '=':    // for "print"
    case 'x':    // for "quit"
    case '(': case ')': case '{': case '}': case '+': case '-': case '*': case '/': case '!':
        return Token(ch);        // let each character represent itself
        break;
    case '.':
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '9':
        {    
            cin.putback(ch);         // put digit back into the input stream
            double val;
            cin >> val;              // read a floating-point number
            return Token('8',val);   // let '8' represent "a number"
        }
        break;
    default:
        throw std::runtime_error("Bad token");

    }
}

In this version of Token_stream::get() we are interested in numbers, mathematical operators and brackets. So you will have to change that case statement to get either '1' or '0', and ignore everything else, or throw, it is up to you, I don't know what is exactly you need to do.

Then create a grammar function, you will have to establish hierarchy of functions that call one another if you want or example 1 character to be processed in front of the other. But if you only need to read sequentially, you can have only 1 function. anyway, I include 3 functions that are using calculator example where you have +,-,*,/,(,),{,}. As you see this example need to identify what it is in order to call the right function before the other one, eg - multiplication before subscription.

primary() function deals with numbers and parentheses:

    // deal with numbers and parentheses
double primary()
{
    Token t = ts.get();


    switch (t.kind) {
    case '(':    // handle '(' expression ')'
        {
            double d = expression();
            t = ts.get();
            if (t.kind != ')') throw std::runtime_error("')' expected");
            return d;
            break;
        }
    case '{':
        {
            double d = expression();
            t=ts.get();
            if (t.kind != '}') throw std::runtime_error("'}' expected");
            return d;
            break;
        }
    case '8':            // we use '8' to represent a number
        return t.value;  // return the number's value
        break;
    default:
        throw std::runtime_error("primary expected");
    }
}

term() function deals with multiplication and division:

// deal with *, /, and %
double term()
{
    double left = primary();
    Token t = ts.get();        // get the next token from token stream

    while(true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = ts.get();
            break;
        case '/':
           {    
                double d = primary();
                if (d == 0) throw std::runtime_error("divide by zero");
                left /= d; 
                t = ts.get();
                break;
            }
        default: 
            ts.putback(t);     // put t back into the token stream
            return left;
        }
    }
}

expression() deals with addition and subtraction:

double expression()
{
    double left = term();      // read and evaluate a Term
    Token t = ts.get();        // get the next token from token stream

    while(true) {    
        switch(t.kind) {
        case '+':
            left += term();    // evaluate Term and add
            t = ts.get();
            break;
        case '-':
            left -= term();    // evaluate Term and subtract
            t = ts.get();
            break;
        default: 
            ts.putback(t);     // put t back into the token stream
            return left;       // finally: no more + or -: return the answer

        }
    }
}

And finally our calling function:

int callDrill_01(void)
try
{
    std::cout << "Welcome to simple calculator." << std::endl;
    std::cout << "Please enter expressions using floating-point numbers." << std::endl;
    std::cout << "The arithmetic operators available are: + - * / ( ) { } = e(x)it." << std::endl;

    double val = 0;
    while (cin) {
        Token t = ts.get();

        if (t.kind == 'x') break; // 'q' for quit
        if (t.kind == '=') {       // ';' for "print now"
            cout << "=" << val << '\n';
        }else{
            ts.putback(t);
        }
        val = expression();
    }
    keep_window_open();
}
catch (exception& e) {
    cerr << "error: " << e.what() << '\n'; 
    keep_window_open();
    return 1;
}
catch (...) {
    cerr << "Oops: unknown exception!\n"; 
    keep_window_open();
    return 2;
}

This should give you an idea of how recursive parser are created. Your head is probably spinning. I suggest you to find that book that I mentioned and read those chapters. It will help you in the future.