[Eclipse Reborn]

I'm looking into parsing some basic text. I had a quick glance Martyn's Fundamentals of Parsing, it doesn't seem to be what I want.

Just some basic functions, Ex:

MsgBox("text", "caption")

And that would create a simple MessageBoxA call, I have no idea where to start, but if Martyn's tutorial will help me achieve this, then tell me.

This post has been edited by Eclipse Reborn: 24 July 2010 - 10:52 PM

[David W]

The idea of splitting a string of text up into words (tokens) is simple ... but can take a fair bit of coding ...

If you would like to see an example in C, look at the split.h tutorial here at DIC ... or this link posted just awhile ago ...

http://www.dreaminco...ost__p__1075186

Or for splitting text up in C++ ...

http://developers-he...index.php/topic,106.msg576.html#msg576

Using stringstream objects in C++ can be a very simple and easy code ... if 'whitespaces' are the delimiters between 'words'.

Something like this ...

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector> // or list or ...

using namespace std;

int main()
{
    vector< string > v; // get a vector to hold your words

    ifstream fin( "yourDataTextFileName.txt" );

    string line; // to hold each line you read from the file
    while( getline( fin, line ) )
    {
        istringstream iss( line ); // construct iss object
        string word;
        while( iss >> word ) // now get words on line into vector
            v.push_back( word );
    }

    // show all the words, here 'inside single quote delimiters'
    for( size_t i = 0; i < v.size(); ++i )
        cout << "'" << v[i] << "'" << endl;
}

This post has been edited by David W: 25 July 2010 - 04:02 AM

[Anarion]

For a basic approach, you can use the find family of functions in C++ Strings. It's easy. Look at [ this snippet ] for example.

The basic rule is like this:
start from beginning of text, check characters one by one. If it is not a delimiter, add this to the temporary string and continue the loop, if it is a delimiter, then what we have in temporary string is separated part and can be operated on as you want. This is continued till end of text is reached.

The above approach is the easiest I know which works well for me most of the time(and also supports paranthesis and quotes etc). Hope that helped you.

[Eclipse Reborn]

Thanks for the example, really appreciate it.

But I'm still stumped on how I would parse basic functions. I could split the function name up by the first '(', and the arguments by either a command or a comma & whitespace. Then end the arguments with the closing ')', and the line with a semi-colon.

I just don't have a good theory on how to translate this, I'll probably have the function identifier in a string, and the arguments in a vector. Switch the function id, and check the argument count, to see if you have the right amount.

[NickDMax]

The first step in building a parser is determining what you will be parsing, i.e. defining a grammar. The small example that you gave is hardly enough to extrapolate a full grammar from but we do have a couple of things to work with.

The first thing I see is an identifier, Identifiers are usually a letter optionally followed by several alphanumeric chars.

Identifier := alpha {alpha | digit}

A string is quotation mark, followed by a series of char that are not the quotation mark, and then the quotation mark

string := '"' char~'"' '"'

next you have a function call... though lets step back and think a little abstractly, a function call might have an identifier in it rather than just a string (though since we don't know what assignment looks like maybe not)

Parameter := Identifier | string

Function Call := Identifier '(' Parameter {',' Parameter } ')'

Defining your grammar makes writing a parser much easier.

once you have sketched out your grammar you have two alternatives, you can hand code your parser as a finite state machine (or machines), OR you use a parser generator to generate one for you from the grammar. There are hundreds of parser generators out there - beyond those listed in the wikipedia article you will also find them littering just about every open source project host (sourceforge, github, google code, etc.) -- basically everyone and their grandmother have written a parser generator. However the big ones are:

YACC (yet another compiler compiler) -- many language compilers and interpreters have been written using LEX/YACC
BISON -- Well this is kind of a joke I guess, BISON is kind of the next evolution of YACC... get it?
ANTLR -- It runs on Java but it can generate a C or C++ parser, the nice thing about this is that it is very popular at the moment and you can find a good number of blogs about how to use it, however most of them are working with Java not C/C++.

Boost::Spirit -- this is not really designed for writing complex languages, but if you just need to extract some data for a format, or maybe implement a small domain specific language (even something like JSON or XML) then this is a good way to embed the parser generator right into your C++ code. I recently did a blog about it parsing name value pairs.

define what it is you want to parse, THEN we can help you with a parser.

[NickDMax]

Here is a *simple* example of parsing a function call with strings as arguments. This is probably very buggy (I already found one bug and had to fix before posting) as this is a very "informal" way to make a parser, you probably want to go with a more formal approach.

This uses templates.. but don't be alarmed you could ditch the template and just replace the word "Iterator" with "string::iterator" -- but with the template you could technically use other containers such as a vector<char> or list<char>... but who would want to?

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <cctype>

using namespace std;


template<typename Iterator>
bool parseIdentifier(Iterator& begin, const Iterator& end, string& result) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
    if(isalpha(*begin) && begin != end) {
        oss << *begin;
        begin++;
        while(isalnum(*begin) && begin != end) {
            oss << *begin++;
        }
        //begin should be the first non-match char...
        result = oss.str();
        return true;
    } else {
        begin = mark;
        result = string("");
        return false;
    }
}

