In the first part, Development of a stacked virtual machine and a compiler for it (part I), I made my own elementary stack virtual machine that can work with the stack, do arithmetic with signed integers, conditional jumps and function calls with return. But since the goal was to create not only a virtual machine, but also a C compiler for a similar language, it was time to take the first steps towards compilation. No experience. I will act according to my understanding.
"C " (, - ). - "" ( ) , .
, - , , (, , , ). C.
constexpr char* BLANKS = "\x20\n\t";
constexpr char* DELIMETERS = ",;{}[]()=><+-*/&|~^!.";
enum class TokenType {
NONE = 0, UNKNOWN, IDENTIFIER,
CONST_CHAR, CONST_INTEGER, CONST_REAL, CONST_STRING,
COMMA, MEMBER_ACCESS, EOS,
OP_BRACES, CL_BRACES, OP_BRACKETS, CL_BRACKETS, OP_PARENTHESES, CL_PARENTHESES,
BYTE, SHORT, INT, LONG, CHAR, FLOAT, DOUBLE, STRING, IF, ELSE, WHILE, RETURN,
ASSIGN, EQUAL, NOT_EQUAL, GREATER, GR_EQUAL, LESS, LS_EQUAL,
PLUS, MINUS, MULTIPLY, DIVIDE, AND, OR, XOR, NOT, SHL, SHR,
LOGIC_AND, LOGIC_OR, LOGIC_NOT
};
typedef struct {
TokenType type;
char* text;
WORD length;
WORD row;
WORD col;
} Token;
, parseToTokens(char*). : (BLANKS DELIMETERS), , () . - , (, "315.0") / ("obj10.field1"), .
void VMLexer::parseToTokens(const char* sourceCode) {
TokenType isNumber = TokenType::UNKNOWN;
bool insideString = false; // inside string flag
bool isReal = false; // is real number flag
size_t length; // token length variable
char nextChar; // next char variable
bool blank, delimeter; // blank & delimeter char flags
tokens->clear(); // clear tokens vector
rowCounter = 1; // reset current row counter
rowPointer = (char*)sourceCode; // set current row pointer to beginning
char* cursor = (char*)sourceCode; // set cursor to source beginning
char* start = cursor; // start new token from cursor
char value = *cursor; // read first char from cursor
while (value != NULL) { // while not end of string
blank = isBlank(value); // is blank char found?
delimeter = isDelimeter(value); // is delimeter found?
length = cursor - start; // measure token length
// Diffirentiate real numbers from member access operator '.'
isNumber = identifyNumber(start, length - 1); // Try to get integer part of real number
isReal = (value=='.' && isNumber==TokenType::CONST_INTEGER); // Is current token is real number
if ((blank || delimeter) && !insideString && !isReal) { // if there is token separator
if (length > 0) pushToken(start, length); // if length > 0 push token to vector
if (value == '\n') { // if '\n' found
rowCounter++; // increment row counter
rowPointer = cursor + 1; // set row beginning pointer
}
nextChar = *(cursor + 1); // get next char after cursor
if (!blank && isDelimeter(nextChar)) { // if next char is also delimeter
if (pushToken(cursor, 2) == TokenType::UNKNOWN) // try to push double char delimeter token
pushToken(cursor, 1); // if not pushed - its single char delimeter
else cursor++; // if double delimeter, increment cursor
} else pushToken(cursor, 1); // else push single char delimeter
start = cursor + 1; // calculate next token start pointer
}
else if (value == '"') insideString = !insideString; // if '"' char - flip insideString flag
else if (insideString && value == '\n') { // if '\n' found inside string
// TODO warn about parsing error
}
cursor++; // increment cursor pointer
value = *cursor; // read next char
}
length = cursor - start; // if there is a last token
if (length > 0) pushToken(start, length); // push last token to vector
}
parseToTokens, , . .
class VMLexer {
public:
VMLexer();
~VMLexer();
void parseToTokens(const char* sourceCode);
Token getToken(size_t index);
size_t getTokenCount();
WORD tokenToInt(Token& tkn);
private:
vector<Token>* tokens;
WORD rowCounter;
char* rowPointer;
bool isBlank(char value);
bool isDelimeter(char value);
TokenType pushToken(char* text, size_t length);
TokenType getTokenType(char* text, size_t length);
TokenType identifyNumber(char* text, size_t length);
TokenType identifyKeyword(char* text, size_t length);
};
VMLexer C ( , ):
int main()
{
printf ("Wow!");
float a = 365.0 * 10 - 10.0 / 2 + 3;
while (1 != 2) {
abc.v1 = 'x';
}
if (a >= b) return a && b; else a || b;
};
:
, . - . , :
. ( ) :
void VMCompiler::parseExpression() {
Token tkn;
parseTerm();
tkn = lexer->getToken(currentToken);
while (tkn.type==TokenType::PLUS || tkn.type==TokenType::MINUS) {
currentToken++;
parseTerm();
if (tkn.type == TokenType::PLUS) {
destImage->emit(OP_ADD);
} else {
destImage->emit(OP_SUB);
}
tkn = lexer->getToken(currentToken);
}
}
void VMCompiler::parseTerm() {
Token tkn;
parseFactor();
currentToken++;
tkn = lexer->getToken(currentToken);
while (tkn.type == TokenType::MULTIPLY || tkn.type == TokenType::DIVIDE) {
currentToken++;
parseFactor();
if (tkn.type == TokenType::MULTIPLY) {
destImage->emit(OP_MUL);
} else {
destImage->emit(OP_DIV);
}
currentToken++;
tkn = lexer->getToken(currentToken);
}
}
void VMCompiler::parseFactor() {
Token tkn = lexer->getToken(currentToken);
bool unaryMinus = false;
if (tkn.type == TokenType::MINUS) {
currentToken++;
tkn = lexer->getToken(currentToken);
unaryMinus = true;
}
if (unaryMinus) destImage->emit(OP_CONST, 0);
if (tkn.type == TokenType::OP_PARENTHESES) {
currentToken++;
parseExpression();
} else if (tkn.type == TokenType::CONST_INTEGER) {
destImage->emit(OP_CONST, lexer->tokenToInt(tkn));
}
if (unaryMinus) destImage->emit(OP_SUB);
}
Let's try to pass the expression " -3 + 5 * (6 + 2) * 3 + 15/5" to the compiler , disassemble the generated code into the console and immediately execute it on the virtual machine. We expect that the result of the calculation should remain at the top of the stack - 120 .
Hooray! Happened! We have a simple but working virtual machine, lexer, compiler of integer expressions with constants. All this is very encouraging!
PS Of course, it would be correct to build a full-fledged AST (abstract syntax tree), a symbol table and much more for convenient code generation, which I learned about from the comments, but the first steps towards the compiler have already been taken.