I'm really new to this concept.
My mistake, i forgot this was in "Beginners Area".. hehe
If you havent done any parsing before i suggest reading up on it before jumping in.
http://en.wikipedia.org/wiki/Parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser <-- easiest to implement in my oppinion
What it boils down to is that an expression like this:
x = a + b * 2
Is translated into either a node structure:
(ASSIGN (VARIABLE x) (ADD (VARIABLE a) (MUL (VARIABLE b) (NUMBER 2) ) ) )
A node can defined like this.
Type TNode Field Left:TNode Field Right:TNode Field Value:String EndType
Or directly to assembler (doesnt have to be real machine asm though, could be an imaginary machine like below)
GET a GET b PUSH 2 MUL ADD SET x
Compilers usually compile to a node tree, then work (doing optimizations etc) on that tree and then spit out some assembler code.
You dont have to use a virtual machine though, you could jsut as well execute the node structure, but it would be a little slower.
What i meant by single number type was just for simplicity of the virtual machine, eg no strings and other fancy structures like proper function calls.
an OpCode is roughly the same as an Instruction, a single operation a CPU or a virtual machine executes.
I adapted an expression interpreter i made a while back to spit out code for a very simple virtual machine, so you can see how it all fits together:
Framework BRL.StandardIO Import BRL.LinkedList Import BRL.Math SuperStrict Private ' COMPILER Global source:String Global pos:Int Global code:Int[] Global cp:Int Global vars:TList = New TList Global numvars:Int Type TVariable Field Name:String Field Index:Int Field Value:Float Function Create:TVariable( name:String, value:Float, index:Int) Local v:TVariable = New TVariable v.Name = name v.Value = value v.Index = index Return v EndFunction EndType Function AddCode( op:Int) If code.Length = 0 Then code = New Int[32] ElseIf cp >= code.Length Then Local sz:Int = code.Length code = code[sz..sz*2] EndIf code[cp] = op cp :+ 1 EndFunction Function AddParam( value:Float) If code.Length = 0 Then code = New Int[32] ElseIf cp >= code.Length Then Local sz:Int = code.Length code = code[sz..sz*2] EndIf Float Ptr(Varptr code[cp])[0] = value cp :+ 1 EndFunction Function ReportError( s:String, printpos:Int = True) If printpos Then Print "ERROR: pos="+pos+" : "+s Else Print "ERROR: "+s EndIf EndFunction Function EatWhitespace() While (pos < source.Length) And ((source[pos] = Asc(" ")) Or (source[pos] = Asc("~t")) Or (source[pos] = Asc("~n")) Or (source[pos] = Asc("~r"))) pos :+ 1 Wend EndFunction Function EatIdent:String() Local start:Int = pos While (pos < source.Length) And (((source[pos] >= Asc("a")) And (source[pos] <= Asc("z"))) Or .. ((source[pos] >= Asc("A")) And (source[pos] <= Asc("Z"))) Or .. ((source[pos] >= Asc("0")) And (source[pos] <= Asc("9"))) Or (source[pos] = Asc("_"))) pos :+ 1 Wend Return source[start..pos] EndFunction Function EatNumber:Double() Local start:Int = pos Local gotsep:Int = False Local res:String While (pos < source.Length) And ((source[pos] >= Asc("0")) And (source[pos] <= Asc("9"))) pos :+ 1 If pos >= source.Length Then Exit If source[pos] = Asc(".") Then If gotsep Then ReportError( "error in number") Return False EndIf gotsep = True pos :+ 1 EndIf Wend Return source[start..pos].ToDouble() EndFunction Function Primary:Int() EatWhitespace() If source[pos] = Asc("(") Then pos :+ 1 AddExpression() If source[pos] <> Asc(")") Then ReportError( "expected )") pos :+ 1 ElseIf (source[pos] >= Asc("0")) And (source[pos] <= Asc("9")) Then AddCode( OP_PUSH) AddParam( EatNumber()) ElseIf source[pos] = Asc("-") Then pos :+ 1 AddCode( OP_PUSH) AddParam( - EatNumber()) If Not AddExpression() Return False ElseIf ((source[pos] >= Asc("a")) And (source[pos] <= Asc("z"))) Or .. ((source[pos] >= Asc("A")) And (source[pos] <= Asc("Z"))) Or (source[pos] = Asc("_")) Then Local ident:String = EatIdent() If source[pos] = Asc("(") Then pos :+ 1 EatWhitespace() If source[pos] = Asc(")") Then ' no parameters pos :+ 1 CompileFunction( ident) Else AddExpression() If source[pos] = Asc(")") Then ' 1 parameter pos :+ 1 CompileFunction( ident) ElseIf source[pos] = Asc(",") Then ' 2 parameters pos :+ 1 AddExpression() If source[pos] <> Asc(")") Then ReportError( "expected )") pos :+ 1 CompileFunction( ident) Else ReportError( "invalid function expression => " + ident) Return False EndIf EndIf Else Local id:Int = LookupVariable( ident) If id <> -1 Then AddCode( OP_GET) AddCode( id) Else ReportError( "undefined variable " + ident) Return False EndIf EndIf Else ReportError( "expected number or -number or (expression)") Return False EndIf EatWhitespace() Return True EndFunction Function MulExpression:Int() EatWhitespace() If Not Primary() Then Return False While (pos < source.Length) And ((source[pos] = Asc("*")) Or (source[pos] = Asc("/"))) If source[pos] = Asc("*") Then pos :+ 1 If Not Primary() Then Return False AddCode( OP_MUL) ElseIf source[pos] = Asc("/") Then pos :+ 1 If Not Primary() Then Return False AddCode( OP_DIV) EndIf Wend EatWhitespace() Return True EndFunction Function AddExpression:Int() EatWhitespace() If Not MulExpression() Then Return False While (pos < source.Length) And ((source[pos] = Asc("+")) Or (source[pos] = Asc("-"))) If source[pos] = Asc("+") Then pos :+ 1 If Not MulExpression() Then Return False AddCode( OP_ADD) ElseIf source[pos] = Asc("-") Then pos :+ 1 If Not MulExpression() Then Return False AddCode( OP_SUB) EndIf Wend EatWhitespace() Return True EndFunction Function CompileFunction:Int( ident:String) Select ident.ToLower() Case "sin" AddCode( OP_SIN) Case "cos" AddCode( OP_COS) Default ReportError( "undefined function " + ident) Return False EndSelect Return True EndFunction Function LookupVariable:Int( name:String) name = name.ToLower() For Local v:TVariable = EachIn vars If v.Name = name Then Return v.Index Next Return -1 EndFunction Public Function AddVariable( name:String, value:Float = 0.0) Local v:TVariable = TVariable.Create( name.ToLower(), value, numvars) vars.AddLast( v) numvars :+ 1 EndFunction Function Compile:Int( s:String) source = s Local id:Int Local idx:Int = source.Find( "=") If idx > 0 Then Local ident:String = EatIdent() id = LookupVariable( ident) If id = -1 Then ReportError( "undefined variable " + ident) Return False EndIf EatWhitespace() pos :+ 1 If Not AddExpression() Then Return False AddCode( OP_SET) AddCode( id) Return True ElseIf idx = 0 Then ReportError( "invalid assignment", False) Return False EndIf If Not AddExpression() Then Return False Return True EndFunction Function GetCompiledCodeData( c:Int[] Var, d:Float[] Var) c = code[..cp] d = New Float[numvars] Local i:Int = 0 For Local v:TVariable = EachIn vars d[i] = v.Value i :+ 1 Next EndFunction Function ResetCompiler() source = Null pos = 0 code = Null cp = 0 vars.Clear() numvars = 0 EndFunction ' VIRTUAL MACHINE Const OP_PUSH:Int = 0 Const OP_GET:Int = 1 Const OP_SET:Int = 2 Const OP_ADD:Int = 3 Const OP_SUB:Int = 4 Const OP_MUL:Int = 5 Const OP_DIV:Int = 6 Const OP_SIN:Int = 7 Const OP_COS:Int = 8 Type TMicroVM Field Data:Float[] Field Code:Int[] Field Stack:Int[] Field CP:Int Field SP:Int Method Execute:Float() CP = 0 SP = Stack.Length While CP < Code.Length Select Code[CP] Case OP_PUSH CP :+ 1 SP :- 1 Stack[SP] = Code[CP] Case OP_GET CP :+ 1 SP :- 1 Float Ptr(Varptr Stack[SP])[0] = Data[ Code[CP]] Case OP_SET CP :+ 1 Data[ Code[CP]] = Float Ptr(Varptr Stack[SP])[0] SP :+ 1 Case OP_ADD Float Ptr(Varptr Stack[SP+1])[0] :+ Float Ptr(Varptr Stack[SP])[0] SP :+ 1 Case OP_SUB Float Ptr(Varptr Stack[SP+1])[0] :- Float Ptr(Varptr Stack[SP])[0] SP :+ 1 Case OP_MUL Float Ptr(Varptr Stack[SP+1])[0] :* Float Ptr(Varptr Stack[SP])[0] SP :+ 1 Case OP_DIV Float Ptr(Varptr Stack[SP+1])[0] :/ Float Ptr(Varptr Stack[SP])[0] SP :+ 1 Case OP_SIN Float Ptr(Varptr Stack[SP])[0] = Sin( Float Ptr(Varptr Stack[SP])[0]) Case OP_COS Float Ptr(Varptr Stack[SP])[0] = Sin( Float Ptr(Varptr Stack[SP])[0]) EndSelect CP :+ 1 Wend If SP < Stack.Length Then Return Float Ptr(Varptr Stack[SP])[0] Else Return Float Ptr(Varptr Stack[Stack.Length-1])[0] EndIf EndMethod EndType ' TEST Local vm:TMicroVM = New TMicroVM ResetCompiler() AddVariable( "a", 1) AddVariable( "b", 2) AddVariable( "x") Compile( "x = a + b * 2") vm.Stack = New Int[32] GetCompiledCodeData( vm.Code, vm.Data) Print vm.Execute()