From feaf41400fd9f84f7957764a24a78d4835e71145 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Tue, 23 Jun 2020 16:36:22 -0400 Subject: [PATCH] updated parser syntax and AST nodes in preparation for type checking implementation --- dyn.rb | 363 ++++++++++++++++++++++++++++++++------------------------ dyn.src | 56 +++++---- 2 files changed, 238 insertions(+), 181 deletions(-) diff --git a/dyn.rb b/dyn.rb index cb4aec7..a696cfa 100755 --- a/dyn.rb +++ b/dyn.rb @@ -2,37 +2,12 @@ require 'strscan' -BuiltinSyms = {} - -class Symtable - def initialize - @builtins = BuiltinSyms - @scopes = [{}] - end - - def []=(k,v) - @scopes.last[k] = v - end - - def [](k) - (@scopes.map{|h| h[k] }.compact.last || BuiltinSyms[k]) - end - - def scope_start - @scopes.push({}) - end - - def scope_stop - @scopes.pop() - end -end - class Lexer Tok = Struct.new(:text, :file, :pos, :type) SPACE = /([ \t\v\n\r]+|#.*\n)/ IDENT = /[_a-zA-Z][_a-zA-Z0-9]*/ BRACES = /[\(\)\[\]\{\}\.]/ - OPERATORS = /[*\/=+-:\$?]/ + OPERATORS = /[:,<>*\/=+\-\$?]+/ NUMBER = /[0-9]+(\.[0-9]+)?/ STRING = /"(\\"|[^"])*"/ ID_TYPES = { @@ -105,30 +80,33 @@ class Parser LVLNAMES = LEVELS.keys RULES = { - "(" => { prefix: :grouping, infix: :func_call, level: :call }, - "+" => { prefix: :unary, infix: :binary, level: :term }, - "-" => { prefix: :unary, infix: :binary, level: :term }, - "*" => { prefix: nil, infix: :binary, level: :factor }, - "/" => { prefix: nil, infix: :binary, level: :factor }, - "=" => { prefix: nil, infix: :definition, level: :assign }, - :fun => { prefix: :function, infix: nil, level: :none }, - :if => { prefix: :if_expr, infix: nil, level: :none }, - :ident => { prefix: :variable, infix: nil, level: :none }, - "[" => { prefix: :constant, infix: :subscript, level: :call }, - "{" => { prefix: :constant, infix: nil, level: :none }, - :nil => { prefix: :constant, infix: nil, level: :none }, - :bool => { prefix: :constant, infix: nil, level: :none }, - :num => { prefix: :constant, infix: nil, level: :none }, - :string => { prefix: :constant, infix: nil, level: :none }, - :char => { prefix: :constant, infix: nil, level: :none }, - :byte => { prefix: :constant, infix: nil, level: :none }, + ":" => { prefix: nil, infix: :annotation, level: :primary }, + "(" => { prefix: :grouping, infix: :func_call, level: :call }, + "+" => { prefix: :unary, infix: :binary, level: :term }, + "-" => { prefix: :unary, infix: :binary, level: :term }, + "*" => { prefix: nil, infix: :binary, level: :factor }, + "/" => { prefix: nil, infix: :binary, level: :factor }, + "=" => { prefix: nil, infix: :definition, level: :assign }, + :fun => { prefix: :function, infix: nil, level: :none }, + :if => { prefix: :if_expr, infix: nil, level: :none }, + :ident => { prefix: :variable, infix: nil, level: :none }, + "[" => { prefix: :constant, infix: :subscript, level: :call }, + "{" => { prefix: :constant, infix: nil, level: :none }, + :nil => { prefix: :constant, infix: nil, level: :none }, + :bool => { prefix: :constant, infix: nil, level: :none }, + :num => { prefix: :constant, infix: nil, level: :none }, + :string => { prefix: :constant, infix: nil, level: :none }, + :char => { prefix: :constant, infix: nil, level: :none }, + :byte => { prefix: :constant, infix: nil, level: :none }, } - 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) + Val = Struct.new(:loc, :type, :value) + Def = Struct.new(:loc, :type, :name, :value) + Func = Struct.new(:loc, :type, :args, :body) + Call = Struct.new(:loc, :type, :func, :args) + IfExpr = Struct.new(:loc, :type, :cond, :br1, :br2) + Ann = Struct.new(:loc, :type, :expr) + Block = Struct.new(:loc, :type, :syms, :exprs) def initialize(path) @lex = Lexer.new(path) @@ -140,19 +118,33 @@ class Parser # Parsing Rules ####################################### def toplevel() - defs = {} + block(true) + end + + def block(toplevel = false) + block = Block.new(location(), nil, {}, []) + syms = {} exprs = [] - while !matches(:eof) + expect("{") if not toplevel + while !matches(:eof) and !matches("}") expr = expression() if expr.is_a? Def - error("global symbol '#{expr.name}' multiply defined") if defs[expr.name] - defs[expr.name] = expr.loc + error("symbol '#{expr.name}' multiply defined in scope", expr.loc) if syms[expr.name] and syms[expr.name][:loc] + syms[expr.name] ||= {} + syms[expr.name][:loc] = expr.loc exprs << Call.new(expr.loc, :set!, [expr.name, expr.value]) + elsif expr.is_a? Ann and expr.expr.class == Symbol + error("symbol '#{expr.expr}' multiply annotated in scope", expr.loc) if syms[expr.expr] and syms[expr.expr][:type] + syms[expr.expr] ||= {} + syms[expr.expr][:type] = expr.type else exprs << expr; end end - [defs, exprs] + expect("}") if not toplevel + block.syms = syms + block.exprs = exprs + block end def expression() @@ -197,9 +189,10 @@ class Parser end def definition(name) + error("invalid identifier for definition") if name.class != Symbol loc = location() expr = expression() - Def.new(loc, name, expr) + Def.new(loc, nil, name, expr) end def function() @@ -212,11 +205,7 @@ class Parser expect(",") if not matches(")") end expect(")") - while (!matches(:end)) - exprs << expression() - end - expect(:end) - Func.new(loc, args, exprs) + Func.new(loc, nil, args, block()) end def constant() @@ -228,24 +217,6 @@ class Parser Val.new(location(), :nil, nil) elsif (@prev.type == :bool) Val.new(location(), :bool, (@prev.text == "true")) - elsif (@prev.type == "[") - ary = Val.new(location(), :array, []) - while !matches("]") - ary.value << expression() - expect(",") if !matches("]") - end - expect("]") - ary - elsif (@prev.type == "{") - hsh = Val.new(location(), :hash, []) - while !matches("}") - key = expression() - expect(":") - hsh.value << [key, expression()] - expect(",") if !matches("}") - end - expect("}") - hsh else error("not a valid constant") end @@ -258,7 +229,7 @@ class Parser end def func_call(ast, first_arg=nil) - call = Call.new(location(), ast, []) + call = Call.new(location(), nil, ast, []) call.args << first_arg if not first_arg.nil? while !matches(")") call.args << expression() @@ -268,36 +239,57 @@ class Parser call end + def annotation(ast) + Ann.new(location(), type_name(), ast) + end + + def type_name() + type = expect(:ident).text.to_sym + if peek().text == "->" then + type = [type] + while peek().text == "->" + consume() + type << expect(:ident).text.to_sym + end + end + type + end + def unary() - Call.new(location(), @prev.type, [parseLevel(:unary)]) + Call.new(location(), nil, @prev.type, [parseLevel(:unary)]) end def binary(left) - Call.new(location(), @prev.type, [left, parseLevel(nextLevel(@prev.type))]) + Call.new(location(), nil, @prev.type, [left, parseLevel(nextLevel(@prev.type))]) end def if_expr() - expr = IfExpr.new(location(), nil, [], []) + expr = IfExpr.new(location(), nil, nil, [], []) expr.cond = expression() - expr.br1 = if_body() - if accept(:else) - if accept(:if) - expr.br2 = if_expr() - else - expr.br2 = if_body() - expect(:end) - end - end + expr.br1 = (matches("{") ? block() : expression()) + expect(:else) + expr.br2 = (matches("{") ? block() : expression()) expr +# expr.br1 = if_body() +# if accept(:else) +# if accept(:if) +# expr.br2 = if_expr() +# else +# expr.br2 = if_body() +# expect(:end) +# end +# end +# expr end def if_body() - block = [expression()] - while (!matches(:else) && !matches(:end)) - block << expression() - end - (matches(:else) || matches(:end)) - block +# # TODO: call block here to parse the if expression... +# block = [ matches("{") ? block() : expression()] +## while (!matches(:else) && !matches(:end)) +## block << expression() +## end +## (matches(:else) || matches(:end)) +# block end ####################################### @@ -345,81 +337,136 @@ class Parser end def location() - [@prev.file, @prev.pos] + if @prev + [@prev.file, @prev.pos] + else + [@lex.file, 0] + end end end -class CodeGenerator - def initialize(defs, exprs) - @syms = Symtable.new - @funcs = { toplevel: { freevars: [], code: StringIO.new } } - @protos = StringIO.new - @protos.puts "Value #{defs.keys.join(", ")};" - exprs.each {|e| emit(e) } +module TypeChecker + def self.check(env, expr, type) end - def mkvar() - @id = 0 if @id.nil? - @id++ - "_tmp#{@id}" + def self.infer(env, expr) end +end - def emitop(op, left, right = nil) - @body << [mkvar, op, left, right] - @body.last - end - def func_start(name, args = []) - args.each {|a| @syms[a] = :arg } - @syms[name] = :func - @syms.scope_start - @funcs[name.to_sym] = { freevars: [], code: StringIO.new } - end - def func_stop() - @syms.scope_stop - end - def dump - #pp @syms - puts @protos.string - end - def emit(e) - if e.is_a? Parser::Val - emit_val(e) - elsif e.is_a? Parser::Def - puts "Def" - elsif e.is_a? Parser::Call - puts "Call" - elsif e.is_a? Parser::IfExpr - puts "IfExpr" - elsif e.is_a? Parser::Func - puts "Func" - end - end - def emit_val(e) - case e.type - when :nil - puts "NULL" - when :bool - puts e.value - when :num - puts e.value - when :string - puts e.value - end - end -end + + + + + + + + + + + + + + + + + + +#BuiltinSyms = {} +# +#class Symtable +# def initialize +# @builtins = BuiltinSyms +# @scopes = [{}] +# end +# +# def []=(k,v) +# @scopes.last[k] = v +# end +# +# def [](k) +# (@scopes.map{|h| h[k] }.compact.last || BuiltinSyms[k]) +# end +# +# def scope_start +# @scopes.push({}) +# end +# +# def scope_stop +# @scopes.pop() +# end +#end +# +#class CodeGenerator +# def initialize(defs, exprs) +# @syms = Symtable.new +# @funcs = { toplevel: { freevars: [], code: StringIO.new } } +# @protos = StringIO.new +# @protos.puts "Value #{defs.keys.join(", ")};" +# exprs.each {|e| emit(e) } +# end +# +# def mkvar() +# @id = 0 if @id.nil? +# @id++ +# "_tmp#{@id}" +# end +# +# def emitop(op, left, right = nil) +# @body << [mkvar, op, left, right] +# @body.last +# end +# +# def func_start(name, args = []) +# args.each {|a| @syms[a] = :arg } +# @syms[name] = :func +# @syms.scope_start +# @funcs[name.to_sym] = { freevars: [], code: StringIO.new } +# end +# +# def func_stop() +# @syms.scope_stop +# end +# +# def dump +# #pp @syms +# puts @protos.string +# end +# +# def emit(e) +# if e.is_a? Parser::Val +# emit_val(e) +# elsif e.is_a? Parser::Def +# puts "Def" +# elsif e.is_a? Parser::Call +# puts "Call" +# elsif e.is_a? Parser::IfExpr +# puts "IfExpr" +# elsif e.is_a? Parser::Func +# puts "Func" +# end +# end +# +# def emit_val(e) +# case e.type +# when :nil +# puts "NULL" +# when :bool +# puts e.value +# when :num +# puts e.value +# when :string +# puts e.value +# end +# end +#end parse = Parser.new("dyn.src") -defs, exprs = parse.toplevel +block = Parser.new("dyn.src").toplevel -# Print the definition prototypes -#puts "Value #{defs.keys.join(", ")};" -#puts exprs +pp block -#puts exprs -gen = CodeGenerator.new(defs, exprs) -gen.dump diff --git a/dyn.src b/dyn.src index 999310b..c7d7885 100644 --- a/dyn.src +++ b/dyn.src @@ -6,29 +6,39 @@ false 123.0 "foo" a = 1 +#b = [1,2,3] +#{ "foo": 123, foo: 24 } -#[1,2,3] -#{ "foo": 123, 42: 24 } -# -## operators -#a = (456 + 1) -#b = (456 - 1) -#c = (456 * 1) -#d = (456 - 1) -#e = (-1) -#f = (+1) -# -## conditionals -#if (1) -# 2 -#else -# 3 -#end -# -## functions and application -#println("foo!") -#print(1,2,3,4,5,6,7,8,9) +# operators +a1 = (456 + 1) +b = (456 - 1) +c = (456 * 1) +d = (456 - 1) +e = (-1) +f = (+1) -foo1 = fun(a) +# conditionals +if (1) { + 2 +} else if (1) { + asd + asd + 21 +} else { + 1 +} + + +# functions and application +println("foo!") +print(1,2,3,4,5,6,7,8,9) + +foo1 : int -> int +foo1 = fun(a) { + b = 123 println("hi!") -end +} + +# TODO: +# * Get rid of end keyword +# * Replace with single or multi-expression blocks -- 2.52.0