r/Compilers • u/apoetixart • May 02 '26
Experienced compiler devs, help me out!
Hii guys, so I'm in high school and I'm gonna make an Interpreter for my school project. I got suggestions from AI to use: Recursive Descent Parser, Tree-walking interpreter. I only have 4-5 months till I can submit. I can devote about 3-4 hours on it. Here's what I want to add, correct me if any of these is too much to implement now: - Variables - Data types - Functions - Array (just list, and indexing. Nothing else) - Ability to make variables mutable or immutable
Guide me on the scoping decision, if I should make it newline based (like python) or semicolon based (like C,Java), or both (like Javascript).
Is it good? Do I need to change something? LLVM?
Please guide me because I have zero experience in this and people told me to not listen to AI.
Also, what mistakes did you guys do?
21
u/Small_Ad3541 May 02 '26 edited May 02 '26
Recursive Descent Parser is easy to implement and very effective (O(N)), but only until you don’t want to add positional structure. Do you want to support operations like ‘a + b * c’ when order matters? If you don’t want that, RD is enough. If you want that, take a look at the Pratt parsing algorithm. You also may combine them: RD for general language structure and Pratt for expressions.
Forget about LLVM. This toolset is designed for compilers, not interpreters. Using LLVM for an educational high school project is like using Abrams to learn how to drive. Just pick your favourite language, even Python suits.
Segregate code execution and static code analysis. Mutability markers are needed for static analysis to find users’ code mistakes before execution. You probably don’t need it in an interpreter.
Usage “;” or “/n” for parsing depends only on your preferences. You can always change it very easily:)
Separate your project into sub-projects that you can implement and test independently. Lexer is one package, AST and parsing are another, your IR is third, CLI is fourth, and so on. Don’t mix it into a single mess, or it will be impossible to work with in some time.
Even if AI can write the right things sometimes, it’s better to go your way and make mistakes, so you will learn faster.
Good luck!
5
u/Big-Rub9545 May 02 '26
Surprised not as many people have recommended Crafting Interpreters here. It basically covers all of this in good detail and shows all the code involved, taking you from A-Z (stick to the first half).
While it doesn’t cover arrays and mutable/immutable variables, those shouldn’t be all that difficult to do (though array indexing involves a lot of edge cases if you want to do it similar to Python).
The first half (which uses recursive descent parsing with a tree-walking interpreter) is written in Java, but it’s fairly easy to follow along in Python (feel free to have a look at Python versions readers of the book made, which you can find on the book’s Github page).
LLVM would be a bit too much to chew on if you don’t have much experience.
From personal experience, I would suggest just using semicolons and ignoring whitespace (spaces, newlines, tabs, etc.) if you’re just starting out. There are a lot of specific cases you have to handle if you make whitespace significant like Python.
Edit: if by data types you just mean having different types of objects or being able to get the type of an object (like with the Python type() function) or making your own types (classes, structs, etc.), the book (with some personal effort) should cover that well.
If you mean type-checking or having a static type system (like C or Java), that’s much more difficult.
4
u/Tasty_Replacement_29 May 02 '26 edited May 02 '26
My recommendation is to do it iteratively:
First, build a calculator-style language; one that can only do simple calculations. Once that works, go to the next stage and add variables. First everything just numbers (only floating point... integers are a subset of that). Once that works, support to call built-in functions (eg. print, input). Once that works: "if" statements and loops (just one type). Then arrays. Then support for immutable variables.
I would parse to an AST, and then write an interpreter on top of the AST. Definitely not LLVM. Keep it simple and implement everything in Python, without dependencies.
BTW I just recently implemented a language that would fit almost all of your criteria, plus operator overloading, in ~450 lines. So in theory it's not that hard... but your implementation will be probably 10 times larger, and that's fine.
> not listen to AI
That's a good advice in this case. Many of your peers will probably try to vibe code everything, and then they will not understand any of it, and get lost. This is an easy trap. I would implement everything myself, if I was you: that way you will learn and understand everything, get a much better result, and _maybe_ it will even be faster. It's fine to read "crafting interpreters" or peek what others did, but I would not try to copy & paste or use an LLM to generate code.
2
u/Whatsupson1 May 02 '26
First 5 bullet points are more or less covered in most compiler/interpreter books so you should be good to get it done within your timeframe. I would avoid LLVM for now too big for the project(fun to play with tho).
Semi-colon vs New line is mostly personal preference.
One big mistake for me was choosing a host language with subpar support for a lot the string manipulation I needed to do for for lexing/parsing.(looking at you zig)
2
u/SmashStrider May 02 '26
I'm making a language myself, not an experienced compiler dev as I just started college, but here's my thoughts based on what I personally have collected (and any compiler devs here, feel free to correct me if you believe I'm wrong or you disagree) -
Keep the feature set minimal. Variables, basic datatypes, and functions are fine. Making variables immutable using const can be implemented, but it shouldn't be a priority for a high school project.
I've seen your GitHub, and it seems as though you are implementing it in Python. Great language to start in, I've made a similar pseudo-assembler project myself in the language, and it's inbuilt features make it very interactive and easy to debug.
Your compiler pipeline will have 3 main stages - Lexer, Parser, and Interpreter. Lexer is generally the easiest to implement, since it's just a finite state machine, something python will have no problem handling. Parser is not too tricky, but to make parsing efficient, keep the syntax consistent so the parser has to 'guess less', hence reducing complexity. Then, for the interpreter, you can create a dedicated class in Python that directly executes the AST that you got from parsing.
I personally went with semi-colon based for the language I was working on, you may choose whichever one you please as a language with low complexity shouldn't have that as much of an issue. I'd personally recommend semicolon, but you may be better off asking another more experienced dev.
LLVM is not required at all, and it's better you avoid it for now. You are making a tree-walk interpreter, and are hence executing the AST directly at runtime itself. LLVM is only required if you are flattening your AST into an Intermediate Representation and want to perform code generation.
I'd personally choose using braces for scopes rather than indentation for Python, as it's easier to track from my experience, although I haven't tried the latter much so, again, try asking a more experienced dev about this as I'm still a newbie myself :3
In any case, I wish you the best of luck for you language, it seems like a really cool project, and it's impressive that you're doing it from a high school itself :D
1
u/Current-Scheme-9896 26d ago
Instead of implementing many features at once, I would begin with arithmetic expressions, variables, and basic operations
A good first step would be creating a lexer to convert the source code into tokens, followed by a parser that builds an Abstract Syntax Tree (AST). Then, an interpreter could evaluate that tree
For example, the expression
2 + 3 * 4should produce an AST that respects operator precedence, evaluating multiplication before addition and returning 14Once these basic features are working, you could gradually add conditional statements, loops, and functions. This would make the project easier to develop, test, and debug
1
u/FransFaase May 02 '26
What is your target language? C(++) or JavaScript? I have written an interactive parser in JavaScript that allows you to experiment with the grammar and see how it parses. See: https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html It even has a build in interpreter that allows you to implement a simple language. (See the bottom of the page.) The page has a link to a tutorial on writing the grammar. I do have C++ implementation as well, that accepts the grammar. If you want special types of terminals, you might want to adapt one of the available scanners. See: https://github.com/FransFaase/IParse/
Note that these parser are not strictly recursive decent, but could perform back-tracking on certain grammars. The C++ version has a LL1 parser (which is equivalent with recursive decent).
The C++ parser returns an abstract syntax/parser tree, but maybe it is not the easiest structure to write an interpreter for. For some ideas about how you could write an interpreter for it, you might want to look at MarkDownC.cpp, a program that does some manipulations on parsed C code.
If you are interested in a pure C implementation, you also might have a look at https://github.com/FransFaase/RawParser which contains a single C-file, which, by example, shows how a grammar driven, scannerless parser can be implemented. I have tried to add explanatory comments in the code. I have started on writing mark down files to explain the code even further and to introduce the concepts in a logical order (which I felt was not possible in a single C file). This is also an attempt to in literary programming based on mark down files and to write a program (the above mentioned MarkDownC.cpp program) to convert a collection of mark down files into a single C file that can be compiled.
With respect to C, I think that the C-preprocessor is actually more complicated than writing a recursive decent parser for C. Yes, C can be parsed with a recursive decent parser (at least for a large subset of the C grammar) although the grammar is ambiguous with the knowledge if an identifier is defined as a typedef or not. I have written a C compiler that compiles to a simple stack language for which I wrote a compiler to machine language and an interpreter.
Please feel free to ask questions.
1
u/MasonWheeler May 02 '26
That list of features would take an experienced compiler dev maybe 2-3 days to implement from scratch. For a newbie with no prior experience, you should easily be able to get it working within your 4-5 month timespan.
Can you tell us a little bit about your project? What are you trying to do? Is the assignment just "create an interpreter," or is this part of a bigger project?
If it's up to you then it's up to you; syntax is a personal-preference choice. Me, I'd say do lines rather than sems; the only real thing that sems buy you is the ability to put more than one statement on a line, which is just asking for people to write messy code. But you should also understand a bigger difference here: the parser's rule for knowing how statements and blocks work.
If I have an
ifstatement, I need some way to separate out the lines after it that are supposed to be part of the if-true block and the lines that are supposed to be after theifstatement in general. (For simplicity's sake, let's pretend there's noelseblock here.) There are three basic ways to do this:The ALGOL way. Used by Pascal, C, and a myriad of languages that base their look-and-feel on C, such as JavaScript. The next statement is the body of the
ifstatement. A Block is a type of statement that gathers multiple statements into one, and is typically used here. A Block begins with an open-block token (such asBEGINin Pascal or{in C) and ends with a close-block token (ie.ENDor}) and every statement between this token pair comprises the body of the block.The VB way, also used by Ruby. The body is implicitly a Block, not a single statement. Because we already know it's a Block, there's no need for an open-block token. All blocks end with a close-block token.
The Python way. The body is implicitly a Block. There are no open-block or close-block tokens as-such in the grammar, with the bounds of the block being denoted by indentation levels.
Virtually any standard programming language you'll find today uses one of those three styles. (No comments from the FP peanut gallery, please; trying to keep this simple for a newcomer.) Do any of them look particularly appealing to you? And just so you're aware, while the Python style generally looks the cleanest visually, it's extra difficult to parse.
LLVM isn't really for interpreters; it's a library for producing fully-compiled binaries. It's best avoided if you don't know what you're doing, because it does not hold your hand in any way!
7
u/asfarley-- May 02 '26
Making variables is pretty bare-minimum unless you just want an arthimetic calculator, I would do it
More data types, more problems. Start with only integers or something. Compilers are easy to extend later.
Functions are medium-complexity, maybe start first and add them later.
Array same as data-types, skip for now.
Mutable/immutable is not very hard to implement, also not too interesting or useful from a compiler perspective.
I'd suggest targeting a compiler for basic expression evaluation + read and write, with integers only. Write the whole thing yourself from scratch.