Skip to main content
gamedev.net
🔒 Locked

Problems with parsing

Started by webwraith Jun 5, 2006 at 1:38 PM 26 replies 5.1k views
Original Post
webwraith
webwraith
Hi, I was wondering how best to parse text files in C++. I'm doing this for my game engine, so the scripts will basically sit "on top" of that. I wanted to use a set of functions in the script that directly call certain functions in the engine, but give the script-writer the ability to write their own functions, along with any variables they may need. I can handle the variables fine, but what I want to know is how to get my parser to handle;

if(((2*AVariable)/74)>20)
and treat it the same way as

if ( ( (2* AVariable)/ 74)  >20)
Kylotan
Kylotan
Do you mean, how to evaluate that expression appropriately? (As opposed to just knowing where to insert whitespace!) You may want to look up Backus-Naur form, and recursive descent parsers, or parser generators (Lex and Yacc are the traditional starting points, though far from being the easiest to work with). Alternatively, consider using an existing scripting language for this; they've done most of the hard work for you.
hplus0603
hplus0603
I would recommend using a scripting language that someone else already created for you. It's going to make you get to your goal much, much faster.

Unless your goal is to learn how to write a script language runtime and parser, of course :-) Typically, you parse the file by reading one token at a time, and making the appropriate decision based on the current context/state. You will build a tree representation of the entire program, and then execute that tree in some form to execute your script.

Generally, the "getToken()" function will skip leading whitespace before it isolates and returns the next token in the input data. A token is something like "if" or "(" or "/" or "74".
enum Bool { True, False, FileNotFound };
webwraith
webwraith
What I'm getting at is I don't know how to get the parser to recognise two tokens that AREN'T separated by whitespace.

And, yeah, this is a bit of a learning thing for me[lol]
Kylotan
Kylotan
Quote:
Original post by webwraith
What I'm getting at is I don't know how to get the parser to recognise two tokens that AREN'T separated by whitespace.


Put very simply, you keep reading the token until you find something that isn't part of the token, then you put that bit back. If you have a choice, you try each potential token until you find one that matches.

webwraith
webwraith
So, one char at a time, then... OK, thanks, I'll try it and come back with the results
webwraith
webwraith
OK, here is the start of my scanner class, but I just keep getting back that it doesn't recognise the token. maybe I'm blind, but I can't see what's wrong with the code, does someone mind looking over the listing for me?

