A code generator translates the output of the syntax analyzer and/or semantic analyzer
into lower level code, either assembly, object, or virtual.

Task[edit]
Take the output of the Syntax analyzer task - which is a flattened Abstract Syntax Tree (AST) - and convert it to virtual machine code, that can be run by the
Virtual machine interpreter. The output is in text format, and represents virtual assembly code.

The program should read input from a file and/or stdin, and write output to a file and/or
stdout.

Example - given the simple program (below), stored in a file called while.t, create the list of tokens, using one of the Lexical analyzer solutions
lex < while.t > while.lex

Run one of the Syntax analyzer solutions

parse < while.lex > while.ast

while.ast can be input into the code generator.
The following table shows the input to lex, lex output, the AST produced by the parser, and the generated virtual assembly code.
Run as:  lex < while.t | parse | gen



 Input to lex

 Output from lex, input to parse

 Output from parse

 Output from gen, input to VM



count = 1;
while (count < 10) {
    print("count is: ", count, "\n");
    count = count + 1;
}


    1      1   Identifier      count
    1      7   Op_assign
    1      9   Integer              1
    1     10   Semicolon
    2      1   Keyword_while
    2      7   LeftParen
    2      8   Identifier      count
    2     14   Op_less
    2     16   Integer             10
    2     18   RightParen
    2     20   LeftBrace
    3      5   Keyword_print
    3     10   LeftParen
    3     11   String          "count is: "
    3     23   Comma
    3     25   Identifier      count
    3     30   Comma
    3     32   String          "\n"
    3     36   RightParen
    3     37   Semicolon
    4      5   Identifier      count
    4     11   Op_assign
    4     13   Identifier      count
    4     19   Op_add
    4     21   Integer              1
    4     22   Semicolon
    5      1   RightBrace
    6      1   End_of_input


Sequence
Sequence
;
Assign
Identifier    count
Integer       1
While
Less
Identifier    count
Integer       10
Sequence
Sequence
;
Sequence
Sequence
Sequence
;
Prts
String        "count is: "
;
Prti
Identifier    count
;
Prts
String        "\n"
;
Assign
Identifier    count
Add
Identifier    count
Integer       1


Datasize: 1 Strings: 2
"count is: "
"\n"
   0 push  1
   5 store [0]
  10 fetch [0]
  15 push  10
  20 lt
  21 jz     (43) 65
  26 push  0
  31 prts
  32 fetch [0]
  37 prti
  38 push  1
  43 prts
  44 fetch [0]
  49 push  1
  54 add
  55 store [0]
  60 jmp    (-51) 10
  65 halt

 Input format

As shown in the table, above, the output from the syntax analyzer is a flattened AST.

In the AST, Identifier, Integer, and String, are terminal nodes, e.g, they do not have child nodes.

Loading this data into an internal parse tree should be as simple as:

 
def load_ast()
    line = readline()
    # Each line has at least one token
    line_list = tokenize the line, respecting double quotes
 
    text = line_list[0] # first token is always the node type
 
    if text == ";"
        return None
 
    node_type = text # could convert to internal form if desired
 
    # A line with two tokens is a leaf node
    # Leaf nodes are: Identifier, Integer String
    # The 2nd token is the value
    if len(line_list) > 1
        return make_leaf(node_type, line_list[1])
 
    left = load_ast()
    right = load_ast()
    return make_node(node_type, left, right)
 
 Output format - refer to the table above
 The first line is the header: Size of data, and number of constant strings.
 size of data is the number of 32-bit unique variables used. In this example, one variable, count
 number of constant strings is just that - how many there are
 After that, the constant strings
 Finally, the assembly code
Registers

 sp: the stack pointer - points to the next top of stack. The stack is a 32-bit integer array.
 pc: the program counter - points to the current instruction to be performed. The code is an array of bytes.
Data
 
32-bit integers and strings

Instructions

Each instruction is one byte. The following instructions also have a 32-bit integer operand:

fetch [index]

where index is an index into the data array.

store [index]

where index is an index into the data array.

push n

where value is a 32-bit integer that will be pushed onto the stack.

jmp (n) addr

where (n) is a 32-bit integer specifying the distance between the current location and the
desired location. addr is an unsigned value of the actual code address.

