AR Programming Language & Interpreter

A custom programming language and its tree-walking interpreter implemented in C++ for DSA semester project.

Features

• Lexical Analysis: Tokenizer that converts source code into tokens
• Syntax Analysis: Recursive descent parser that builds an Abstract Syntax Tree (AST)
• Interpretation: Tree-walking interpreter that executes the AST
• Data Types: Numbers, strings, booleans, and null
• Variables: Dynamic variable declaration and assignment
• Functions: User-defined functions with parameters and return values
• Control Flow: if/else statements, while loops
• Operators: Arithmetic, comparison, logical, and assignment operators
• Built-in Functions: print for output

Grammar

program        → declaration* EOF ;
declaration    → funcDecl | varDecl | statement ;
funcDecl       → "func" IDENTIFIER "(" parameters? ")" block ;
varDecl        → "let" IDENTIFIER ( "=" expression )? ";" ;
statement      → exprStmt | printStmt | returnStmt | ifStmt | whileStmt | block ;
exprStmt       → expression ";" ;
printStmt      → "print" expression ";" ;
returnStmt     → "return" expression? ";" ;
ifStmt         → "if" "(" expression ")" statement ( "else" statement )? ;
whileStmt      → "while" "(" expression ")" statement ;
block          → "{" declaration* "}" ;
expression     → assignment ;
assignment     → IDENTIFIER "=" assignment | logic_or ;
logic_or       → logic_and ( "||" logic_and )* ;
logic_and      → equality ( "&&" equality )* ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" | "%" ) unary )* ;
unary          → ( "!" | "-" ) unary | call ;
call           → primary ( "(" arguments? ")" )* ;
primary        → NUMBER | STRING | "true" | "false" | "null" | IDENTIFIER | "(" expression ")" ;
parameters     → IDENTIFIER ( "," IDENTIFIER )* ;
arguments      → expression ( "," expression )* ;

Example Programs

Hello World

print "Hello, World!";

Variables and Arithmetic

let x = 10;
let y = 20;
let sum = x + y;
print "Sum: " + sum;

Functions

func fibonacci(n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

print fibonacci(10);

Control Flow

let count = 0;
while (count < 5) {
    print "Count: " + count;
    count = count + 1;
}

Conditional Statements

let age = 18;
if (age >= 18) {
    print "You are an adult";
} else {
    print "You are a minor";
}

Building and Running

Prerequisites

• C++17 or later
• A C++ compiler (g++, clang++, or MSVC)

Compilation

g++ -std=c++17 -o ar *.cpp

Usage

# Interactive mode
./ar

# Run a script file
./ar program.ar

# Show help
./ar --help

Architecture

Components

1. Lexer (lexer.h, lexer.cpp)

   • Tokenizes source code into meaningful tokens
   • Handles keywords, operators, literals, and identifiers
   • Supports string escaping and comments

2. Token (token.h, token.cpp)

   • Defines token types and token structure
   • Utility functions for token manipulation

3. AST (ast.h, ast.cpp)

   • Abstract Syntax Tree node definitions
   • Visitor pattern for tree traversal
   • Represents program structure hierarchically

4. Parser (parser.h, parser.cpp)

   • Recursive descent parser
   • Builds AST from token stream
   • Error handling and recovery

5. Interpreter (interpreter.h, interpreter.cpp)

   • Tree-walking interpreter
   • Environment for variable scoping
   • Runtime value representation using std::any

6. Main (main.cpp)

   • Command-line interface
   • File handling and interactive mode

Design Patterns Used

• Visitor Pattern: For AST traversal and interpretation
• Recursive Descent: For parsing expressions and statements
• Environment Chain: For variable scoping and function calls

Language Specification

Keywords

• let - Variable declaration
• func - Function declaration
• if, else - Conditional statements
• while - Loop statement
• return - Return from function
• true, false - Boolean literals
• null - Null value
• print - Print statement

Operators

• Arithmetic: +, -, *, /, %
• Comparison: ==, !=, <, <=, >, >=
• Logical: &&, ||, !
• Assignment: =

Data Types

• Numbers: Floating-point numbers (e.g., 42, 3.14)
• Strings: Text enclosed in double quotes (e.g., "Hello")
• Booleans: true or false
• Null: null value

Error Handling

The interpreter provides comprehensive error handling:

• Lexical Errors: Invalid characters or malformed tokens
• Syntax Errors: Grammar violations with line/column information
• Runtime Errors: Division by zero, undefined variables, type mismatches

Future Enhancements

• Arrays and indexing
• For loops
• Import/module system
• More built-in functions
• Object-oriented features
• Garbage collection
• Just-in-time compilation

Project Structure

DSA/
├── token.h           # Token definitions
├── token.cpp         # Token implementation
├── lexer.h           # Lexer interface
├── lexer.cpp         # Lexer implementation
├── ast.h             # AST node definitions
├── ast.cpp           # AST implementation
├── parser.h          # Parser interface
├── parser.cpp        # Parser implementation
├── interpreter.h     # Interpreter interface
├── interpreter.cpp   # Interpreter implementation
├── main.cpp          # Main program
└── README.md         # This file

Academic Context

This project demonstrates key concepts in:

• Compiler Design: Lexical analysis, syntax analysis, semantic analysis
• Data Structures: Trees (AST), Hash tables (symbol tables), Stacks (call stack)
• Algorithms: Recursive descent parsing, tree traversal, pattern matching
• Software Engineering: Modular design, error handling, testing

License

This project is created for educational purposes as part of a DSA semester project.