template<typename Iterator>
bool parseLiteral(Iterator& begin, const Iterator& end, char ch) {
    if (begin != end && *begin == ch) { begin++; return true; }
    return false;
}

template<typename Iterator>
bool parseString(Iterator& begin, const  Iterator& end, string& result) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
    if (parseLiteral(begin, end, '\"')) { 
        while(begin != end && *begin != '\"') {
            oss << *begin;
            begin++;
        }
        if(parseLiteral(begin, end, '\"')) {
            //*begin should be the char after closing quotes
            result = oss.str();
            return true;
        }
    }
    result = string("");
    begin = mark; //reset our begin iterator
    return false;
}

template<typename Iterator>
bool parseFunctionCall(Iterator& begin, const Iterator& end, string& cmd, vector<string>& args) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    if (parseIdentifier(begin, end, cmd)) {
        if(parseLiteral(begin, end, '(')) {
            if(begin != end) {
                string arg;
                if(parseString(begin, end, arg)) {
                    args.push_back(arg);
                    while(isspace(*begin) && begin != end) { begin++; }
                    while(parseLiteral(begin, end, ',')) {
                        if(parseString(begin, end, arg)) {
                            args.push_back(arg);
                            while(isspace(*begin) && begin != end) { begin++; }
                        } else {
                            //error a comma not followed by a string!
                            begin = mark;
                            cmd = "";
                            args = vector<string>();
                            return false;
                        }
                    }
                    
                } 
            }
            while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
            if(parseLiteral(begin, end, ')')) {
                //success!
                return true;
            }
        }
    }
    cmd = string("");
    args = vector<string>();
    begin = mark; //reset our begin iterator
    return false;
}


//utility function just to make it easy to display what got parsed
void displayParse(string line) {
    string cmd;
    vector<string> args;
    string::iterator iter = line.begin(); // we want an iterator we can use as a variable to keep track of where we are in the string...
    if(parseFunctionCall(iter, line.end(), cmd, args)) {
        cout << "line: " << line << endl;
        cout << "Command: " << cmd << endl;
        for(int i = 0; i < args.size(); ++i) {
            cout << "args[" << i << "] = \"" << args[i] << "\"" << endl;
        }    
    } else {
        cout << "ERROR parsing: " << line << endl;
    }
    cout << "--------------------------------------------\n" << endl;
}




int main() {
    vector<string> samples;
    samples.push_back("MsgBox(\"Hello\", \" World\")");
    samples.push_back("voidFunction()");
    samples.push_back("longFuntionName124(\"This\",\"is\",\"a\",\"test of a really long function!!!\")");
    samples.push_back("nullargument1(,)");
    samples.push_back("nullargument1(\"no next argument\",)");
    samples.push_back("1invalidIdentfier()");
    
    for_each(samples.begin(), samples.end(), displayParse);
    
    return 0;
}

[Eclipse Reborn]

Yeah thanks a lot for the example, I appreciate it. I still don't have a decent theory on how I would parse strings and integers as arguments.

And I don't know what you mean by yours is informal.

This post has been edited by Eclipse Reborn: 26 July 2010 - 12:49 AM

[David W]

Eclipse Reborn, on 26 July 2010 - 01:49 AM, said:

... I still don't have a decent theory on how I would parse strings and integers as arguments. ...

