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

require'format/printf'
 
(opcodes)=: opcodes=: ;:{{)n
 fetch store push add sub mul div mod lt gt le ge
 eq ne and or neg not jmp jz prtc prts prti halt
}}-.LF
 
(ndDisp)=: ndDisp=:;:{{)n
 Sequence Multiply Divide Mod Add Subtract Negate Less LessEqual Greater
 GreaterEqual Equal NotEqual Not And Or Prts Assign Prti x If x x x While
 x x Prtc x Identifier String Integer
}}-.LF
 
ndDisp,.ndOps=:;: {{)n
 x mul div mod add sub neg lt le gt ge eq ne not and or
 x x x x x x x x x x x x x x x x
}} -.LF
 
load_ast=: {{
  'node_types node_values'=: 2{.|:(({.,&<&<}.@}.)~ i.&' ');._2 y
  1{::0 load_ast ''
:
  node_type=. x{::node_types
  if. node_type-:,';' do. x;a: return.end.
  node_value=. x{::node_values
  if. -.''-:node_value do.x;<node_type make_leaf node_value return.end.
  'x left'=.(x+1) load_ast''
  'x right'=.(x+1) load_ast''
  x;<node_type make_node left right
}}
 
make_leaf=: ; 
make_node=: {{m;n;<y}}
typ=: 0&{::
val=: left=: 1&{::
right=: 2&{::
 
gen_code=: {{
  if.y-:'' do.'' return.end.
  V=. val y
  W=. ;2}.y
  select.op=.typ y
    case.'Integer'do.gen_int _".V [ gen_op push
    case.'String'do.gen_string V [ gen_op push
    case.'Identifier'do.gen_var V [ gen_op fetch
    case.'Assign'do.gen_var left V [ gen_op store [ gen_code W
    case.;:'Multiply Divide Mod Add Subtract Less LessEqual Greater GreaterEqual Equal NotEqual And Or'do.
      gen_op op [ gen_code W [ gen_code V
    case.;:'Not Negate'do.
      gen_op op [ gen_code V
    case.'If'do.
      p1=. gen_int 0 [ gen_op jz [ gen_code V
      gen_code left W
      if.#right W do.
        p2=. gen_int 0 [ gen_op jmp
        gen_code right W [ p1 patch #object
        p2 patch #object
      else.
        p1 patch #object
      end.
    case.'While'do.
      p1=. #object
      p2=. gen_int 0 [ gen_op jz [ gen_code V
      gen_int p1 [ gen_op jmp [ gen_code W
      p2 patch #object
    case.'Prtc'do.gen_op prtc [ gen_code V
    case.'Prti'do.gen_op prti [ gen_code V
    case.'Prts'do.gen_op prts [ gen_code V
    case.'Sequence'do.
      gen_code W [ gen_code V
    case.do.error'unknown node type ',typ y
  end.
}}
 
gen_op=:{{
   arg=. boxopen y
   if. -.arg e. opcodes do.
     arg=. (ndDisp i. arg){ndOps
   end.
   assert. arg e. opcodes
   object=: object,opcodes i.arg
}}
 
gen_int=:{{
   if.#$y do.num=. _ ".y
   else.num=. y end.
   r=. #object
   object=: object,(4#256)#:num
   r
}}
 
gen_string=: {{
   strings=:~.strings,<y
   gen_int strings i.<y
}}
 
gen_var=: {{
   vars=:~.vars,<y
   gen_int vars i.<y
}}
 
patch=: {{ #object=: ((4#256)#:y) (x+i.4)} object }}
error=: {{echo y throw.}}
getint=: _2147483648+4294967296|2147483648+256#.]
 
list_code=: {{
  r=.'Datasize: %d Strings: %d\n' sprintf vars;&#strings
  r=.r,;strings,each LF
  pc=. 0
  lim=.<:#object
  while.do.
    op=.(pc{object){::opcodes
    r=.r,'%5d %s'sprintf pc;op
    pc=. pc+1
    i=. getint (lim<.pc+i.4){object
    k=. 0
    select.op
      case.fetch;store do.k=.4[r=.r,' [%d]'sprintf i
      case.push do.k=.4[r=.r,'  %d'sprintf i
      case.jmp;jz do.k=.4[r=.r,'    (%d) %d'sprintf (i-pc);i
      case.halt do.r=.r,LF return.
    end.
    pc=.pc+k
    r=.r,LF
  end.
}}
 
gen=: {{
  object=:strings=:vars=:i.0
  gen_code load_ast y
  list_code gen_op halt
}}