main.cpp

Code for top down parser in C++

//---------------------------------------------------------------------------
//
//  Top-down parser with backtracking for arbitrary context-free grammars
//  Dmitry Brant, Spr 2004
//
//-----------

#include <vcl.h>
#pragma hdrstop

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <stdexcept.h>
#include "grammar.h"
#include "treeform.h"

using std::runtime_error;

bool Traverse(char* input);
unsigned int inputLength, verbosity=0;
Grammar* g;
//---------------------------------------------------------------------------


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

    g = new Grammar();
    char* inputStr = new char[32768]; //nice, big buffer for input
    char* grammarFile = "grammar.txt";
    memset(inputStr, 0, 32768);
    inputStr[0] = 0;

    try{
        bool doEliminateEpsilon=true, doEliminateUnit=true, doEliminateLeftRecursion=true;

        //what's this? do we have a command line argument?
        if(argc > 1){
            for(int i=1; i<argc; i++){
                if(LowerCase(String(argv[i])) == "-v"){
                    if(i<(argc-1)){ verbosity = atoi(argv[i+1]); i++; }
                }
                else if(LowerCase(String(argv[i])) == "-g"){
                    if(i<(argc-1)){ grammarFile = argv[i+1]; i++; }
                }
                else if(LowerCase(String(argv[i])) == "-ne"){
                    doEliminateEpsilon = false;
                }
                else if(LowerCase(String(argv[i])) == "-nu"){
                    doEliminateUnit = false;
                }
                else if(LowerCase(String(argv[i])) == "-nr"){
                    doEliminateLeftRecursion = false;
                }
                else if(LowerCase(String(argv[i])) == "-na"){
                    doEliminateEpsilon = false;
                    doEliminateUnit = false;
                    doEliminateLeftRecursion = false;
                }
                else{
                    FILE* f = fopen(argv[i], "rb");
                    if(!f) throw runtime_error(("could not open " + String(argv[1]) + " for input").c_str());
                    unsigned int bytesread = fread(inputStr, 1, 32768, f);
                    fclose(f);
                    if(!bytesread) throw runtime_error(("could not read from file " + String(argv[1])).c_str());
                    inputLength = bytesread;
                    printf("Input loaded successfully.\n");
                }
            }
        }

        g->LoadFromFile(grammarFile);
        printf("\nGrammar loaded successfully.\n");

        if(doEliminateEpsilon){
            g->EliminateEpsilonProductions();
            g->SaveToFile("grammar_after_epsilon.txt");
            printf("Epsilon productions eliminated.\n");
        }

        if(doEliminateUnit){
            g->EliminateUnitProductions();
            g->SaveToFile("grammar_after_unit.txt");
            printf("Unit productions eliminated.\n");
        }

        if(doEliminateLeftRecursion){
            g->EliminateLeftRecursion();
            g->SaveToFile("grammar_after_left_recursion.txt");
            printf("Left recursion eliminated.\n");
        }
        
        if(!inputStr[0]){
            printf("\nPlease enter your input string:\n");
            gets(inputStr);
            inputLength = strlen(inputStr);
        }

        if(!inputLength) throw runtime_error("Empty input string");

        //collapse whitespace in string
        int ptr=0, newPtr=0;
        do{
            if((inputStr[ptr] > ' ') || (inputStr[ptr] == 0)){
                inputStr[newPtr++] = inputStr[ptr];
            }
        }while(inputStr[ptr++] != 0);

        //check this out:
        if(Traverse(inputStr)){
            printf("\nString parsed successfully!\n");
        }else{
            throw runtime_error("failed to parse string");
        }

    }catch(exception &e){
        printf("\nParsing failed: %s\n", e.what());
    }catch(...){
        printf("\nUnknown exception.\n");
    }

    delete g;
    delete [] inputStr;
    return 0;
}
//---------------------------------------------------------------------------



void printNodes(TList* nodes, ParseNode* currentNode){
    for(int i=0; i<nodes->Count; i++){
        if(((ParseNode*)nodes->Items[i]) == currentNode){
            printf("[");
            printf(((ParseNode*)nodes->Items[i])->str.c_str());
            printf("]");
        }else
        printf(((ParseNode*)nodes->Items[i])->str.c_str());
        int idx = ((ParseNode*)nodes->Items[i])->index;
        printf(("<" + String(idx) + ">").c_str());
    }
    printf("\n");
}
//---------------------------------------------------------------------------

void printflevel(int level, char* str){
    for(int i=0; i<level; i++) printf("  ");
    printf(str);
}
//---------------------------------------------------------------------------

