Skip to content

Latest commit

 

History

History
76 lines (61 loc) · 3.3 KB

README.md

File metadata and controls

76 lines (61 loc) · 3.3 KB

Note

Currently being rewritten in C++ at https://github.com/ianayl/compiler

Experimental Interpreter

A toy programming language meant as a way to study interpreters and how to write them. This is purely a hobby project and is intended as a means to develop the skills necessary to eventually write a general purpose programming language.

Currently, it supports:

  • Arithmetic operations with numbers
  • Setting and referencing variables
  • Currently working on function calls

Detailed overview

As of now, the language is a basic REPL interpreter that:

  • Uses a recursive-descent parser that parses LL(2) grammar
  • A basic tree-walk evaluator is used to evaluate AST's generated by the parser
  • Variables are stored in a dynamically-resized hashmap with conflicts resolved using separate chaining -- This will eventually have to change in the future to accommodate for pointers
  • A rather messy lexer that will need to be cleaned up in the future

To learn more details about the current functional state of the language, refer to it's EBNF grammar: current_grammar.md

Goals checklist:

Eventually I want to hit all of these checkpoints:

  • Basic lexer
  • Clean up lexer, lex using a FSM implemented as a table instead
  • A LL(1) LL(2) Parser
    • Parse basic arithmetic (numbers, +*(), etc.)
    • Parse extended symbols (-/^%)
    • Generates concrete syntax trees
    • Generates abstract syntax trees
    • Integrate lexer into the parser
  • Evaluates concrete abstract syntax trees
  • Variables
    • Implement a hashmap
    • Write and parse grammar for variables
    • Rework the hashmaps to support pointers in the future -- use a heap combined with the hashmap
  • Interaction
    • Add an interactive shell mode
    • Add ability to read from file
  • Functions
    • Introduce function object type: A list of AST's basically
    • Introduce scoping
      • "Scopes" via a parent pointer tree of activation records (each containing it's own heap)
      • Associating each function call (scope/activation record) with it's own activation record in the parent-pointer tree
  • Garbage collector
    • Reference counting GC maybe?
    • Actual, proper bicolored GC (or maybe even tricolored...)
  • Control flows, loops, etc
    • Introduce booleans
    • Introduce basic boolean expressions
    • Introduce if
    • Introduce while
    • Introduce for
  • More data types
    • Consider: integers and bitwise operations
      • Also consider: making integers the default data type again
    • Introduce structs
    • Introduce lists
    • Hashmap exists, might as well make a dictionary too
  • Clean up output so debug information can be toggled
  • Basic code generation -- moving away from interpreters

Note to self:

  • Review eval.c and ast_parser.c; they're scuffed and TODO's are building up

  • Review hashmap.c after implementing garbage collector

    • Btw: consider implementing a garbage collector soon
    • Be sure to reconsider hashmap's freeing behavior after
    • Consider that one day you will need to need to implement pointers: You will then need to implement the variables on a heap instead.