Expression Language Interpreter

Project roadmap

1. 01

   Define the language

   ~2h

   Write LANGUAGE.md: the syntax (let x = 1; assignment; +, -, *, / and %; comparisons and and, or and not; if and else; while; fn name(params) { ... }; return; print(...)), the value types (numbers, booleans, strings and functions), the rules for scopes, and example programs (FizzBuzz, factorial and fibonacci) with their expected output. Write the grammar in a simple notation. Set up a CMake project with Boost (for Program_options). Done when: LANGUAGE.md fully defines the language with examples.

2. 02

   Scan the source

   ~1.5h

   Write a scanner that turns source text into tokens (numbers, strings with escapes, names, keywords, operators and punctuation), each with its line and column, skipping whitespace and comments. Report unknown characters and unterminated strings with their position. Done when: unit tests show each example program scans into the right tokens.

3. 03

   Parse into a syntax tree

   ~3h

   Write a recursive descent parser following the grammar, with one function per precedence level for expressions, building a syntax tree of expression and statement nodes (with std::unique_ptr or std::variant). On a syntax error, report the line, column and what was expected (such as expected ')' after arguments), and recover to the next statement so several errors can be reported at once. Done when: the example programs parse, and broken programs give clear errors with positions.

4. 04

   Evaluate expressions and statements

   ~2.5h

   Write a tree-walking evaluator with values as a std::variant, and environments as a chain of scopes (each with a map of names and a pointer to the enclosing scope). Implement expressions, variables, assignment, if, while and print, with runtime errors (undefined variable, wrong types for an operator and division by zero) reported with the position. Done when: programs using variables, loops and conditions produce the expected output.

5. 05

   Add functions

   ~2.5h

   Implement function definitions (capturing the scope they were defined in, so they're closures), calls with argument count checks, return (for example using an exception or a special result to unwind), and recursion with a depth limit that reports stack overflow instead of crashing. Add a few built-in functions (such as len, str and clock). Done when: factorial, fibonacci and a closure-based counter all work.

6. 06

   Build the command line and prompt

   ~1h

   Run a file given as an argument (with Boost.Program_options for options such as --tokens and --ast, which print the tokens or syntax tree for debugging), or start an interactive prompt that keeps variables between lines and shows errors without exiting. Done when: files run, the prompt works, and the debug options print useful output.

7. 07

   Test it

   ~2h

   Write tests (with GoogleTest or Catch2) for the scanner, parser and evaluator, plus a folder of test programs with their expected output (including error messages with positions) that a test runner compares automatically. Run the tests with AddressSanitizer. Done when: all tests pass with no sanitizer errors.

Resources

• DocsCrafting Interpreters (free book)
• Docsstd::variant (cppreference)
• Docsstd::unique_ptr (cppreference)
• DocsBoost.Program_options tutorial
• DocsGoogleTest primer