void DeleteNodeChildren(TList* nodes, ParseNode* node){
    //delete any other nodes whose parent is this node
    for(int i=0; i<nodes->Count; i++){
        ParseNode* otherNode = (ParseNode*)nodes->Items[i];
        if(otherNode->parent == node){
            if(!otherNode->terminal) DeleteNodeChildren(nodes, otherNode);
            int pos = nodes->IndexOf(otherNode);
            delete otherNode;
            nodes->Delete(pos);
            i--;
        }
    }
}
//-----------------------------------------

bool MatchNodeTrace(TList* nodes, char* input){
    int inputPtr=0;
    bool equal = true;
    //delete any other nodes whose parent is this node
    for(int i=0; i<nodes->Count; i++){
        ParseNode* node = (ParseNode*)nodes->Items[i];
        if(node->terminal && (node->str != "")){
            if(node->str != String(input[inputPtr])){
                equal = false; break;
            }
            inputPtr++;
        }
    }
    return equal;
}
//-----------------------------------------



//The traversal procedure:
//an ingenious linked-list design, without recursion.
//Algorithm:
//Wave hands, and sing:
//   "Backtrack, backtrack, search, search, search,
//      "Search, search, search, and backtrack some more!"

bool Traverse(char* input){

    RewriteRuleGroup* activeGroup;
    if(!g->ruleGroups->Count) throw runtime_error("empty grammar");
    activeGroup = (RewriteRuleGroup*)g->ruleGroups->Items[0];
    if(verbosity > 0) printf(("\nAssuming start symbol " + activeGroup->nonTerminal + "\n").c_str());

    //create parse node list
    TList* nodes = new TList();
    try{
        //set up first node
        ParseNode* node = new ParseNode();
        nodes->Add(node);
        node->myGroup = activeGroup;
        node->terminal = false;
        node->currentRuleIndex = 0;
        node->str = activeGroup->nonTerminal;

        int currentNodeIndex = 0;
        int inputPtr = 0;
        bool match;

        while(1){

            //find the next unmarked node
            node = NULL;
            for(int i=0; i<nodes->Count; i++){
                ParseNode* newNode = (ParseNode*)nodes->Items[i];
                if(newNode->index == -1){ node = newNode; break; }
            }
            if(!node){
                //are we at the end of the string? [I hope?]
                if(input[inputPtr] == 0){

                    //there's still a small chance that the terminal trace of the nodes
                    //does not match output
                    if(!MatchNodeTrace(nodes, input)){
                        goto backtrack;
                    }

                    //we're done!!!
                    if(verbosity > 0) printf("Success!\n");
                    //show the parse tree
                    TfrmTree* theForm = new TfrmTree(NULL);
                    theForm->FillTree(nodes, (ParseNode*)nodes->Items[0], NULL);
                    theForm->TreeView1->FullExpand();
                    theForm->ShowModal();
                    delete theForm;
                    return true;

                }else{

                    //This condition occurs when the algorithm is "successful"
                    //all the way back to the start symbol, and yet there's still
                    //input remaining. This means only one thing:

                    //Backtrack!!!!!!
                    //My apologies, Father Dijkstra:
                    goto backtrack;

                }
            }

            if(!node->terminal){
                //if the node is a nonterminal, roll it out
                if(verbosity > 1) printflevel(node->level, ("Encountered nonterminal " + node->str + "\n").c_str());
                RewriteRule* currentRule = (RewriteRule*)node->myGroup->rules->Items[node->currentRuleIndex];

                if(verbosity > 1){ printflevel(node->level, ""); printNodes(nodes, node); }

                //this rule can only be used once. increment the rule used index
                node->currentRuleIndex++;

                if(verbosity > 0) printflevel(node->level, ("Rolling out nonterminal " + node->str + " -> ").c_str());

                //start inserting nodes directly after the current node index
                int insertPoint=currentNodeIndex+1;
                for(int i=0; i<currentRule->units->Count; i++){
                    RewriteUnit* unit = (RewriteUnit*)currentRule->units->Items[i];
                    ParseNode* newNode = new ParseNode();
                    newNode->index = -1;
                    newNode->parent = node;
                    newNode->level = node->level+1;
                    nodes->Insert(insertPoint++, newNode);
                    newNode->terminal = unit->terminal;
                    newNode->str = unit->str;
                    if(!newNode->terminal){
                        //find the group of this nonterminal
                        newNode->myGroup = g->getGroup(newNode->str);
                        newNode->currentRuleIndex = 0;
                    }
                    if(verbosity > 0){ if(newNode->str=="") printf("