Scanner:
enum TOKEN_TYPE{NUM,IDENT,COND,STRING};struct TokenStruct{    char delimiter;    std::string alpha;    std::string num;    std::string other;};class Scanner{    protected:        char m_delimiter;//defines the end of a line        std::string m_alpha;//letters in both Upper and Lower case        std::string m_num;//every numeric digit        std::string m_other;//everything else        TOKEN_TYPE token_type;//stores the type of token    public:        Scanner():m_delimiter(';'),m_alpha("_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"),m_num("0123456789"),m_other("#\"=+-*/.:!<>,'{}[]()"){}        Scanner(TokenStruct tokstr):m_delimiter(tokstr.delimiter),m_alpha(tokstr.alpha),m_num(tokstr.num),m_other(tokstr.other){}        ~Scanner(){}        //Note: the file pointer given to GetToken() must already be open.        std::string GetToken(std::ifstream& fin)        {            std::string token="";            char tempchar;            bool decimalpoint=false,whtspc=true;//decimalpoint is used to check if the token already has a decimal point. if it has, then the token is returned without the second decimal            //test if the file is actually open            if(!(fin.is_open()))                return std::string("file not open");            //get rid of whitespace            //do{                tempchar = fin.get();            //}while(isspace(tempchar)==0);            if(strcmp(&tempchar,""))                tempchar = fin.get();            //set token type            if(m_alpha.find(tempchar,0)!=std::string::npos)            {                token_type=IDENT;                token.append((const char*)tempchar);            }            else if(m_num.find(tempchar,0)!=std::string::npos)            {                token_type=NUM;            }            else if(m_other.find(tempchar,0)!=std::string::npos)            {                if(!strcmp((const char*)tempchar,"\""))                    token_type=STRING;                else                    token_type=COND;            }            else return std::string("token type not recognised");            return token;            //time to start reading in the token        }        std::vector<std::string> TokenizeLine(std::ifstream& fin)        {            std::vector<std::string> ret_vec;            std::string temp;            size_t line_size;            while(!(temp[0]==m_delimiter))            {                temp=GetToken(fin);            }            return ret_vec;        }};


main.cpp:
#include "tokeniser.h"#include <fstream>using namespace std;int main(){    Scanner tokens;    ifstream fin;    fin.open("test.txt");    std::string myString;    std::vector<std::string> myVector;    myString=tokens.GetToken(fin);    //myVector=tokens.TokenizeLine(fin);    std::cout << myString << std::endl;    fin.close();}


test.txt:
a; a;	a;a;abc;ab_;ab_c;a1;a1_;a_1;a,b;_a;_a_b;_1;2;234;2.3;2.34;23.4;23.45;23.;"The (quick) br0wn f0x j&umped over_the_lazy_dog";(;::;==;<=;>=;!=;++;--;=!;<";>%;:[;+-;-+;#hell, we made it!


the
 return token


at the end of the Scanner::GetToken() method is just there until I know that this section is working

[Edited by - webwraith on July 4, 2006 3:26:34 PM]
Kylotan
Kylotan
I'm pretty sure that strcpy is not what you intended there. You shouldn't be using strcpy on std::strings anyway.
webwraith
webwraith
That might be it, I'll change that now [embarrass]. That was supposed to be a strcmp(), because tempchar is of type char, and the only times I'm using it is when I'm testing against other chars.


Nope, just changed it, and still got the bad token response

[Edited by - webwraith on July 4, 2006 9:55:02 PM]
webwraith
webwraith
Right, I tried this with both MinGW and DJGPP, and keep getting segmentation violations:
#include <stdio.h>#include <conio.h>#include <ctype.h>#include <string.h>#ifndef NDEBUG    #define debug strcpy(argv[1],"errorlog.txt")#else    #define debug#endiftypedef enum{ident=0,num,string,punct,eof} type;/*    standard structure*/typedef struct{    type ttype;    char* value;    int size;} tok_type;int main(int argc,char** argv){    char            tempchar;    char*           token;    type            ttype;    int             size=0;    FILE            *in,*out;    debug;//used to set debug info    if(argc<2)        return 1;    else if(!(in = fopen(argv[1],"rt")))        return 1;    else if(!(out = fopen("out.tmp","wt+")))    {        fclose(in);        return 1;    }    while(!(feof(in)))    {        tempchar = fgetc(in);        if(isspace(tempchar))            continue;        if(size==0)        {            strcat(token,&tempchar);            size++;            if(tempchar=='"')                ttype=string;            else if(isalpha(tempchar))                ttype=ident;            else if(isdigit(tempchar))                ttype=num;            else if(ispunct(tempchar))                ttype=punct;            else                ttype=eof;        }        else        {            if(isspace(tempchar))                continue;            if(ttype == ident)            {                if(isalnum(tempchar)|| tempchar=='_')                {                    strcat(token,&tempchar);                    size++;                    continue;                }                else                {                    tok_type temp;                    temp.ttype=ttype;                    strcpy(temp.value,token);                    temp.size=size;                    fwrite(&temp,1,sizeof(temp),out);                    size=0;                    memset(&temp,0,sizeof(temp));                    ungetc(tempchar,in);                }            }            else if(ttype==num)            {                if(isdigit(tempchar))                {                    strcat(token,&tempchar);                    size++;                    continue;                }                else                {                    tok_type temp;                    temp.ttype=ttype;                    strcpy(temp.value,token);                    temp.size=size;                    fwrite(&temp,1,sizeof(temp),out);                    size=0;                    memset(&temp,0,sizeof(temp));                    ungetc(tempchar,in);                }            }            else if(ttype==string)            {                if(tempchar=='"')                {                    if(token[size-1]=='\\')                    {                        strcat(token,&tempchar);                        size++;                        continue;                    }                    else                    {                        tok_type temp;                        temp.ttype=ttype;                        strcpy(temp.value,token);                        temp.size=size;                        fwrite(&temp,1,sizeof(temp),out);                        size=0;                        memset(&temp,0,sizeof(temp));                        ungetc(tempchar,in);                    }                }                else                {                    strcat(token,&tempchar);                    size++;                    continue;                }            }        }    }    fclose(in);    fclose(out);    fflush(stdin);    return 0;}
Joakim_ar
Joakim_ar
As somebody else mentioned, using a scanner (tokenizer) and parser generation tool , such as the wonderful ANTLR tool is a much easier (and more maintainable) way to go than to write everything in a general purpose language such as c++. ANTLR can even build a syntax tree for you, reducing the complexity a great deal.
webwraith
webwraith
I understand what you're saying J_a, but the idea is to write my own. I don't want to just blindly use someone else's program. I have an annoying habit of wanting to roll my own, if for no other reason than to see if it can be done in the way I imagine it to be done
Joakim_ar
Joakim_ar
I totally dig that :) It's nice to know what's going on behind the scenes.
Have you taken a look in the Scripting Languages and Mod Development aricles at this site yet?
Extrarius
Extrarius
I strongly suggest the book Compilers: Principles, Techniques, and Tools. It's _FAR_ better than any tutorials on the internet (or, at least, all that I've seen) because it explains in detail the theory and design parts, and it sounds like that is what you're having a hard time with.

