好友学习递归时无法理解用递归下降的方式分析表达式，所以写了个简单的例子，
为了使代码尽可能简单，省略了此法分析模块，直接使用人脑分析的词法^_^
由于好友不懂c++，所以这里虽然用的c++，但还是按照c的方式写的代码。
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
#define MAX_ID_LENGTH 20
#define ID 1
#define DIGIT 2
#define EQUAL 3
#define PLUS 4
#define MUL 5
#define SUB 6
#define INPUT_CODE "var = 20 - 59"
char* KeyWord[] =
{
"print",
"status",
};
typedef struct _TOKEN_
{
int type;
char str[MAX_ID_LENGTH];
}Token;
typedef vector<Token> Tokens;
Tokens g_tokens;
int g_tokenIndex = 0;
int ParseStatement();
int ParseExpresstion();
int ParseTerm();
int ParseFactor();
void PushBackToken(int type, const char* str)
{
Token token = { 0 };
token.type = type;
strcpy(token.str, str);
g_tokens.push_back(token);
}
void GetAllTokens()
{
PushBackToken(ID, "var");
PushBackToken(EQUAL, "=");
PushBackToken(DIGIT, "20");
PushBackToken(MUL, "*");
PushBackToken(DIGIT, "3");
}
bool IsEnd()
{
return g_tokenIndex == g_tokens.size();
}
Token GetNextToken()
{
if ( g_tokenIndex <= g_tokens.size() - 1 )
{
return g_tokens[g_tokenIndex++];
}
else
{
Token token = { 0 };
return token;
}
}
void UnGetNextToken()
{
--g_tokenIndex;
}
void ShowAllTokens()
{
for (int i = 0; i < g_tokens.size(); i++)
{
cout << g_tokens[i].str;
}
}
int ParseStatement()
{
Token token = GetNextToken();
if ( ID != token.type )
{
cout << "statement should begin with identifier" << endl;
}
token = GetNextToken();
if ( EQUAL != token.type )
{
cout << "= lost" << endl;
}
return ParseExpresstion();
}
int ParseExpresstion()
{
int sum = ParseTerm();
while (true)
{
if ( IsEnd() )
{
return sum;
}
Token token = GetNextToken();
if ( PLUS == token.type )
{
sum += ParseTerm();
}
else if ( SUB == token.type )
{
sum -= ParseTerm();
}
//todo: add "-"
else
{
UnGetNextToken();
break;
}
}
return sum;
}
int ParseTerm()
{
int mulResult = ParseFactor();
while ( true )
{
if ( IsEnd() )
{
return mulResult;
}
Token token = GetNextToken();
if ( MUL == token.type )
{
mulResult *= ParseFactor();
}
else
{
UnGetNextToken();
break;
}
//todo add "/"
}
return mulResult;
}
int ParseFactor()
{
Token token = GetNextToken();
if ( ID == token.type )
{
cout << "statement should begin with identifier" << endl;
}
else if( DIGIT == token.type )
{
return atoi(token.str);
}
else
{
UnGetNextToken();
//cout << "bug found" << endl;
}
return 1;
}
void TestPlus()
{
g_tokenIndex = 0;
g_tokens.clear();
PushBackToken(ID, "var");
PushBackToken(EQUAL, "=");
PushBackToken(DIGIT, "20");
PushBackToken(PLUS, "+");
PushBackToken(DIGIT, "30");
PushBackToken(PLUS, "+");
PushBackToken(DIGIT, "30");
PushBackToken(SUB, "-");
PushBackToken(DIGIT, "1");
assert(79 == ParseStatement());
}
void TestSub()
{
g_tokenIndex = 0;
g_tokens.clear();
PushBackToken(ID, "var");
PushBackToken(EQUAL, "=");
PushBackToken(DIGIT, "20");
PushBackToken(SUB, "-");
PushBackToken(DIGIT, "30");
assert(-10 == ParseStatement());
}
void TestMul()
{
g_tokenIndex = 0;
g_tokens.clear();
PushBackToken(ID, "var");
PushBackToken(EQUAL, "=");
PushBackToken(DIGIT, "20");
PushBackToken(PLUS, "+");
PushBackToken(DIGIT, "30");
PushBackToken(MUL, "*");
PushBackToken(DIGIT, "30");
assert(920 == ParseStatement());
}
int main()
{
TestPlus(); //测试加法
TestSub(); //测试减法
TestMul(); //测试乘法
return 0;
}