Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    557
  • comments
    1237
  • views
    423612

Untitled

Sign in to follow this  
Evil Steve

93 views

I'm happy.

const int g_nFoo = (256 >> 8) * 100 - 50;
const int g_nBar = g_nFoo * 2;

int Add(int a, int b) {}


^ Compiles perfectly. Still doesn't generate assembly, but that'll be trivial. And besides, there'd be nothing to generate here [smile]

Expressions are evaluated at compile time, so the above snippet is exactly the same as:

const int g_nFoo = 50;
const int g_nBar = 100;

int Add(int a, int b) {}


Supported operators are, in precedence tier order (So operators on the same row have the same precedence and are evaluated left to right):
~ !
* / % **
+ -
<< >>
& ^ |
< <= > >= == !=
&& ^^ ||

** is pow(), and ^^ is logical XOR. Apparently it doesn't exist in C++. I've never needed to use it before, but I figured I might as well add it in.


So, a little more information on how it all works...
As soon as the compiler sees the const keyword, it knows it can expect a type, then an identifier than '=', then an expression. Expressions always end with a semicolon.
So, it gets to the point of parsing the expression, and it reads a series of TokenStruct's until it finds a semicolon. Here's a couple of structs:

struct CodeNode
{
CodeNode() {}
~CodeNode()
{
for(size_t i=0; i delete expr;
}

std::vector expr;
};

struct TokenStruct
{
TokenStruct() {pCode = NULL;}
~TokenStruct() {delete pCode;}

Token eToken;
char szLexeme[MAX_LEXEME_LEN];

TokenStruct* pNext;
TokenStruct* pPrev;
CodeNode* pCode;
size_t nCharOffset;
unsigned int nLine;
};

It builds up a linked list of TokenStruct's as it goes, setting the token and lexeme to what the lexer returns. TokenStruct's are allocated in a pool allocator, so cache misses should be fairly minimal.
Once the expression parser has the token stream, it gets to work looking for brackets. Whenever it finds brackets, it recursively calls itself. If it doesn't find any brackets, then it calls GenerateICode(), which goes through each operator precedence level, hunting for operators, and then pulling out left and right operands. Here's the whole function, although it probably won't make a lot of sense out of context. And also the GenerateCodeForToken() function because it's fairly short:

static bool GenerateCodeForToken(TokenStruct* pToken)
{
ExpressionContext* pContext;
if((pToken->eToken > TOKBLOCK_OpFirst) && (pToken->eToken < TOKBLOCK_OpLast))
pContext = new ExpressionContextOp(pToken->eToken);
else if(pToken->eToken == TOK_Integer)
pContext = new ExpressionContextInt(pToken->szLexeme);
else if(pToken->eToken == TOK_Float)
pContext = new ExpressionContextFloat(pToken->szLexeme);
else if(pToken->eToken == TOK_String)
pContext = new ExpressionContextString(pToken->szLexeme);
else if(pToken->eToken == TOK_Identifier)
pContext = new ExpressionContextIdent(pToken->szLexeme);
else
return false;

pToken->pCode = new CodeNode;
pToken->pCode->expr.push_back(pContext);
return true;
}

static TokenStruct* GenerateICode(TokenStruct* pFirst, TokenStruct* pLast, ErrorData& theError)
{
TokenStruct* pCodeNode = pFirst;
for(size_t nLevel=0; nLevel {
TokenStruct* pToken = pFirst;
while(pToken != pLast)
{
// Is this token an operator?
Token tokCurr = pToken->eToken;
if((tokCurr > TOKBLOCK_OpFirst) && (tokCurr < TOKBLOCK_OpLast))
{
// Is it a recognised operator?
for(size_t nOp=0; s_eOpPrecedence[nLevel][nOp]!=TOK_Unknown; ++nOp)
{
if(tokCurr != s_eOpPrecedence[nLevel][nOp])
continue;

// We recognise this operator. We need a right and maybe left operand for it
TokenStruct* pLeft = NULL;
if(!IsUnaryOp(tokCurr))
{
pLeft = pToken->pPrev;
if(!pLeft)
{
theError.pErrorToken = pToken;
return NULL;
}
}
TokenStruct* pRight = pToken->pNext;
if(!pRight)
{
theError.strError = "Unexpected end of expression";
return NULL;
}

// Get code for left
if(pLeft && !pLeft->pCode && !GenerateCodeForToken(pLeft))
{
theError.pErrorToken = pToken;
return NULL;
}

// Get code for right
if(!pRight->pCode && !GenerateCodeForToken(pRight))
{
theError.pErrorToken = pRight;
return NULL;
}

// Emit code for operator in RPN
pToken->pCode = new CodeNode;
pToken->pCode->expr.insert(pToken->pCode->expr.end(), pRight->pCode->expr.begin(), pRight->pCode->expr.end());
if(pLeft) pToken->pCode->expr.insert(pToken->pCode->expr.end(), pLeft->pCode->expr.begin(), pLeft->pCode->expr.end());
pToken->pCode->expr.push_back(new ExpressionContextOp(pToken->eToken));
if(pLeft) pLeft->pCode->expr.clear();
pRight->pCode->expr.clear();

// Unlink left operand
if(pLeft)
{
if(pLeft->pPrev) pLeft->pPrev->pNext = pToken;
pToken->pPrev = pLeft->pPrev;
}

// Unlink right operand
if(pRight->pNext) pRight->pNext->pPrev = pToken;
pToken->pNext = pRight->pNext;

pToken->eToken = TOK_Invalid; // Debug(?)
pCodeNode = pToken;
}
}
else
{
// Not an operator, emit code for it
if(!pToken->pCode && !GenerateCodeForToken(pToken))
{
theError.pErrorToken = pToken;
return NULL;
}
}

pToken = pToken->pNext;
}
}

// This should generate one node of code. Any more means we have something like "7 42"
if(pCodeNode->pNext != pLast)
{
Assert(pCodeNode->pNext);
theError.pErrorToken = pCodeNode->pNext;
return NULL;
}
return pCodeNode;
}

That took ages for me to replace all the tabs with three spaces, so I hope you appreciate it :P

An ExpressionContext is a class which wraps an element of an expression. Once the expression parser has done its stuff, it creates an Expression class, which contains little more than a vector of ExpressionContext pointers. It calls on them to evaluate the code (By using an operand stack which is passed along), and to determine if the whole expression is constant, and so on.

And it all nicely points out errors to you. For instance:

const int g_nFoo = 12 + 3456 + 17 * (8 + 3 << 17) +
& 14;

Produces:
Compiling test.ds...
test.ds:2: Syntax error: Unexpected "14" At:
const int g_nFoo = 12 + 3456 + 17 * (8 + 3 << 17) +
& 14;
^


Bollocks. Oh well, I'll fix that later. It's close enough anyway.

I'm bored typing. The whole Parser_Expression.cpp file is uploaded here. Most of the meaty bits are in the expression context stuff, but I can't be bothered showing you that, because if you're interested enough to look at that, you'll need more and more, and then I'm just as well exposing all my code. Which I will do, but only once DruinkScript is more complete than it is.

Anyway, I'm off to watch Mythbusters and sleep.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!