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.