As already hinted, you may need to establish a very well defined dictionary of all the possible objects/object_types that may occur on any line ...

It could help us help you if you provided samples of the text you wish to parse ... and what it is that you wish to extract from a line ...

For example ... if one was wanting to be able to read a math line and then do the operations on that line ?

x := 5; y := 10; z := x + y; print "The sum of", x, "+", y, "is", z;

[Eclipse Reborn]

It's just going to be basic function calls.

Ex:

DrawText("some text", 10, 20, 0);
DrawLine(10, 10, 600, 400);

Some functions may only be integers, and some strings, and some a combination of both.

[NickDMax]

What did I mean by "informal" -- well parsing is very well understood by the CS community. The theory has been long established and papers and text-books have been in print since the dawn of computer science. Parsing has a mountain of solid theory behind it. So much theory in fact that humans rarely write parsers by hand anymore, parsers have been formalized and understood well enough that we have programs that write them for us. These parsers use finite state machines and push down automata and have goofy names like LL(1), LL(2), LL(*), LR, LALR etc. and their strengths, limitations, and capabilities are well understood. (note that my "informal" approach does not have a lexer... it jumps right into parsing, i.e. a "formal" implementation would be much more robust).

The parser I wrote above is basically a Recursive decent parser but it is hand coded and has a few problems ( like it can not tell you why you have an error in the input, it just fails ).

A recursive decent parser starts by trying to recognize the largest part, and working its way down to the smallest, it does back tracking to (try to parse something, if you have a failer reset your marker/pointer and try to parse the next possible selection.)

So for my parser below (the latest version of the one above) it starts by trying to recognize a function call:

function call := identifier '(' { parameterList } ')'

first it checks for an identifier:

identifier := alpha { *alphanum }

if it finds one of those, it looks for a literal: '('

if it finds one of those, it looks for an optional parameter list:

parameterList := parameter {',' parameter}

so it begins by looking for a parameter:

parameter := identifier | string | integer

so first it looks for an identifier, if it does not find one it rewinds and tried a string:

string := '"' *{ ('\' ('a'|'b'|'f'|'n'|'r'|'t'|'"'|singlequote|'\'|'?') ) | char~'"' } '"'

If it does not find a string, it rewinds and looks for an integer (note I did not check "bounds" for the integer so it will parse numbers larger than an int)

integer := { '-' } digit *{ digit }

hopefully it found one of these, if not parameterList fails, else it will look for a optional "next parameter" (a ',' followed by another parameter).

when it has the parameter list it will look for the last literal ')' marking a complete parse...

In this new version I introduced the concept of a Token which can help understand the kind of token found (was that an identifier, a string, or a parameter):

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <cctype>

using namespace std;

//use a token type to abstract the return results of a parser...
struct Token {
    enum Types {
        Error,
        Unknown,
        Identifier,
        String,
        Integer,
        Keyword,
    };
    Types type;
    string token;
};
    
template<typename Iterator>
bool parseIdentifier(Iterator& begin, const Iterator& end, Token& result) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
    if(isalpha(*begin) && begin != end) {
        oss << *begin;
        begin++;
        while(isalnum(*begin) && begin != end) {
            oss << *begin++;
        }
        //begin should be the first non-match char...
        result.type = Token::Identifier;
        result.token = oss.str();
        return true;
    } else {
        begin = mark;
        result.type = Token::Error;
        result.token = string("");
        return false;
    }
}

template<typename Iterator>
bool parseLiteral(Iterator& begin, const Iterator& end, char ch) {
    if (begin != end && *begin == ch) { begin++; return true; }
    return false;
}

//TODO: add in hex/octal parsers
template<typename Iterator>
bool parseEscape(Iterator& begin, const Iterator& end, char& ch) {
    Iterator mark = begin; //save our begining incase we fail
    if(parseLiteral(begin, end, '\\')) {
        if(begin!=end) {
            switch(*begin) {
                case 'a': ch = '\a'; begin++; return true;
                case 'b': ch = '\b'; begin++; return true;
                case 'f': ch = '\f'; begin++; return true;
                case 'n': ch = '\n'; begin++; return true;
                case 'r': ch = '\r'; begin++; return true;
                case 't': ch = '\t'; begin++; return true;
                case '\'': ch = '\''; begin++; return true;
                case '\"': ch = '\"'; begin++; return true;
                case '\\': ch = '\\'; begin++; return true;
                case '?': ch = '?'; begin++; return true;
                default: break;
            } 
        }
    }
    begin = mark;
    return false;
}


template<typename Iterator>
bool parseString(Iterator& begin, const  Iterator& end, Token& result) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
    if (parseLiteral(begin, end, '\"')) { 
        while(begin != end && *begin != '\"') {
            char ch;
            if(parseEscape(begin, end, ch)) {
                oss << ch;
            } else {
                oss << *begin;
                begin++;
            }
        }
        if(parseLiteral(begin, end, '\"')) {
            //*begin should be the char after closing quotes
            result.type = Token::String;
            result.token = oss.str();
            return true;
        }
    }
    result.type = Token::Error;
    result.token = string("");
    begin = mark; //reset our begin iterator
    return false;
}

