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

import os, re, streams, strformat, strutils, tables, std/decls
 
type
 
  # AST node types.
  NodeKind = enum
             nIdentifier = "Identifier"
             nString = "String"
             nInteger = "Integer"
             nSequence = "Sequence"
             nIf = "If"
             nPrtc = "Prtc"
             nPrts = "Prts"
             nPrti = "Prti"
             nWhile = "While"
             nAssign = "Assign"
             nNegate = "Negate"
             nNot = "Not"
             nMultiply = "Multiply"
             nDivide = "Divide"
             nMod = "Mod"
             nAdd = "Add"
             nSubtract = "Subtract"
             nLess = "Less"
             nLessEqual = "LessEqual"
             nGreater = "Greater"
             nGreaterEqual = "GreaterEqual"
             nEqual = "Equal"
             nNotEqual = "NotEqual"
             nAnd = "And"
             nOr = "Or"
 
  # Ast node description.
  Node = ref object
    left: Node
    right: Node
    case kind: NodeKind
    of nString: stringVal: string
    of nInteger: intVal: int
    of nIdentifier: name: string
    else: nil
 
  # Virtual machine opcodes.
  OpCode = enum
           opFetch = "fetch"
           opStore = "store"
           opPush = "push"
           opJmp = "jmp"
           opJz = "jz"
           opAdd = "add"
           opSub = "sub"
           opMul = "mul"
           opDiv = "div"
           opMod = "mod"
           opLt = "lt"
           opgt = "gt"
           opLe = "le"
           opGe = "ge"
           opEq = "eq"
           opNe = "ne"
           opAnd = "and"
           opOr = "or"
           opNeg = "neg"
           opNot = "not"
           opPrtc = "prtc"
           opPrti = "prti"
           opPrts = "prts"
           opHalt = "halt"
           opInvalid = "invalid"
 
  # Code generator context.
  CodeGen = object
    address: int              # Current address in code part.
    instr: seq[string]        # List of instructions.
    vars: Table[string, int]  # Mapping variable name -> variable index.
    strings: seq[string]      # List of strings.
 
  # Node ranges.
  UnaryOpNode = range[nNegate..nNot]
  BinaryOpNode = range[nMultiply..nOr]
  PrintNode = range[nPrtc..nPrti]
 
 
const
 
  # Mapping unary operator Node -> OpCode.
  UnOp: array[UnaryOpNode, OpCode] = [opNeg, opNot]
 
  # Mapping binary operator Node -> OpCode.
  BinOp: array[BinaryOpNode, OpCode] = [opMul, opDiv, opMod, opAdd, opSub, opLt,
                                        opLe, opGt, opGe, opEq, opNe, opAnd, opOr]
 
  # Mapping print Node -> OpCode.
  PrintOp: array[PrintNode, OpCode] = [opPrtc, opPrts, opPrti]
 
 
####################################################################################################
# Code generator.
 
proc genSimpleInst(gen: var CodeGen; opcode: OpCode) =
  ## Build a simple instruction (no operand).
  gen.instr.add &"{gen.address:>5} {opcode}"
 
#---------------------------------------------------------------------------------------------------
 
proc genMemInst(gen: var CodeGen; opcode: OpCode; memIndex: int) =
  ## Build a memory access instruction (opFetch, opStore).
  gen.instr.add &"{gen.address:>5} {opcode:<5} [{memIndex}]"
 
#---------------------------------------------------------------------------------------------------
 
proc genJumpInst(gen: var CodeGen; opcode: OpCode): int =
  ## Build a jump instruction. We use the letters X and Y as placeholders
  ## for the offset and the target address.
  result = gen.instr.len
  gen.instr.add &"{gen.address:>5} {opcode:<5} (X) Y"
 
#---------------------------------------------------------------------------------------------------
 
proc genPush(gen: var CodeGen; value: int) =
  ## Build a push instruction.
  gen.instr.add &"{gen.address:>5} {opPush:<5} {value}"
 
#---------------------------------------------------------------------------------------------------
 
proc updateJumpInst(gen: var CodeGen; index: int; jumpAddress, targetAddress: int) =
  ## Update the offset and the target address of a jump instruction.
 
  var instr {.byAddr.} = gen.instr[index]
  let offset = targetAddress - jumpAddress - 1
  for idx in countdown(instr.high, 0):
    case instr[idx]
    of 'Y':
      instr[idx..idx] = $targetAddress
    of 'X':
      instr[idx..idx] = $offset
      break
    else:
      discard
 
#---------------------------------------------------------------------------------------------------
 
