=begin The goal here is to build a very simple compiler, for a very simple language. We will have very simple constructs for now like def f(x,y) add(42, add(x,y)) end, which says in English, define a function f that takes 2 arguments (x,y) and returns the return value of add(42, add(x, y)). This could easily be much more complex, but I wanted to keep things simple for high level understanding. Feel free to expand on this in your own languages 😉

This code will consist of 3 main components: a lexer (or tokenizer), a parser, and a code generator.

Note that this code does NOT use the most efficient practices for compiler building, but rather the simplest approach for understanding purposes. 

The simple version of this compiles the code down to python. feel free to test it! 😎

While I do work in the system field, compiler design is not my area of expertise, and I referred to a number of written sources to put this together.

@uthor: Ace
Bugs: None known
Version:
20180505 - Lexer class added
20180515 - Lexer complete, begin Parser
20180520 - Parser complete, Start generation 
20180524 - CodeGen complete, code release

=end

class Lexer T_TYPES = [ [:define, /\bfun\b/], [:func_end, /\bend\b/], [:identifier, /\b[a-zA-Z]+\b/], [:integer, /\b[0-9]+\b/], [:oparan, /(/], [:cparan, /)/], [:comma, /\,/] ] def initialize(code) @code = code print "TEST CODE\n#{@code}\n\n" end

#This method is responsible for breaking #the code into the smallest meaningful #units possible def tokenize tokens = [] until @code.empty? tokens << getToken @code = @code.strip end tokens end

def getToken T_TYPES.each do |type, re| #make sure we get the true #beginning of the string re = /\A(#{re})/ #check for regex match if @code =~ re val = $1 @code = @code[val.length..-1] return Token.new(type, val) end end raise RuntimeError("Could not retrieve token for #{@code.inspect}") end end

Token = Struct.new(:type, :value)

Typically these tokens would be read from a

source file, but in an effort to keep

things simple, we won't worry about that

for now.

tokens = Lexer.new("fun f(x,y) add(42, add(x,y)) end").tokenize print "TESTING LEXER\n" print tokens.map(&:inspect).join("\n")

Tokenizer complete. Step 2 - Parse the tokens

class Parser #A parser translates the tokens into
#tree representing structure of the code def initialize(tokens) @tokens = tokens end

def parse
    defParse
end

def defParse 
    consume(:define)
    name = consume(:identifier).value 
    args = getArgs #could be 0 or more
    body = getBody #could be a complex expression
    DefNode.new(name, args, body)
end

def getArgs
    args = []
    consume(:oparan)
    #do we have argument(s)?
    if(peek(:identifier))
        args << consume(:identifier).value
        while(peek(:comma))
            consume(:comma)
            args << consume(:identifier).value
        end
    end
    consume(:cparan)
    args
end

def peek(expectedType, offset=0)
    @tokens.fetch(offset).type == expectedType
end

def getBody
    if peek(:integer)
        parseInt
    elsif peek(:identifier) && peek(:oparan, 1)
        parseCall
    else 
        parseVar
    end
end

def parseVar 
    VarNode.new(consume(:identifier).value)
end

def parseCall 
    name = consume(:identifier)
    exp = parseArgExp
    CallNode.new(name, exp)
end

def parseArgExp
    argExp  = []
    consume(:oparan)
    #do we have argument(s) or expression(s)?
    if(!peek(:cparan))
        argExp << parseExp
        while(peek(:comma))
            consume(:comma)
            argExp << parseExp
        end
    end
    consume(:cparan)
    argExp
end

def parseExp
#Expressions can be one of the following:
#1) Integers
#2) function calls
#3) variables
    if peek(:integer)
        parseInt 
    elsif peek(:identifier) && peek(:oparan, 1)
        parseCall 
    else
        parseVar 
    end
end

def parseInt 
    IntNode.new(consume(:integer).value.to_i)
end

def consume(expectedType)
    token = @tokens.shift
    if token.type == expectedType
        token 
    else
        raise RuntimeError.new("Expected #{expectedType} but received #{token.type}")
    end
end

end

DefNode = Struct.new(:name, :args, :body) IntNode = Struct.new(:value) CallNode = Struct.new(:name, :argExp) VarNode = Struct.new(:value)

tokenTree = Parser.new(tokens).parse puts "\n\n*TESTING PARSER*" print tokenTree.map(&:inspect).join("\n")

Parsing complete. Last is code generation

puts "\n\n*TESTING CODE GENERATOR*\n" class CodeGen def generate(node) case node when DefNode "def %s(%s):\n\treturn %s" % [node.name, node.args.join(","), generate(node.body) ] when CallNode "%s(%s)" % [node.name.value, node.argExp.map{ |exp| generate(exp) }.join(",")] when IntNode node.value when VarNode node.value else raise RuntimeError.new("Unexpected node type: #{node.class}") end end end

generated = CodeGen.new.generate(tokenTree) aux = "\n\ndef add(x,y):\n\treturn x+y \nprint(f(-1, -10))" print generated + aux puts "\n*TRY THIS GENERATED CODE IN PYTHON*"

Built With

• ruby-on-rails