From 5012e2d56cbc9c897698cd5423f2dd8bd04fb34f Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Tue, 27 Dec 2022 22:08:42 -0500 Subject: [PATCH] added cerise compiler script --- build.sh | 2 + inputs/cerise.m | 49 ++++ inputs/sclpl.src | 35 +++ lib/cerise.rb | 564 +++++++++++++++++++++++++++++++++++++++ lib/{dyn.rb => sclpl.rb} | 194 +------------- lib/utils/anf.rb | 97 +++++++ lib/utils/base_lexer.rb | 28 ++ lib/utils/base_parser.rb | 82 ++++++ lib/utils/parser.rb | 2 + lib/utils/sym_table.rb | 102 +++++++ 10 files changed, 973 insertions(+), 182 deletions(-) create mode 100755 build.sh create mode 100644 inputs/cerise.m create mode 100644 inputs/sclpl.src create mode 100755 lib/cerise.rb rename lib/{dyn.rb => sclpl.rb} (86%) create mode 100644 lib/utils/anf.rb create mode 100644 lib/utils/base_lexer.rb create mode 100644 lib/utils/base_parser.rb create mode 100644 lib/utils/parser.rb create mode 100644 lib/utils/sym_table.rb diff --git a/build.sh b/build.sh new file mode 100755 index 0000000..22685a8 --- /dev/null +++ b/build.sh @@ -0,0 +1,2 @@ +#!/bin/sh +find -type f | entr -c ./lib/${1}.rb \ No newline at end of file diff --git a/inputs/cerise.m b/inputs/cerise.m new file mode 100644 index 0000000..f7f412a --- /dev/null +++ b/inputs/cerise.m @@ -0,0 +1,49 @@ +#a1 = 1 +#a2 = 1.0 +#a3 = "string" +#a4 = true + +#b1 : int +#b1 = 1.0 # error +#b2 : float +#b2 = 1 # error +#b3 : string +#b3 = 1 # error +#b4 : bool +#b4 = 1 # error + +#if true then 2 else 3 +#if true then 2 else 3.0 # error +#if true then 2.0 else 3 # error + + +# type variables and unused args + +# TODO: implement operator precedence +# TODO: desugar to ANF *after* typing + +foo = func(a) + let b = bar(a) in + let c = 123.0 + b in c + +bar = func(a) # TODO func type is wrong, for a + let b = 1.0 + a in b + + + +#bar : int -> int +#bar = func(a) +# 123 + + + +#foo = func(a, b) +# let bar = foo(a, b) in +# bar + + +#let bar : int -> int -> int = func(a,b) +# if 1 then 2 else 3 +# +#let setter : int -> void = func(a) +# set! value = 4 diff --git a/inputs/sclpl.src b/inputs/sclpl.src new file mode 100644 index 0000000..d5e9337 --- /dev/null +++ b/inputs/sclpl.src @@ -0,0 +1,35 @@ +123 +123.0 +"" +true +false + +a = 123 +b = (123 < 321) +c = (if (123 < 1) 1 else 2) + +if (123 < 1) { + 123.0 +} else { + 321 +} + +somefunc : int -> int +somefunc = func(a) { + 42 +} +d = somefunc(42) + +foo : int -> int +foo = func(b) { + d = 123 + bar : int -> int + bar = func(c) { + a + b + c + } + bar(1) + d + e = 1 + e + d +} diff --git a/lib/cerise.rb b/lib/cerise.rb new file mode 100755 index 0000000..3bebdc2 --- /dev/null +++ b/lib/cerise.rb @@ -0,0 +1,564 @@ +#!/usr/bin/env ruby +require 'stringio' +require_relative "utils/base_lexer" +require_relative "utils/base_parser" +require_relative "utils/anf" + +class Lexer < BaseLexer + SPACE = /([ \t\v\n\r]+|#.*\n)/ + IDENT = /[_a-zA-Z][_a-zA-Z0-9]*!?/ + BRACES = /[\(\)\[\]\{\}\.]/ + OPERATORS = /[:,<>*\/=+\-\$?!]+/ + INTEGER = /[0-9]+/ + FLOATING = /[0-9]+\.[0-9]+/ + STRING = /"(\\"|[^"])*"/ + ID_TYPES = { + "true" => :bool, + "false" => :bool, + "if" => :if, + "then" => :then, + "else" => :else, + "end" => :end, + "let" => :let, + "func" => :func, + "in" => :in, + "set!" => :set, + } + + def next + while @data.skip(SPACE) do + end + if not @data.eos? + type = :eof + if @data.scan(IDENT) + type = (ID_TYPES[@data.matched] || :ident) + elsif @data.scan(FLOATING) + type = :float + elsif @data.scan(INTEGER) + type = :int + elsif @data.scan(STRING) + type = :string + elsif @data.scan(BRACES) + type = @data.matched + elsif @data.scan(OPERATORS) + type = @data.matched + end + Tok.new(@data.matched, @file, @data.pos, type) if type + else + Tok.new("EOF", @file, @data.pos, :eof) + end + end +end + +class TypeChecker + UnaryOps = { + "+" => { + int: [:int, :int], + float: [:float, :float], + }, + "-" => { + int: [:int, :int], + float: [:float, :float], + }, + "!" => { + bool: [:bool, :bool] + }, + } + + BinaryOps = { + "+" => { + int: [:int, :int, :int], + float: [:float, :float, :float], + }, + "-" => { + int: [:int, :int, :int], + float: [:float, :float, :float], + }, + "*" => { + int: [:int, :int, :int], + float: [:float, :float, :float], + }, + "/" => { + int: [:int, :int, :int], + float: [:float, :float, :float], + }, + "%" => { + int: [:int, :int, :int], + float: [:float, :float, :float], + }, + "<" => { + int: [:int, :int, :bool], + float: [:float, :float, :bool], + }, + ">" => { + int: [:int, :int, :bool], + float: [:float, :float, :bool], + }, + "<=" => { + int: [:int, :int, :bool], + float: [:float, :float, :bool], + }, + ">=" => { + int: [:int, :int, :bool], + float: [:float, :float, :bool], + }, + "==" => { + int: [:int, :int, :bool], + float: [:float, :float, :bool], + string: [:string, :string, :bool], + }, + "!=" => { + int: [:int, :int, :bool], + float: [:float, :float, :bool], + string: [:string, :string, :bool], + }, + "&&" => { bool: [:bool, :bool, :bool] }, + "||" => { bool: [:bool, :bool, :bool] }, + "<<" => { int: [:int, :int, :int] }, + ">>" => { int: [:int, :int, :int] }, + "&" => { int: [:int, :int, :int] }, + "^" => { int: [:int, :int, :int] }, + "|" => { int: [:int, :int, :int] }, + } + + def initialize(parser) + @parser = parser + end + + def error(loc, msg) + @parser.error(msg, loc) + end + + def check(env, expr, type) + if (expr.is_a? ANF::If) + check_ifexpr(env, expr, type) +# elsif (expr.is_a? ANF::Func) +# check_func(env, expr, type) + elsif (expr.is_a? ANF::Var) + check_var(env, expr, type) + elsif (expr.is_a? ANF::Let) + check_let(env, expr, type) + else + etype = infer(env, expr) + if type != etype + error(expr.loc, "expected #{type}, received #{etype}") + end + end + expr.type = type + end + + def infer(env, expr) + if expr.is_a? ANF::Const + infer_const(env, expr) + elsif expr.is_a? ANF::Var + infer_var(env, expr) + elsif expr.is_a? ANF::Let + infer_let(env, expr) + elsif expr.is_a? ANF::If + infer_ifexpr(env, expr) + elsif expr.is_a? ANF::Set + infer_set(env, expr) + elsif expr.is_a? ANF::Func + infer_func(env, expr) + elsif expr.is_a? ANF::Apply + infer_apply(env, expr) + else + error(expr.loc, "unable to determine type of expression") + end + end + + private + + def make_typevar() + @typevar ||= 0 + var = "abcdefghijklmnopqrstuvwxyz"[@typevar] + @typevar += 1 + var + end + + def var?(expr) + expr.class == ANF::Var + end + + def untyped_global_func?(env, func, type) + type.nil? and + var?(func) and + env.global?(func.name) and + env[func.name][:value] + end + + def check_apply(env, expr, type) + # Handle global functions that haven't been typed yet but are + # being called. We pause to infer them. This probably causes + # a loop on recursive functions. Break that later. + if untyped_global_func?(env, expr.func, type) + value = env[expr.func.name][:value] + env[expr.func.name][:value] = nil + infer(@parser.syms, value) + type = infer(env, expr.func) + + pp "CHECK_APPLY", expr.func.name, type, expr.func, value + end + + error(expr.loc, "object being applied is not a function (has type: #{type.to_s})") if not type.is_a? Array + error(expr.loc, "wrong number of arguments to function call") if (type.length - 1) != expr.args.length + type[0..-2].each_with_index do |t,i| + check(env, expr.args[i], t) + end + expr.type = type.last + end + + def check_ifexpr(env, expr, type) + check(env, expr.cond, :bool) + check(env, expr.then, type) + check(env, expr.else, type) + end + + def check_var(env, expr, type) + etype = infer(env, expr) + if (etype.class == String) + expr.type = type + env.set_type(expr.name, type) + elsif expr.type != type + error(expr.loc, "expected #{type}, received #{etype}") + end + type + end + +# def check_func(env, expr, type) +# end + +# def check_let(env, expr, type) +# end + + def infer_const(env, expr) + expr.type + end + + def infer_var(env, expr) + if not env.defined?(expr.name) + error(expr.loc, "symbol '#{expr.name}' not defined") + end + expr.type = env[expr.name][:type] + end + + def infer_let(env, let) + if let.body.nil? + infer_decl(env, let) + else + infer_let_expr(env, let) + end + end + + def infer_decl(env, let) + env = env.clone + + # handle the binding + if let.var.type + check(env, let.expr, let.var.type) + else + let.var.type = infer(env, let.expr) + end + + env.set_type(let.var.name, let.var.type) + env[let.var.name][:value] = nil + let.type = :void + end + + def infer_let_expr(env, let) + env = env.clone + + # handle the binding + if let.var.type + check(env, let.expr, let.var.type) + else + let.var.type = infer(env, let.expr) + end + + env.add_sym(let.var.name, let.var.loc, :var, let.var.type) + let.type = infer(env, let.body) + end + + def infer_ifexpr(env, expr) + check(env, expr, infer(env, expr.then)) + end + + def infer_set(env, expr) + error(expr.loc, "infer_set unimplemented") + end + + def infer_func(env, expr) + env = env.clone + @typevar = 0 + expr.args.each do |a| + a.type ||= make_typevar() + env.add_sym(a.name, a.loc, :arg, a.type) + end + infer(env, expr.expr) + type = (expr.args + [expr.expr]).map {|v| v.type } + type.unshift(:void) if type.length == 1 + + # the body may have inferred an arg type, fix it up here + expr.args.each_with_index do |a,i| + a.type = env[a.name][:type] + type[i] = a.type + end + expr.type = type + end + + def infer_apply(env, expr) + if expr.func.is_a? String + expr.type = infer_opcall(env, expr) + else + type = infer(env, expr.func) + check_apply(env, expr, type) + end + end + + def assign_type(env, var, type) + if var.class == ANF::Var and (var.type.nil? or var.type == String) then + var.type = type + env[var.name][:type] = type + end + end + + def infer_opcall(env, expr) + # infer the operand type first + vtype = infer(env, expr.args[0]) + if (not vtype or vtype.class == String) and expr.args.length == 2 + vtype = infer(env, expr.args[1]) + end + + # use the operand type to pick op type and check it + if expr.args.length == 1 + optype = UnaryOps[expr.func][vtype] + error(expr.loc, "unknown unary operation '#{expr.func}' for operand type #{vtype}") if not optype + check_apply(env, expr, optype) + elsif expr.args.length == 2 + infer_binary(env, expr, vtype) + else + error(expr.loc, "too many operands for operator '#{expr.func}'") + end + end + + def infer_unary(env, expr, vtype) + end + + def infer_binary(env, expr, vtype) + optype = BinaryOps[expr.func][vtype] + error(expr.loc, "unknown binary operation '#{expr.func}' for operand type #{vtype}") if optype.nil? + + expr.args.each_with_index do |a, i| + assign_type(env, a, optype[i]) + end + check_apply(env, expr, optype) + end +end + + +class Parser < BaseParser + attr_accessor :exprs + + def toplevel + @type_checker = TypeChecker.new(self) + @exprs = [] + while !matches(:eof) + decl = declaration() + if decl.class == ANF::Let + syms[decl.var.name][:value] = decl + end + @exprs << decl + end + @exprs = @exprs.compact + @exprs.each do |e| + @type_checker.infer(syms, e) + end + pp syms + end + + def declaration() + if matches(:ident) + expr = ident() + expr.type = syms[expr.name][:type] if syms[expr.name] + if accept("=") + value = expression() + syms.add_sym(expr.name, expr.loc, :var, expr.type) + ANF::Let.new(expr.loc, nil, expr, value, nil) + elsif accept(":") + expr.type = type_spec() + syms.add_sym(expr.name, expr.loc, :var, expr.type) + nil + else + expression() + end + else + expression() + end + end + + def expression() + if matches(:let) + let_expr() + else + complex_expr() + end + end + + def complex_expr() + expr = nil + if matches(:if) + expr = if_expr() + elsif matches(:set) + expr = var_set() + else + expr = atomic_expr() + if matches("(") + expr = func_call(expr) + elsif operator? + expr = operator_call(expr) + end + end + expr + end + + def atomic_expr() + if matches(:func) + func_expr() + elsif matches(:ident) + ident() + else + constant() + end + end + + + + + def application() +# expr = atomic_expr() +# expr = func_call(expr) if matches("(") + # EQ, NEQ, '<', LTEQ, '>', GTEQ + end + + def simple_expr() + # '+', '-', OR + end + + def term() + # '*', '/', '%', AND + end + + def factor() + # '(', NOT, atomic + end + + + + + + OPERATORS = { + "+" => true, + "-" => true, + "*" => true, + "/" => true, + "%" => true, + } + + def operator? + OPERATORS[peek().type] + end + + def operator_call(expr) + op = consume() + rhs = atomic_expr() + ANF::Apply.new(expr.loc, nil, op.type, [expr, rhs]) + end + + + + def if_expr() + loc = expect(:if).pos + cond = atomic_expr() + expect(:then) + branch1 = expression() + expect(:else) + branch2 = expression() + ANF::If.new(loc, nil, cond, branch1, branch2) + end + + def var_set() + loc = expect(:set).pos + name = ident() + expect("=") + expr = expression() + ANF::Set.new(loc, nil, name, expr) + end + + def func_call(func) + args = [] + expect("(") + while !matches(")") + args << atomic_expr() + expect(",") if not matches(")") + end + expect(")") + ANF::Apply.new(func.loc, nil, func, args) + end + + def func_expr() + loc = expect(:func).pos + args = [] + expect("(") + while !matches(")") + args << ident() + expect(",") if not matches(")") + end + expect(")") + body = expression() + ANF::Func.new(loc, nil, args, body) + end + + def ident() + name = expect(:ident) + ANF::Var.new(name.pos, nil, name.text.to_sym) + end + + def constant() + tok = consume() + if tok.type == :bool + ANF::Const.new(tok.pos, :bool, tok.text == "true") + elsif tok.type == :string + ANF::Const.new(tok.pos, :string, tok.text) + elsif tok.type == :int + ANF::Const.new(tok.pos, :int, tok.text.to_i) + elsif tok.type == :float + ANF::Const.new(tok.pos, :float, tok.text.to_f) + elsif tok.type == :void + ANF::Const.new(tok.pos, :void, :void) + else + error("invalid constant") + end + end + + def let_expr() + expect(:let) + name = ident() + type = type_spec() if accept(":") + expect("=") + expr = complex_expr() + expect(:in) + body = expression() + ANF::Let.new(name.loc, nil, name, expr, body) + end + + def type_spec() + type = [ident().name] + while accept("->") + type << ident().name + end + (type.length == 1 ? type[0] : type) + end +end + +parser = Parser.new("inputs/cerise.m") +pp parser.syms diff --git a/lib/dyn.rb b/lib/sclpl.rb similarity index 86% rename from lib/dyn.rb rename to lib/sclpl.rb index 34d06ec..ed2b90e 100755 --- a/lib/dyn.rb +++ b/lib/sclpl.rb @@ -14,103 +14,26 @@ # byte # intset -require 'strscan' +require 'stringio' +require_relative "utils/sym_table" +require_relative "utils/base_lexer" +require_relative "utils/base_parser" $debug = false def error(loc, msg) if loc[0] == "" - raise ":0: error: #{msg}" + $stderr.puts ":0:#{loc[1]}: error: #{msg}" else lines = File.read(loc[0])[0..(loc[1])].split("\n") $stderr.puts "#{loc[0]}:#{lines.length}: error: #{msg}" - raise "" if $debug # $stderr.puts "#{lines.last}" # $stderr.puts (" " * lines.last.length) + "^" end -# exit 1 + exit 1 end -class SymTable < Hash - attr_accessor :type - attr_accessor :freevars - - def initialize(parent = nil) - @parent = (parent || {}) - @freevars = {} - end - - def clone(type = :block) - s = SymTable.new(self) - s.type = type - s - end - - def [](key) - (super(key) || @parent[key]) - end - - def local(key) - method(:[]).super_method.call(key) - end - - def defined_ever?(key) - (not (self[key] || {})[:type].nil?) - end - - def defined_locally?(key) - (not (local(key) || {})[:type].nil?) - end - - def block_local?(key) - (not local(key).nil?) - end - - def global?(key) - if @parent.class == Hash - block_local?(key) - elsif block_local? key - false - else - @parent.global? key - end - end - - def local?(key) - if @parent.class == Hash - false - elsif @type == :func - block_local? key - else - @parent.local? key - end - end - - def free?(key) - (defined_ever? key) and (not local? key) and (not global? key) - end - - def merge!(env) - env.each {|k,v| self[k] = v } - end - - def annotate(key, type) - self[key] ||= {} - self[key][:ann] = type - end - - def annotation(key) - (method(:[]).super_method.call(key) || {})[:ann] - end - - def stack() - parent = (@parent.is_a?(SymTable) ? @parent.stack : []) - ([self] + parent).flatten - end -end - -class Lexer - Tok = Struct.new(:text, :file, :pos, :type) +class Lexer < BaseLexer SPACE = /([ \t\v\n\r]+|#.*\n)/ IDENT = /[_a-zA-Z][_a-zA-Z0-9]*/ BRACES = /[\(\)\[\]\{\}\.]/ @@ -128,32 +51,13 @@ class Lexer "func" => :fun, } - attr_accessor :file - attr_accessor :data - - def initialize(path = nil) - @file = (path || "") - @text = (path ? File.read(path) : "") - @data = StringScanner.new(@text) - end - - def parse_string(str) - @file = "" - @text = str - @data = StringScanner.new(@text) - end - - def get_id_type(str) - ID_TYPES[str] || :ident - end - def next while @data.skip(SPACE) do end if not @data.eos? type = :eof if @data.scan(IDENT) - type = get_id_type(@data.matched) + type = (ID_TYPES[@data.matched] || :ident) elsif @data.scan(FLOATING) type = :float elsif @data.scan(INTEGER) @@ -170,13 +74,9 @@ class Lexer Tok.new("EOF", @file, @data.pos, :eof) end end - - def linenum(pos = nil) - @text[0..(pos || @data.pos)].count("\n") + 1 - end end -class Parser +class Parser < BaseParser LEVELS = { none: 0, assign: 1, @@ -253,23 +153,6 @@ class Parser Ann = Struct.new(:loc, :type, :expr) Block = Struct.new(:loc, :type, :exprs) - def initialize(path = nil) - parse_file(path) - end - - def parse_string(str) - @lex = Lexer.new() - @lex.parse_string(str) - @prev = nil - @next = nil - toplevel - end - - def parse_file(path) - @lex = Lexer.new(path) - @prev = nil - @next = nil - end ####################################### # Parsing Rules @@ -423,60 +306,6 @@ class Parser expr.br2 = (matches("{") ? block() : expression()) expr end - - ####################################### - # Parsing Primitives - ####################################### - def error(str, loc = nil) - file, pos = (loc ? loc : [@lex.file, (@next || @prev).pos]) - raise "#{file}:#{@lex.linenum(pos)}: #{str}" -# puts "#{file}:#{@lex.linenum(pos)}: #{str}" -# raise "" if $debug -# exit 1 - end - - def peek() - @next = @lex.next if @next.nil? - @next - end - - def matches(type) - (peek().type == type) - end - - def accept(type) - if (matches(type)) - @prev = @next - @next = nil - true - else - false - end - end - - def expect(type) - tok = peek() - if not accept(type) - error("expected '#{type}', received '#{tok.type}'") - end - tok - end - - def consume() - expect(peek().type) - end - - def eof? - (peek().type == :eof) - end - - def location() - if @prev - [@prev.file, @prev.pos] - else - [@lex.file, 0] - end - end end module TypeChecker @@ -729,7 +558,6 @@ class Codegen name end - def emit_toplevel(block) out = StringIO.new out.puts "void toplevel(void)" @@ -888,7 +716,7 @@ b = (123 < 321) c = (if (123 < 1) 1 else 2) if (123 < 1) { - 123 + 123.0 } else { 321 } @@ -919,8 +747,10 @@ eos #syms[:a] = {} #pp syms.global? :a +tree = Parser.new("inputs/sclpl.src") tree = Parser.new.parse_string(STRING) TypeChecker.infer_block(SymTable.new, tree, false) +pp tree puts <<-eos #include diff --git a/lib/utils/anf.rb b/lib/utils/anf.rb new file mode 100644 index 0000000..471351a --- /dev/null +++ b/lib/utils/anf.rb @@ -0,0 +1,97 @@ +# Extended A-Normal Form Lambda Calculus +# +# = ... +# +# = (let ) +# | +# +# = (func ( ...) ) +# | +# | +# | +# | +# | (void) +# +# = ( ...) +# | (if ) +# | (set! ) +# +# = (let ([ ]) ) +# | +# | + +module ANF + Const = Struct.new(:loc, :type, :value) + Var = Struct.new(:loc, :type, :name) + Let = Struct.new(:loc, :type, :var, :expr, :body) + If = Struct.new(:loc, :type, :cond, :then, :else) + Set = Struct.new(:loc, :type, :var, :expr) + Func = Struct.new(:loc, :type, :args, :expr) + Apply = Struct.new(:loc, :type, :func, :args) + + def self.check_atomic(expr) + case expr.class + when Const + when Var + when Func + return + else + raise "not ANF compliant" + end + end + + def self.check_complex(expr) + case expr.class + when Apply + when If + when Set + return + else + raise "not ANF compliant" + end + end + + def self.check(expr) + case expr.class + when Let + check_let(expr) + when If + check_if(expr) + when Set + check_set(expr) + when Func + check_func(expr) + when Apply + check_apply(expr) + end + end + + def self.check_let(expr) + if not expr.body + check(expr.value) + else + check_complex(expr.value) + check(expr.body) + end + end + + def self.check_if(expr) + check_atomic(expr.cond) + check(expr.then) + check(expr.else) + end + + def self.check_set(expr) + check(expr.expr) + end + + def self.check_func(expr) + check(expr.body) + end + + def self.check_apply(expr) + ([expr.func] + expr.args).each do |e| + check_atomic(e) + end + end +end diff --git a/lib/utils/base_lexer.rb b/lib/utils/base_lexer.rb new file mode 100644 index 0000000..e4e8616 --- /dev/null +++ b/lib/utils/base_lexer.rb @@ -0,0 +1,28 @@ +require 'strscan' + +class BaseLexer + Tok = Struct.new(:text, :file, :pos, :type) + + attr_accessor :file + attr_accessor :data + + def initialize(path = nil) + @file = (path || "") + @text = (path ? File.read(path) : "") + @data = StringScanner.new(@text) + end + + def parse_string(str) + @file = "" + @text = str + @data = StringScanner.new(@text) + end + + def linenum(pos = nil) + @text[0..(pos || @data.pos)].count("\n") + 1 + end + + def next() + raise "next() must be implemented by inheriting class" + end +end \ No newline at end of file diff --git a/lib/utils/base_parser.rb b/lib/utils/base_parser.rb new file mode 100644 index 0000000..23b8784 --- /dev/null +++ b/lib/utils/base_parser.rb @@ -0,0 +1,82 @@ +require_relative "sym_table" + +class BaseParser + attr_accessor :syms + + def initialize(path = nil) + @syms = SymTable.new + parse_file(path) + end + + def parse_string(str) + @lex = Lexer.new() + @lex.parse_string(str) + @prev = nil + @next = nil + toplevel + end + + def parse_file(path) + @lex = Lexer.new(path) + @prev = nil + @next = nil + toplevel + end + + def toplevel + raise "toplevel() must be implemented by inheriting class" + end + + def error(str, loc = nil) + file, pos = (loc ? [@lex.file, loc] : [@lex.file, (@next || @prev).pos]) + $stderr.puts "#{file}:#{@lex.linenum(pos)}: #{str}" + exit 1 + end + + def peek() + @next = @lex.next if @next.nil? + @next + end + + def matches(type) + (peek().type == type) + end + + def matches_any(types) + types.any? {|type| peek().type == type } + end + + def accept(type) + if (matches(type)) + @prev = @next + @next = nil + true + else + false + end + end + + def expect(type) + tok = peek() + if not accept(type) + error("expected '#{type}', received '#{tok.type}'") + end + tok + end + + def consume() + expect(peek().type) + end + + def eof? + (peek().type == :eof) + end + + def location() + if @prev + [@prev.file, @prev.pos] + else + [@lex.file, 0] + end + end +end \ No newline at end of file diff --git a/lib/utils/parser.rb b/lib/utils/parser.rb new file mode 100644 index 0000000..0604ce2 --- /dev/null +++ b/lib/utils/parser.rb @@ -0,0 +1,2 @@ +class Parser +end diff --git a/lib/utils/sym_table.rb b/lib/utils/sym_table.rb new file mode 100644 index 0000000..711ef27 --- /dev/null +++ b/lib/utils/sym_table.rb @@ -0,0 +1,102 @@ +class SymTable < Hash + def initialize(parent = nil) + @global_scope = true if not parent.nil? + @parent = (parent || {}) + end + + def clone() + SymTable.new(self) + end + + def [](key) + (super(key) || @parent[key]) + end + + def defined?(key) + not self[key].nil? + end + + def typed?(key) + not (self[key] || {})[:type].nil? + end + + def add_sym(name, loc, kind, type = nil) + self[name] = { + loc: loc, + kind: kind, + type: type + } + end + + def set_type(name, type) + (self[name] || {})[:type] = type + end + + def global?(name) + if self[name] + @global_scope + elsif @parent.class == SymTable + @parent.global?(name) + else + nil + end + end + +# def local(key) +# method(:[]).super_method.call(key) +# end +# +# def defined_ever?(key) +# (not (self[key] || {})[:type].nil?) +# end +# +# def defined_locally?(key) +# (not (local(key) || {})[:type].nil?) +# end +# +# def block_local?(key) +# (not local(key).nil?) +# end +# +# def global?(key) +# if @parent.class == Hash +# block_local?(key) +# elsif block_local? key +# false +# else +# @parent.global? key +# end +# end +# +# def local?(key) +# if @parent.class == Hash +# false +# elsif @type == :func +# block_local? key +# else +# @parent.local? key +# end +# end +# +# def free?(key) +# (defined_ever? key) and (not local? key) and (not global? key) +# end +# +# def merge!(env) +# env.each {|k,v| self[k] = v } +# end +# +# def annotate(key, type) +# self[key] ||= {} +# self[key][:ann] = type +# end +# +# def annotation(key) +# (method(:[]).super_method.call(key) || {})[:ann] +# end +# +# def stack() +# parent = (@parent.is_a?(SymTable) ? @parent.stack : []) +# ([self] + parent).flatten +# end +end -- 2.49.0