template<typename Iterator>
bool parseInteger(Iterator& begin, const  Iterator& end, Token& result) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
    if (*begin == '-' || *begin == '+') { 
        oss << *begin;
        begin++;
    }
    if(begin!=end && isdigit(*begin)) {
        while(begin!=end && isdigit(*begin)) {
            oss << *begin;
            begin++;
        }
        result.type = Token::Integer;
        result.token = oss.str();
        return true;
    }
    result.type = Token::Error;
    result.token = string("");
    begin = mark; //reset our begin iterator
    return false;
}

template<typename Iterator>
bool parseArgument(Iterator& begin, const  Iterator& end, Token& result) {
    return parseIdentifier(begin, end, result) || 
           parseString(begin, end, result) ||
           parseInteger(begin, end, result);
}

template<typename Iterator>
bool parseArgumentList(Iterator& begin, const  Iterator& end, vector<Token>& result) {
    Iterator mark = begin;
    if(begin != end) {
        Token arg;
        if(parseArgument(begin, end, arg)) {
            result.push_back(arg);
            while(isspace(*begin) && begin != end) { begin++; }
            while(parseLiteral(begin, end, ',')) {
                if(parseArgument(begin, end, arg)) {
                    result.push_back(arg);
                    while(isspace(*begin) && begin != end) { begin++; }
                } else {
                    //error a comma not followed by a string!
                    begin = mark;
                    result = vector<Token>();
                    return false;
                }
            }
            
        } 
    }
    return true;
}



template<typename Iterator>
bool parseFunctionCall(Iterator& begin, const Iterator& end, Token& cmd, vector<Token>& args) {
    stringstream oss;
    Iterator mark = begin; //save our begining incase we fail
    if (parseIdentifier(begin, end, cmd)) {
        if(parseLiteral(begin, end, '(')) {
            if(!parseArgumentList(begin, end, args)) {
                    begin = mark;
                    cmd.type = Token::Error;
                    cmd.token="";
                    return false;            
            }
            while(isspace(*begin) && begin != end) { begin++; } //eat whitespace
            if(parseLiteral(begin, end, ')')) {
                //success!
                return true;
            }
        }
    }
    cmd.token = "";
    cmd.type = Token::Error;
    args = vector<Token>();
    begin = mark; //reset our begin iterator
    return false;
}


//utility function just to make it easy to display what got parsed
void displayParse(string line) {
    Token cmd;
    vector<Token> args;
    string::iterator iter = line.begin(); // we want an iterator we can use as a variable to keep track of where we are in the string...

    cout << "line: " << line << endl;
    while (iter!=line.end() && parseFunctionCall(iter, line.end(), cmd, args)) {
        cout << "Command: " << cmd.token << endl;
        for(int i = 0; i < args.size(); ++i) {
            cout << "args[" << i << "] = ";
            if (args[i].type == Token::String) { 
                cout << "\"" << args[i].token << "\"" << endl;
            } else if (args[i].type == Token::Integer){
                cout << args[i].token << endl;
            } else {
                cout << args[i].token << "_" << args[i].type << endl;
            }          
        }
        
    }
    cout << "--------------------------------------------\n" << endl;
}




