From f952851e6962a7f8e2e05c46756b815e3ebac76b Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Fri, 24 Apr 2020 17:42:27 -0400 Subject: [PATCH] experimented with one-pass code generation and started to overhaul dyn.rb with a two-pass generation assuming immutable bindings and values --- dyn.rb | 83 +++++++++++--------------- dyn.src | 59 ++++++++++--------- dyn2.rb | 178 ++++++++++++++++++++++---------------------------------- 3 files changed, 131 insertions(+), 189 deletions(-) diff --git a/dyn.rb b/dyn.rb index ccac77b..b94d519 100755 --- a/dyn.rb +++ b/dyn.rb @@ -126,17 +126,16 @@ class Parser :byte => { prefix: :constant, infix: nil, level: :none }, } - Def = Struct.new(:name, :value) - Func = Struct.new(:args, :body) - Call = Struct.new(:func, :args) - IfExpr = Struct.new(:cond, :br1, :br2) + Val = Struct.new(:loc, :type, :value) + Def = Struct.new(:loc, :name, :value) + Func = Struct.new(:loc, :args, :body) + Call = Struct.new(:loc, :func, :args) + IfExpr = Struct.new(:loc, :cond, :br1, :br2) def initialize(path) @lex = Lexer.new(path) @prev = nil @next = nil - @name = nil - @symbols = {} end def toplevel() @@ -145,13 +144,13 @@ class Parser while !matches(:eof) expr = expression() if expr.is_a? Def - defs << expr.name - exprs << Call.new(:set!, [expr.name, expr.value]) + pp expr + exprs << Call.new(expr.loc, :set!, [expr.name, expr.value]) else exprs << expr; end end - [defs, exprs] + exprs end ####################################### @@ -195,7 +194,7 @@ class Parser end def assign(left) - Call.new(:set!, [left, expression()]) + Call.new(location(), :set!, [left, expression()]) end def variable() @@ -203,6 +202,7 @@ class Parser end def definition() + loc = location() name = expect(:ident).text.to_sym expr = nil if (matches("(")) @@ -211,10 +211,11 @@ class Parser expect("=") expr = expression() end - Def.new(name, expr) + Def.new(loc, name, expr) end def function() + loc = location() args = [] exprs = [] expect("(") @@ -227,32 +228,32 @@ class Parser exprs << expression() end expect(:end) - Func.new(args, exprs) + Func.new(loc, args, exprs) end def constant() if (@prev.type == :num) - @prev.text.to_f + Val.new(location(), :num, @prev.text.to_f) elsif (@prev.type == :string) - @prev.text + Val.new(location(), :string, @prev.text) elsif (@prev.type == :nil) - nil + Val.new(location(), :nil, nil) elsif (@prev.type == :bool) - (@prev.text == "true") + Val.new(location(), :bool, (@prev.text == "true")) elsif (@prev.type == "[") - ary = [] + ary = Val.new(location(), :array, []) while !matches("]") - ary << expression() + ary.value << expression() expect(",") if !matches("]") end expect("]") ary elsif (@prev.type == "{") - hsh = {} + hsh = Val.new(location(), :hash, []) while !matches("}") - name = expect(:ident).text - expect("=") - hsh[name] = expression() + key = expression() + expect(":") + hsh.value << [key, expression()] expect(",") if !matches("}") end expect("}") @@ -268,18 +269,8 @@ class Parser ast end -# def ufcs_call(left) -# # TODO: UFCS call doesnt seem right or well thought out here... -# access = Call.new(:get!, [left, expect(:ident).text]) -# if accept("(") -# func_call(access, left) -# else -# access -# end -# end - def func_call(ast, first_arg=nil) - call = Call.new(ast, []) + call = Call.new(location(), ast, []) call.args << first_arg if not first_arg.nil? while !matches(")") call.args << expression() @@ -290,15 +281,15 @@ class Parser end def unary() - Call.new(@prev.type, [parseLevel(:unary)]) + Call.new(location(), @prev.type, [parseLevel(:unary)]) end def binary(left) - Call.new(@prev.type, [left, parseLevel(nextLevel(@prev.type))]) + Call.new(location(), @prev.type, [left, parseLevel(nextLevel(@prev.type))]) end def if_expr() - expr = IfExpr.new(nil, [], []) + expr = IfExpr.new(location(), nil, [], []) expr.cond = expression() expr.br1 = if_body() if accept(:else) @@ -363,6 +354,10 @@ class Parser def eof? (peek().type == :eof) end + + def location() + [@prev.file, @prev.pos] + end end @@ -408,17 +403,5 @@ end parse = Parser.new("dyn.src") -defs, exprs = parse.toplevel - -puts "Value " + (defs.join(", ")) + ";" -puts "void toplevel(void) {" -exprs.each do |e| - puts Emit.expr(e) -# puts e -# if (e.is_a? Parser::Call) -# Emit.call(e) -# else -# puts e -# end -end -puts "}" +exprs = parse.toplevel +pp exprs diff --git a/dyn.src b/dyn.src index 58983d8..4b596af 100644 --- a/dyn.src +++ b/dyn.src @@ -1,34 +1,35 @@ -#[1,2,3] +# constants +[1,2,3] +{ "foo": 123 } +nil +true +false +123 +123.0 +"foo" -#{ "foo": 123 } -#123 = foo -#foo = 1 -##{} -#true -#false -#123 -#123.0 -#"foo" -#nil -#(456 + 1) -#(456 - 1) -#(456 * 1) -#(456 - 1) -# -#let foo = 123 -#foo = 42 -# -#if 1 -# 2 -#else -# 3 -#end -# -#println("foo!") -#print(1,2,3,4,5,6,7,8,9) -#(-1) -#(+1) +# operators +let a = (456 + 1) +let a = (456 - 1) +let a = (456 * 1) +let a = (456 - 1) +let a = (-1) +let a = (+1) +# variables +let foo = 123 +foo = 42 + +# conditionals +if (1) + 2 +else + 3 +end + +# functions and application +println("foo!") +print(1,2,3,4,5,6,7,8,9) let foo = fun(a) println("hi!") end diff --git a/dyn2.rb b/dyn2.rb index aeb2d54..bdc215d 100755 --- a/dyn2.rb +++ b/dyn2.rb @@ -88,44 +88,46 @@ end class Codegen def initialize() + @funcs = [] + @syms = Symtable.new() @protos = StringIO.new - @funcs = {} - @func_stack = [] @func_id = 0 @temp_id = 0 end + def dump(file=$stdout) + protos = StringIO.new + bodies = StringIO.new + @funcs.each do |name| + val = @syms[name] + protos.puts "Value #{name}(#{val[:args].join(", ")});" + bodies.puts "Value #{name}(#{val[:args].join(", ")}) {" + val[:body].each do |i| + bodies.puts " #{i[0]} = #{i[1]} #{i[2]}#{i[3].nil? ? "" : ", " + i[3].to_s}" + end + bodies.puts "}" + end + file.puts protos.string + file.puts bodies.string + end -# def emit_line(str) -# @func_stack.last.puts str -# end -# -# def emit(str) -# @func_stack.last.print str -# end -# -# def emit_expr(expr) -# v = get_tempvar() -# emit_line " Value #{v} = #{expr};" -# v -# end -# -# def dump(file=$stdout) -# file.puts @protos.string -# @funcs.each {|f| file.puts f.string } -# end -# -# def func_start() -# io = StringIO.new -# @syms.scope_start -# @funcs.push(io) -# @func_stack.push(io) -# end -# -# def func_stop -# @syms.scope_stop() -# @func_stack.pop() -# end + def func_start(name, args) + @syms[name.to_sym] = { kind: :func, args: args, body: [] } + @funcs << name.to_sym + @body = [] + @syms.scope_start + args.each {|a| @syms[a.to_sym] = { kind: :arg } } + end + + def func_stop + @syms.scope_stop() + @syms[@funcs.last][:body] = @body + end + + def emit(op, left, right = nil) + @body << [mkvar, op, left, right] + @body.last + end private @@ -182,6 +184,7 @@ class Parser def initialize(path) @lex = Lexer.new(path) @syms = Symtable.new() + @gen = Codegen.new() @prev = nil @next = nil @protos = StringIO.new @@ -264,15 +267,12 @@ class Parser end def toplevel() - func_start() - emit_line "Value toplevel(void) {" - expr = emit_expr "NULL" + @gen.func_start("toplevel", []) + expr = emit :nil, nil while !matches(:eof) expr = expression() end - emit_line " return #{expr};" - emit_line "}" - func_stop() + @gen.func_stop end ####################################### @@ -286,83 +286,70 @@ class Parser if (left.to_s.start_with? "__tmp") error("invalid expression on left-hand side of assignment") end - emit_line " #{left} = #{expression()};" - left.to_s + emit :assign, left[0], expression()[0] end def variable() - @prev.text.to_sym + [@prev.text.to_sym] end def definition() name = expect(:ident).text.to_sym expect("=") - emit_line " Value #{name} = #{expression()};" - name + emit :def, name, expression()[0] end def function() # TODO: fix this! - func_start() - name = func_args() +# func_start() + name = "__anonfunc" + func_args() result = nil while (!matches(:end)) result = expression() end - emit_line " return #{result};" - emit_line "}" expect(:end) - func_stop() - emit_expr "MKFUNC(#{name})" +# func_stop() +# emit_expr "MKFUNC(#{name})" + [name] end def func_args() - @func_id += 1 - name = "__anon_func#{@func_id}" - @protos.print "static Value #{name}(" - emit "static Value #{name}(" expect("(") while (!matches(")")) arg = expect(:ident).text @syms[arg] = :arg - @protos.print "Value #{arg}" - emit "Value #{arg}" if not matches(")") - @protos.print ", " - emit ", " expect(",") end end - @protos.puts(");") - emit_line ") {" expect(")") - name end def constant() if (@prev.type == :num) - emit_expr("MKNUM(#{@prev.text.to_f})") + emit :float, @prev.text.to_f elsif (@prev.type == :string) - emit_expr("MKSTR(#{@prev.text})") + emit :string, @prev.text elsif (@prev.type == :nil) - emit_expr("NULL") + emit :nil, nil, nil elsif (@prev.type == :bool) - emit_expr("MKBOOL(#{@prev.text == "true"})") + emit :bool, (@prev.text == "true") elsif (@prev.type == "[") - array = emit_expr "MKARRAY()" + array = (emit :array, 0)[0] while !matches("]") elem = expression() - emit_line " ARRAY_APPEND(#{array}, #{elem})" + emit :append, array, elem[0] expect(",") if !matches("]") end expect("]") array elsif (@prev.type == "{") - hash = emit_expr "MKHASH()" + hash = (emit :hash, 0)[0] while !matches("}") - name = expression() + key = expression()[0] expect(":") - expr = expression() - emit_line " HASH_SET(#{hash}, #{name}, #{expr})" + expr = expression()[0] + emit :insert, key, expr expect(",") if !matches("}") end expect("}") @@ -386,18 +373,18 @@ class Parser end expect(")") if args.length > 8 - emit_expr("CALLN(#{func}, #{args.length}, #{args.join(", ")})") +# emit_expr("CALLN(#{func}, #{args.length}, #{args.join(", ")})") else - emit_expr("CALL#{args.length}(#{func}, #{args.join(", ")})") +# emit_expr("CALL#{args.length}(#{func}, #{args.join(", ")})") end end def unary() case @prev.type when "+" - emit_expr("OP_POS(#{parseLevel(:unary)})") + emit :pos, parseLevel(:unary)[0] when "-" - emit_expr("OP_NEG(#{parseLevel(:unary)})") + emit :neg, parseLevel(:unary)[0] else error("invalid binary operator #{op.type.inspect}") end @@ -408,13 +395,13 @@ class Parser right = parseLevel(nextLevel(op.type)) case op.type when "+" - emit_expr("OP_ADD(#{left}, #{right})") + emit :add, left[0], right[0] when "-" - emit_expr("OP_SUB(#{left}, #{right})") + emit :sub, left[0], right[0] when "*" - emit_expr("OP_MUL(#{left}, #{right})") + emit :mul, left[0], right[0] when "/" - emit_expr("OP_DIV(#{left}, #{right})") + emit :div, left[0], right[0] else error("invalid binary operator #{op.type.inspect}") end @@ -447,41 +434,12 @@ class Parser ####################################### # Code Generation Primitives ####################################### - def get_tempvar() - @tempvar = 0 if @tempvar.nil? - @tempvar += 1 - "__tmp#{@tempvar}" - end - - def emit_line(str) - @func_stack.last.puts str - end - - def emit(str) - @func_stack.last.print str - end - - def emit_expr(expr) - v = get_tempvar() - emit_line " Value #{v} = #{expr};" - v + def emit(op, left, right = nil) + @gen.emit(op, left, right) end def dump(file=$stdout) - file.puts @protos.string - @funcs.each {|f| file.puts f.string } - end - - def func_start() - io = StringIO.new - @syms.scope_start - @funcs.push(io) - @func_stack.push(io) - end - - def func_stop - @syms.scope_stop() - @func_stack.pop() + @gen.dump(file) end end -- 2.52.0