If you'd like to look at a small calculator-type program I made that has a tokenizer in it (with a tiny bit of commenting), you can download ExprCalc. The tokenizer is the function "ExprParser::NextToken". Be warned that the program has not been extensively bug tested so it could have significant faults =-)
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
daerid
daerid
Quote:
Original post by Extrarius
I strongly suggest the book Compilers: Principles, Techniques, and Tools. It's _FAR_ better than any tutorials on the internet (or, at least, all that I've seen) because it explains in detail the theory and design parts, and it sounds like that is what you're having a hard time with.

If you'd like to look at a small calculator-type program I made that has a tokenizer in it (with a tiny bit of commenting), you can download ExprCalc. The tokenizer is the function "ExprParser::NextToken". Be warned that the program has not been extensively bug tested so it could have significant faults =-)


Yeah, on that note, CPTT is a great book, but it's a f**kin bear to get down unless you're very familiar with lots and lots of algebra and a little calculus. It's definitely the best reference out there (even though it's ~20 years old), but most definitely NOT for the faint of heart.
daerid@gmail.com
Extrarius
Extrarius
Quote:
Original post by daerid
[...]Yeah, on that note, CPTT is a great book, but it's a f**kin bear to get down unless you're very familiar with lots and lots of algebra and a little calculus. It's definitely the best reference out there (even though it's ~20 years old), but most definitely NOT for the faint of heart.
While it does have a lot of algebraic expressions, I don't really think you need to be good with math so much as good with abstractions in general. A lot of people freak out if they see something like a regular expression, which is pretty much what many of the expressions are. A requirement for algebra has the connotation (to me) that you'll need to solve equations or maniulate them extensively, but most of the expressions are just shorter ways to saw what the text says.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
webwraith
webwraith
yeah,I've actually had a link to that for quite a while, but it got lost in my bookmarks folders :/ Well, I went through it, and I've now got a cool (well, I think it is :)) little lexer:

lexer.h:
#ifndef _LEX_H#define _LEX_H#include <iostream>#include <fstream>#include <string>//using operandsusing std::ifstream;using std::ofstream;using std::string;enum token_type{unknown=0,ident,number,punct,comment,strlit};//used by the lexer to work out how to act in different situationsstruct tok_type{    token_type token;    std::string value;};class str_test{    public:        bool    isAlpha(char);        bool    isNum(char);        bool    isSpace(char);        bool    isAlphaNum(char);        bool    isPunct(char);        bool    isUpper(char);        bool    isLower(char);        char    caseToggle(char);//NOTE: takes a single char and converts it to its alternate case(upper->lower,lower->upper)};//basic lexer classclass base_lexer{    public:        base_lexer(ifstream& _in):in(_in){}        ~base_lexer(){}        tok_type NextToken();//the main method of the lexer    protected:        char GetChar(){return in.get();}        void Unget(){in.unget();}        str_test str;        ifstream& in;};#endif