jz (n) addr

where (n) is a 32-bit integer specifying the distance between the current location and the
desired location. addr is an unsigned value of the actual code address.

The following instructions do not have an operand. They perform their operation directly
against the stack:

For the following instructions, the operation is performed against the top two entries in
the stack:

add
sub
mul
div
mod
lt
gt
le
ge
eq
ne
and
or

For the following instructions, the operation is performed against the top entry in the
stack:

neg
not

prtc

Print the word at stack top as a character.

prti

Print the word at stack top as an integer.

prts

Stack top points to an index into the string pool. Print that entry.

halt

Unconditional stop.

 Additional examples
Your solution should pass all the test cases above and the additional tests found Here.

Reference
The C and Python versions can be considered reference implementations.

Related Tasks
 Lexical Analyzer task
 Syntax Analyzer task
 Virtual Machine Interpreter task
 AST Interpreter task

 
Module CodeGenerator (s$){
	Function code$(op$) {
		=format$("{0::-6} {1}", pc, op$)
		pc++
	}
	Function code2$(op$, n$) {
		=format$("{0::-6} {1} {2}", pc, op$, n$)
		pc+=5
	}
	Function code3$(op$,pc, st, ed) {
		=format$("{0::-6} {1} ({2}) {3}", pc, op$, ed-st-1, ed)
	}
 
	Enum tok {
		gneg, gnot, gmul, gdiv, gmod, gadd, gle, gsub, glt
		gle, ggt, gge, geq, gne, gand, gor, gprtc, gprti, gprts,
		gif, gwhile, gAssign, gSeq, gstring, gidentifier, gint, gnone
	}
 
	\\ Inventories are lists with keys, or keys/data (key must be unique)
	\\ there is one type more the Invetory Queue which get same keys.
	\\ But here not used.
	Inventory symb="Multiply":=gmul, "Divide":=gdiv, "Mod":=gmod, "Add":=gadd
	Append  symb, "Negate":=gneg, "Not":=gnot,"Less":=glt,"Subtract":=gsub
	Append  symb, "LessEqual":=gle, "Greater":=ggt, "GreaterEqual":=gge, "Sequence":=gSeq
	Append  symb, "Equal":=geq, "NotEqual":=gne,  "And":=gand, "Or":=gor, "While":=gwhile
	Append  symb, "Prtc":=gprtc,"Prti":=gprti,"Prts":=gprts, "Assign":=gAssign, "If":=gif
	Append  symb, "String":=gstring, "Identifier":=gidentifier, "Integer":=gint, ";", gnone
 
	Inventory DataSet
	\\ We set string as key. key maybe an empty string, a string or a number.
	\\ so we want eash string to saved one time only.
	Inventory Strings
 
	Const nl$=chr$(13)+chr$(10), Ansi=3
	Def z$, lim, line$, newvar_ok, i=0
	Document message$=nl$
	Global pc     \\ functions have own scope, so we make it global, for this module, and childs.
 
	Dim lines$()
	s$=filter$(s$,chr$(9))   \\ exclude tabs
	Lines$()=piece$(s$,nl$) \\ break to lines
	lim=len(Lines$())
	Flush ' empty stack (there is a current stack of values which we use here)
 
	Load_Ast()
	If not stack.size=1 Then Flush : Error "Ast not loaded"
	AST=array   \\ pop the array from stack
	Document Assembly$, Header$
 
	\\ all lines of assembly goes to stack. Maybe not in right order.
	\\ Push statement push to top, Data statement push to bottom of stack
 
	CodeGenerator(Ast)
	Data  code$("halt") ' append to end of stack
	\\ So now we get all data (letters) from stack
	While not empty
		Assembly$=letter$+nl$
	end while
	\\ So now we have to place them in order
	Sort Assembly$
 
	\\ Let's make the header
	Header$=format$("Datasize: {0} Strings: {1}", Len(Dataset),Len(strings))
	\\ we use an iterator object, str^ is the counter, readonly, but Eval$() use it from object.
	str=each(strings)    
	While str
		Header$=nl$+Eval$(str)
	End while
	Assembly$=nl$
	\\ insert to line 1 the Header
	Insert 1 Assembly$=Header$
	\\ Also we check for warnings
	If len(message$)>2 then Assembly$="Warnings: "+nl$+message$
	\\ So now we get a report
	\\ (at each 3/4 of window's lines, the printing stop and wait for user response, any key)
	Report Assembly$
	Clipboard Assembly$
	Save.Doc Assembly$, "code.t", Ansi
	End
	\\ subs have 10000 limit for recursion but can be extended to 1000000 or more.
	Sub CodeGenerator(t)
 
		If len(t)=3 then
			select case  t#val(0)
			Case gSeq
				CodeGenerator(t#val(1)) : CodeGenerator(t#val(2))
			Case gwhile
			{
				local spc=pc
				CodeGenerator(t#val(1)) 
				local pc1=pc
				pc+=5 ' room for jz
				CodeGenerator(t#val(2))
				data code3$("jz",pc1, pc1, pc+5)
				data code3$("jmp",pc,  pc, spc)
				pc+=5  ' room for jmp
			}
			Case gif
			{
				CodeGenerator(t#val(1)) 
				local pc1=pc, pc2
				pc+=5
				CodeGenerator(t#val(2)#val(1)) 
				If len(t#val(2)#val(2))>0 then
					pc2=pc
					pc+=5
					data code3$("jz",pc1, pc1, pc)
					CodeGenerator(t#val(2)#val(2))
					data code3$("jmp",pc2, pc2, pc)
				else
					data code3$("jz",pc1, pc1, pc)
				end If		
			}
			Case gAssign
			{
				CodeGenerator(t#val(2))
				local newvar_ok=true
				CodeGenerator(t#val(1))
			}
			case gneg to gnot, gprtc to gprts
				CodeGenerator(t#val(1)) : data code$(mid$(eval$(t#val(0)),2))
			case gmul to gor
			{
				CodeGenerator(t#val(1))
				CodeGenerator(t#val(2))
				data code$(mid$(eval$(t#val(0)),2))
			}
			End select
		Else.if len(t)=2 then
			select case  t#val(0)
			Case gString
			{
				local spos
				If exist(strings,t#val$(1)) then
					spos=eval(strings!)
				else
					append strings, t#val$(1)		
					spos=len(strings)-1
				end If
				Push code2$("push",str$(spos,0))
			}
			Case gInt
				Push code2$("push",t#val$(1), pc)
			Case gIdentifier
			{
				local ipos
				If exist(dataset,t#val$(1)) then
					ipos=Eval(dataset!)  ' return position
				else.if newvar_ok then
					Append dataset, t#val$(1)
					ipos=len(dataset)-1
				else
					message$="Variable "+t#val$(1)+" not initialized"+nl$
 
				end If
				If newvar_ok then
					Push code2$("store","["+str$(ipos, 0)+"]")
				else
					Push code2$("fetch","["+str$(ipos, 0)+"]")
				end If
			}
			end select
		End If
	End Sub
	Sub Load_Ast()
			If i>=lim then Push (,) : exit sub
			do
			line$=Trim$(lines$(i))
			I++
			tok$=piece$(line$," ")(0)
			until line$<>"" or i>=lim
			If tok$="Identifier" then
				Push (gidentifier,trim$(Mid$(line$,11)))
			else.if tok$="Integer" then
				long n=Val(Mid$(line$,8))  ' check overflow
				Push (gint, Trim$(Mid$(line$,8)))
			else.if tok$="String" then
				Push (gstring,Trim$(Mid$(line$,7)))
			else.if tok$=";" then
				Push (,)
			Else
				local otok=symb(tok$)
				Load_Ast() 
				Load_Ast()
				Shift 2
				Push (otok,array, array)
			End If
	End Sub
}
 
CodeGenerator {
	Sequence
	Sequence
	;
	Assign
	Identifier    count
	Integer       1
	While
	Less
	Identifier    count
	Integer       10
	Sequence
	Sequence
	;
	Sequence
	Sequence
	Sequence
	;
	Prts
	String        "count is: "
	;
	Prti
	Identifier    count
	;
	Prts
	String        "\n"
	;
	Assign
	Identifier    count
	Add
	Identifier    count
	Integer       1
}
 