// CSE468 Fall 2000, HW6 Exercise 1.3
// 
// Recursive Descent parser for the LL(1) grammar
//  S -> T$
//  T -> abV
//  V -> UV | lambda
//  U -> aW
//  W -> Ubb | b
#include<iostream.h>
#include<stdlib.h>

char curr_ch;

void get_ch(); // Gets the next character in the string
void err(); // Exits the program

void S(); // Starting symbol
void T(); // T production
void U(); // U production
void V(); // V production
void W(); // W production

int main()
{
        cout << "Enter a string: ";
        get_ch();
        S();
        cout << "\nThe above string was accepted.\n";

        exit(1);
}

void get_ch()
{
        if (cin >> curr_ch) cout << curr_ch;
}       

void err()
{
        cout << " <-- Error processing symbol\n\nThe string is not in the language of expressions.\n";
        exit(0);
}

void S() // S -> T$
{
        T();  // First process T symbol

        if(curr_ch != '$') // Then consume the $
                err();     // If the symbol is not a $, the string is invalid
}

void T() // T -> abV
{

        if(curr_ch == 'a') // Consume the a
        {
                get_ch();

                if(curr_ch == 'b')  // Consume the b
                {
                        get_ch();
                        V();  // Process V symbol
                }
                else err();
        }
        else err();
}

void V()
{
        if(curr_ch == 'a') // If the current character is an a, we need to follow the production 
        {                  // V -> UV but we have already consumed the a so the production becomes
                get_ch();  // V -> aWV -> WV.  
                W();
                V();
        }
        else if(curr_ch != '$') err(); // Otherwise the current character is a $ so we apply the lambda production
}

void U() // U -> aW
{
        if(curr_ch == 'a') // First consume the a
        {
                get_ch();
                W(); // Then process the W symbol
        }
        else err();
}

void W() // W -> Ubb | b
{
        if(curr_ch == 'a')  // If the current character is an a then the W production has to be W -> Ubb.  
        {                   // But since we have already consumed the a we need to change the production to
                get_ch();   // W -> aWbb -> Wbb.
                W();
                if(curr_ch == 'b')
                {
                        get_ch();
                        if(curr_ch == 'b')
                        {
                                get_ch();
                        } else err();
                } else err();
        }
        else if(curr_ch == 'b') // Otherwise, if the current character is an a, then the W production has to
        {                       // be W -> b.  In this case, just consume the b
                get_ch();
        }
        else err();
}