lexer.cpp:
tok_type base_lexer::NextToken(){    static char temp=GetChar();    std::string token;    tok_type ret;    //ignore whitespace    if(str.isSpace(temp))    {        //use a do...while() loop so temp is always holding a new charcter        while(str.isSpace(temp))        {            temp=GetChar();        }    }    //is token a comment?    if(temp=='#')    {        while(temp!='\n'&&temp!='\r')        {            temp=GetChar();        }        temp=GetChar();    }    token.append(&temp);    //is the token an identifier?    if(str.isAlpha(temp) || temp=='_')    {        ret.token=ident;        while(!in.eof())        {            temp=GetChar();            if(str.isAlphaNum(temp) || temp=='_')            {                token.append(&temp);            }            else            {                ret.value=token;                return ret;            }        }    }    //is token a number?    else if(str.isNum(temp))    {        ret.token=number;        while(!in.eof())        {            temp=GetChar();            if(str.isNum(temp))            {                token.append(&temp);            }            else            {                ret.value=token;                return ret;            }        }    }    //is token a string const?    //NOTE: The string literal does not mark escape sequences. They are included    //into the body of the text as part of the literal string. The only    //reason special case code is needed is to allow the '"' character    else if(temp=='\"')    {        ret.token=strlit;        temp=GetChar();        token.append(&temp);        while(temp!='\"' && !in.eof())        {            if(temp=='\\')            {                temp=GetChar();                token.append(&temp);            }            temp=GetChar();            token.append(&temp);        }        ret.value=token;        temp=GetChar();        return ret;    }    //is token punctuation?    //NOTE: punctuation currently acts like numbers, in that the lexer keeps adding    //to the token for as long as the next char is punctuation.    //This will have to be changed to allow strings surrounded by other punctuation    else if(str.isPunct(temp))    {        ret.token=punct;        while(!in.eof())        {            temp=GetChar();            if(str.isPunct(temp))            {                token.append(&temp);            }            else            {                ret.value=token;                return ret;            }        }    }    //the token found is about as helpful as a caterer serving roadkill at a wedding...ToT    else    {        ret.token=unknown;        ret.value=temp;        return ret;    }}/**  * str_test:  *          The string testing class.  *  *          I thought of just making these functions wrappers of the functions  *          found in string.h and cstring, but as they are all single digits,  *          I can just test them quickly against ASCII values  */bool str_test::isAlpha(char c){    if((c>='A' && c<='Z') || (c>='a' && c<='z'))return true; else return false;}bool str_test::isNum(char c){    if(c>='0' && c<='9')return true;else return false;}bool str_test::isAlphaNum(char c){    if(isAlpha(c) || isNum(c))return true;else return false;}bool str_test::isLower(char c){    if(c>='a' && c<='z')return true;else return false;}bool str_test::isUpper(char c){    if(c>64 && c<91)return true; else return false;}bool str_test::isSpace(char c){    if(c==' ' || c=='\n' || c=='\r' || c=='\t')return true;else return false;}bool str_test::isPunct(char c){    if((c>32 && c<48) || (c>57 && c<65) || (c>90 && c<97) || (c>122 && c<127))return true;else return false;}char str_test::caseToggle(char c){    if(isUpper(c))return c+32;else if(isLower(c))return c-32;else return 0;}


OK, I know that ASCII is old, and UTF and Unicode should be supported instead, but I don't care at the mo :P

I've got a few improvements in mind for this, but I'd be happy to hear people's suggestions too
orcfan32
orcfan32
When you put

bool str_test::isUpper(char c){    if(c>64 && c<91)return true; else return false;}


Wouldn't it have been easier to use

bool str_test::isUpper(char c){    if(c>'A' && c<'Z')return true; else return false;}


Or am I horribly mistaken?

EDIT: I am horribly mistaken... -_-

EDIT2: I cnp'ed your code to try to hunt bugs, etc. It crashes on string literals for me...

[Edited by - orcfan32 on August 7, 2006 9:00:13 PM]
The best thing to do is just choose whatever you think you'd prefer, and go for it. -Promit
webwraith
webwraith
What the heck is "cnp'ed"? I've found that MinGW doesn't like using C-style string functions (basically )

Back on track, what would be the most effective way for me to pass in a list of keywords for the lexer to look out for? I had a go and just got the Windows Error report dialog T_T

Still, I did get it to keep track of the line number it is on, and it tokenizes every plain-text file I feed into it

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.