proc process(gen: var CodeGen; node: Node) =
  ## Generate code for a node.
 
  if node.isNil: return
 
  case node.kind:
 
  of nInteger:
    gen.genPush(node.intVal)
    inc gen.address, 5
 
  of nIdentifier:
    if node.name notin gen.vars:
      gen.vars[node.name] = gen.vars.len
    gen.genMemInst(opFetch, gen.vars[node.name])
    inc gen.address, 5
 
  of nString:
    var index = gen.strings.find(node.stringVal)
    if index < 0:
      index = gen.strings.len
      gen.strings.add(node.stringVal)
    gen.genPush(index)
    inc gen.address, 5
 
  of nAssign:
    gen.process(node.right)
    if node.left.name notin gen.vars:
      gen.vars[node.left.name] = gen.vars.len
    gen.genMemInst(opStore, gen.vars[node.left.name])
    inc gen.address, 5
 
  of UnaryOpNode.low..UnaryOpNode.high:
    gen.process(node.left)
    gen.genSimpleInst(UnOp[node.kind])
    inc gen.address
 
  of BinaryOpNode.low..BinaryOpNode.high:
    gen.process(node.left)
    gen.process(node.right)
    gen.genSimpleInst(BinOp[node.kind])
    inc gen.address
 
  of PrintNode.low..PrintNode.high:
    gen.process(node.left)
    gen.genSimpleInst(PrintOp[node.kind])
    inc gen.address
 
  of nIf:
    # Generate condition expression.
    gen.process(node.left)
    # Generate jump if zero.
    let jzAddr = gen.address
    let jzInst = gen.genJumpInst(opJz)
    inc gen.address, 5
    # Generate then branch expression.
    gen.process(node.right.left)
    # If there is an "else" clause, generate unconditional jump
    var jmpAddr, jmpInst: int
    let hasElseClause = not node.right.right.isNil
    if hasElseClause:
      jmpAddr = gen.address
      jmpInst = gen.genJumpInst(opJmp)
      inc gen.address, 5
    # Update JZ offset.
    gen.updateJumpInst(jzInst, jzAddr, gen.address)
    # Generate else expression.
    if hasElseClause:
      gen.process(node.right.right)
      # Update JMP offset.
      gen.updateJumpInst(jmpInst, jmpAddr, gen.address)
 
  of nWhile:
    let condAddr = gen.address
    # Generate condition expression.
    gen.process(node.left)
    # Generate jump if zero.
    let jzAddr = gen.address
    let jzInst = gen.genJumpInst(opJz)
    inc gen.address, 5
    # Generate loop code.
    gen.process(node.right)
    # Generate unconditional jump.
    let jmpAddr = gen.address
    let jmpInst = gen.genJumpInst(opJmp)
    inc gen.address, 5
    # Update JMP offset.
    gen.updateJumpInst(jmpInst, jmpAddr, condAddr)
    # Update JZ offset.
    gen.updateJumpInst(jzInst, jzAddr, gen.address)
 
  of nSequence:
    gen.process(node.left)
    gen.process(node.right)
 
#---------------------------------------------------------------------------------------------------
 
proc run(gen: var CodeGen; ast: Node) =
  ## Run the code generator on the AST.
 
  # Process recursively the nodes.
  gen.process(ast)
  gen.genSimpleInst(opHalt)   # Add a Halt operator at the end.
 
  # Output header.
  echo &"Datasize: {gen.vars.len} Strings: {gen.strings.len}"
  # Output strings.
  for s in gen.strings:
    echo s.escape().replace("\\x0A", "\\n")
  # Output code.
  for inst in gen.instr:
    echo inst
 
####################################################################################################
# AST loader.
 
proc newNode(kind: NodeKind; left: Node; right: Node = nil): Node =
  ## Create a new node with given left and right children.
  result = Node(kind: kind, left: left, right: right)
 
#---------------------------------------------------------------------------------------------------
 
proc loadAst(stream: Stream): Node =
  ## Load a linear AST and build a binary tree.
 
  let line = stream.readLine().strip()
  if line.startsWith(';'):
    return nil
 
  var fields = line.split(' ', 1)
  let kind = parseEnum[NodeKind](fields[0])
  if kind in {nIdentifier, nString, nInteger}:
    if fields.len < 2:
      raise newException(ValueError, "Missing value field for " & fields[0])
    else:
      fields[1] = fields[1].strip()
  case kind
  of nIdentifier:
    return Node(kind: nIdentifier, name: fields[1])
  of nString:
    let str = fields[1].replacef(re"([^\\])(\\n)", "$1\n").replace(r"\\", r"\").replace("\"", "")
    return Node(kind: nString, stringVal: str)
  of nInteger:
    return Node(kind: nInteger, intVal: parseInt(fields[1]))
  else:
    if fields.len > 1:
      raise newException(ValueError, "Extra field for " & fields[0])
 
  let left = stream.loadAst()
  let right = stream.loadAst()
  result = newNode(kind, left, right)
 
 
#———————————————————————————————————————————————————————————————————————————————————————————————————
 
var stream: Stream
var toClose = false
var codegen: CodeGen
 
if paramCount() < 1:
  stream = newFileStream(stdin)
else:
  stream = newFileStream(paramStr(1))
  toClose = true
 
let ast = loadAst(stream)
if toClose: stream.close()
 
codegen.run(ast)