Compiler/code generator: Difference between revisions
Content added Content deleted
Line 3,724: | Line 3,724: | ||
65 halt |
65 halt |
||
</pre > |
</pre > |
||
=={{header|Nim}}== |
|||
{lang Nim}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)</lang> |
|||
{{out}} |
|||
The code produced is compliant with the specification and can be executed by the virtual machine interpreter. |
|||
Example with ASCII Mandelbrot (https://rosettacode.org/wiki/Compiler/Sample_programs#Ascii_Mandlebrot). |
|||
<pre>Datasize: 15 Strings: 0 |
|||
0 push 420 |
|||
5 neg |
|||
6 store [0] |
|||
11 push 300 |
|||
16 store [1] |
|||
21 push 300 |
|||
26 store [2] |
|||
31 push 300 |
|||
36 neg |
|||
37 store [3] |
|||
42 push 7 |
|||
47 store [4] |
|||
52 push 15 |
|||
57 store [5] |
|||
62 push 200 |
|||
67 store [6] |
|||
72 fetch [2] |
|||
77 store [7] |
|||
82 fetch [7] |
|||
87 fetch [3] |
|||
92 gt |
|||
93 jz (329) 423 |
|||
98 fetch [0] |
|||
103 store [8] |
|||
108 fetch [8] |
|||
113 fetch [1] |
|||
118 lt |
|||
119 jz (276) 396 |
|||
124 push 0 |
|||
129 store [9] |
|||
134 push 0 |
|||
139 store [10] |
|||
144 push 32 |
|||
149 store [11] |
|||
154 push 0 |
|||
159 store [12] |
|||
164 fetch [12] |
|||
169 fetch [6] |
|||
174 lt |
|||
175 jz (193) 369 |
|||
180 fetch [10] |
|||
185 fetch [10] |
|||
190 mul |
|||
191 push 200 |
|||
196 div |
|||
197 store [13] |
|||
202 fetch [9] |
|||
207 fetch [9] |
|||
212 mul |
|||
213 push 200 |
|||
218 div |
|||
219 store [14] |
|||
224 fetch [13] |
|||
229 fetch [14] |
|||
234 add |
|||
235 push 800 |
|||
240 gt |
|||
241 jz (56) 298 |
|||
246 push 48 |
|||
251 fetch [12] |
|||
256 add |
|||
257 store [11] |
|||
262 fetch [12] |
|||
267 push 9 |
|||
272 gt |
|||
273 jz (14) 288 |
|||
278 push 64 |
|||
283 store [11] |
|||
288 fetch [6] |
|||
293 store [12] |
|||
298 fetch [10] |
|||
303 fetch [9] |
|||
308 mul |
|||
309 push 100 |
|||
314 div |
|||
315 fetch [7] |
|||
320 add |
|||
321 store [9] |
|||
326 fetch [13] |
|||
331 fetch [14] |
|||
336 sub |
|||
337 fetch [8] |
|||
342 add |
|||
343 store [10] |
|||
348 fetch [12] |
|||
353 push 1 |
|||
358 add |
|||
359 store [12] |
|||
364 jmp (-201) 164 |
|||
369 fetch [11] |
|||
374 prtc |
|||
375 fetch [8] |
|||
380 fetch [4] |
|||
385 add |
|||
386 store [8] |
|||
391 jmp (-284) 108 |
|||
396 push 10 |
|||
401 prtc |
|||
402 fetch [7] |
|||
407 fetch [5] |
|||
412 sub |
|||
413 store [7] |
|||
418 jmp (-337) 82 |
|||
423 halt</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |