Ace compiler

ace_compiler. rb

=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***"