int main() {
    vector<string> samples;
    samples.push_back("MsgBox(\"Hello\", \" World\")");
    samples.push_back("voidFunction()");
    samples.push_back("longFuntionName124(\"This\",\"is\",\"a\",\"test of a really long function!!!\")");
    samples.push_back("nullargument1(,)");
    samples.push_back("nullargument1(\"no next argument\",)");
    samples.push_back("1invalidIdentfier()");
    samples.push_back("tryEscaping(\"\\\"This is in quotes\\\"\", \"line1\\nline2\", \"This\\t\\ttabs\")");
    samples.push_back("tryEscaping(\"Testing\\x10Hex\")");
    samples.push_back("PassIdentifier( someVar, \"a string\")");
    samples.push_back("integerArguments(123, -123)");
    samples.push_back("mixItUp123OK(\"Parse\n\t\t\tThis\", -9876543210, allright, awayWeGo, \")(*&^%$#@!`~\")");
    samples.push_back("functionOne(1) Function2(2)");
    for_each(samples.begin(), samples.end(), displayParse);
    
    return 0;
}

Unfortunately one has to code a recursive decent parser from the bottom up i.e. start with the most simple pices and work your way up to the larger ones:

struct Token -- identifies a Token (I never actually used "Unknown")
bool parseIdentifier(Iterator& begin, const Iterator& end, Token& result)
-- Parses an identifier or will return an Error token.
-- All of the parse functions take a begin and end Iterator and some kind or result, the begin iterator will be set to the next char after a successful parse so for example:
"functionCall()" -- after the token "functionCall" has been parsed the 'begin' iterator will point to '(' all of the parse functions have this behavior.
-- The 'result' will be filled out upon successful parsing, most functions will return an Error if uncesseful but some don't return a token (either a char or a vector).
-- The return result will indicate success, true == successful parse, false indicates an unsuccessful parse.

bool parseLiteral(Iterator& begin, const Iterator& end, char ch)
-- looks for the char in ch, if it is found then begin is advanced, note this one does not return anyother value as the caller should know what char it passed in.

bool parseEscape(Iterator& begin, const Iterator& end, char& ch)
-- parse an escape sequence (used in strings).
-- if successful then ch will contain the escaped char.

bool parseString(Iterator& begin, const Iterator& end, Token& result)
-- does what its name implies.

bool parseInteger(Iterator& begin, const Iterator& end, Token& result)
-- Parses an integer, BUT the resulting token is still in string form and must be converted to an integer by whatever is using the value.

bool parseArgument(Iterator& begin, const Iterator& end, Token& result)
-- Parses either an identifier, or a string, or an integer (whichever parses correctly first).
-- This demonstrates the "Recursive decent parser" part very well, a smarter parser could have looked at the first char (either an alpha, a '"', or a digit) and determined which kind of token could possibly follow.

bool parseArgumentList(Iterator& begin, const Iterator& end, vector<Token>& result)
-- Parse a list of arguments.
-- the results get stored in a vector, Upon failure the begin iterator is reset even if we successfully parsed 20 arguments before an error...

bool parseFunctionCall(Iterator& begin, const Iterator& end, Token& cmd, vector<Token>& args)
-- Uses the functions above to parse a function call, the result is a token with the function name "cmd" and a list of argument "args"

void displayParse(string line)
-- utility function to parse and display the results of a line of text.

[Eclipse Reborn]

Thanks I haven't read your example yet, but I really appreciate the help.

[ishkabible]

if you want to call functions from text your looking at indexing function by name then braking apart what a function call is (this is the parsing part). if you make something that would brake up text into tokens (i call it a tokenizer but that's kinda unofficial) you could look at it in easier to read parts. for example take "add(10,10)" <add> <(> <10> <,> <10> <)> are the tokens it would brake up into. once you have that you would look at the parts, first look at "add" check to see if it is a function(this is the part where you would need the function pointers indexed by text), if so recorded something that says what function to call. next you would see the "(" if you don't see this then there is an error but we will say we saw it so we will keep going. next you would see 10 you would then store this in something that set this as an argument for "add". next you would see the "," this is like the "(" we see so we keep going. then you would see another "10" you would store this as an argument somehow for "add" then finely you would see ")" this can be used a bunch of different ways it could simply mean stop parsing or you might store it as an end of arguments flag where ever you where storing the other arguments. i know this is kinda vague as i haven't given any source to give you an example but as always feel free to ask, i hoped this helped.