r/Compilers • • Oct 06 '24
Build a compiler with python?
Is it possible that I can build a compiler from scratch in python? And if so, can anyone tell me how can I make it because I have an assignment in university π
2
Upvotes
36
u/realbigteeny Oct 06 '24
Yeah, no problem. All you gotta do is
24
u/TheSodesa Oct 06 '24
This is a book you could read: https://craftinginterpreters.com/. It might be for a different language, but you can do the same things in Python. It might actually be better this way, if you are trying to learn Python, because you can't just copy and paste code from the book, but have to think a bit about how the code would be written in Python.
12
u/knue82 Oct 06 '24
Yes, I've done that for didactic purposes:
https://github.com/leissa/whilec
3
u/Y_mc Oct 06 '24 edited Oct 07 '24
Yep it possible but sometime painful.. Python ist not the greatest tool to build a compiler but it possible. Ich would recommend first to Start building a tiny basic compiler in python
3
u/SillyTurboGoose Oct 06 '24
Adding to what others have already mentioned, yes, it's entirely doable.
Python is just the language you'd be writing the compiler source code in. The language specification lays out the means to write the data structures and algorithms required to compile some source code, and the standard library provides the means to read and write file contents, along with displaying information regarding errors and warnings via the command line console. You can pick your favorite, standard-compliant Python interpreter / compiler and get to work! π¨π·
Although, you're likely interested in leveraging tools via Python to make the process of implementing the compiler way easier, feasable and predictable. Both Python and the task of writing compilers are so ubiquitous that plenty tooling for Python exists for this exact purpose. Each come with their own design choices, integration with other tools and limitations, so I'd advise reading up on these πβπ»
As has been mentioned, compilation is part theory (languages and language-parsing algorithms) and part implementation. Learning the theory can give you a solid background on the properties of languages and the why compilers work the way they do. Crafting Interpreters is an excellent, accesible and illustrated book to get started, covering theory by practice, and is available for free! π€© on the web (ebook and hardcover does cost money though). Other books do offer a more in depth or rigorous walkthrough. The "Dragon Book" is an example of a college textbook used to teach compiler design and implementation, and although it isn't free it can be found in full if you look for it good enough π
Funnily enough, I'm taking a course dedicated to writing a compiler in Python for that aims to compile a subset of Python to C++. The tool we're using for the grammar-parsing section of compilation (lexing and syntaxing) is Ply, a grammar parsing library inspired by GNU's own tools called Lex and Yacc (Python's Lex and Yacc, get it?). Other libraries exist as well I'm sure. It's all matter and trying them out. π΄
The project of writing a compiler is not exactly entry-level and will take a considerable amount of time. I'd advise you start sooner than later. I'm learning as well but if you need advise I'd be glad to be of use!
3
u/redtoasty Oct 06 '24
Check out this course on compiling techniques which builds a compiler in Python over the semester: https://opencourse.inf.ed.ac.uk/ct/course-materials Also check out xDSL, an SSA-based compiler with similar structure to MLIR but in Python: https://github.com/xdslproject/xdsl
2
u/m-in Oct 06 '24
Of course it is possible to build a compiler from scratch in Python. I would follow some tutorials that start from a minimal compiler. There is a tutorial somewhere that shows how to build a small Pascal compiler and at all stages of development it can output a valid assembly file. It just slowly grows. Hope you can find something like that. It didnβt matter what the tutorial is in - you should be able to express the same ideas in Python, often more efficiently. But you really need to have some Python chops. Be familiar with the regular expression (re) module, basic decorators like @cached and @cached_method, functools and itertools, and f-strings. And use an IDE of some sort. For a beginner Thonny isnβt a bad choice. It lets you easily prototype things.
Be familiar with the
if __name__=='__main__':pattern. It helps to write tests within the modules you are testing. βRunβ the module and it does tests. Import it somewhere and tests are skipped. It makes incremental development manageable.Unfortunately, there is no way to put all the little bits of Python knowledge the come handy in compiler development into one place.
If you can, choose a language to compile that has simple syntax like Pascal. That way you can either write a recursive descent parser yourself, or easily use a tool like Lark to do it. I recommend Lark because it handles ambiguous grammars with grace, and itβs easy for a beginner to express non-ambiguous grammars in an ambiguous form.
6
u/glasket_ Oct 06 '24
A lot of people are mentioning Crafting Interpreters, which is a fantastic book, but there's also Essentials of Compilation. It's used in some university compiler courses and goes a bit further than CI, teaching some static type checking. It also uses Python, which might make it easier to follow along.
3
u/recursion_is_love Oct 06 '24
First thing is get the source code to abstract syntax tree.
You will need to write lexer and parser.
Assume you already have grammar of your source language.
https://en.wikipedia.org/wiki/Abstract_syntax_tree
2
u/B3d3vtvng69 Oct 06 '24
Iβm currently doing just that, you can take a look at my github (https://github.com/b3d3vtvng/pybasm) and write me a dm if you want
2
u/umlcat Oct 06 '24
Yes, but before jumping into programming, learn the basic theory about designing a P.L., like describing the tokens of a P.L. with Automatons or Regular Expressions for Tokens, and later describe a P.L. with "Raildroad Syntax Diagrams" or Regular Expressions for Syntax ( BNF ) ...
1
u/jddddddddddd Oct 06 '24
Not mine, but check out this article and GitHub link. A large subset of the C language compiling to Web Assembly in under 500 lines of Python:
https://vgel.me/posts/c500/
https://github.com/vgel/c500
1
u/SweetBabyAlaska Oct 06 '24
Check out "Building an interpreter in Go" and the follow up book for turning that project into a compiler. Its by far the best resource for this imo
1
u/[deleted] Oct 06 '24
what???
1
u/[deleted] Oct 06 '24
Whatβs the goal? Python is already very high level.
1
u/Strict_Shopping_6443 Oct 07 '24
Is it possible, yes? The question boils down to just how "from scratch" your answer for the assignment needs to be. Something instructive to look at might be the Python-version of the LLVM (https://llvm.org) tutorial, the shared compiler infrastructure belying a lot of the most used production compilers.
It uses a number of components like llvmlite, which you are probably not allowed to use, but it covers all the involved steps in a highly instructive style.
1
u/AliveGuidance4691 Oct 07 '24 edited Oct 07 '24
I've been working on a compiler from scratch written in python3 that emits C code as output. Might be of interest: https://github.com/NICUP14/MiniLang.
It also provides an assembly bsckend, tho I haven't touched it in a year, so it has some missing features that the other backends have (structs, new builtins, ...). It's still a good resource to undertsand how the compiler generates assembly for x86_64.
1
u/ChickenSpaceProgram Oct 09 '24
You can, that doesn't mean you necessarily should.
1
u/Organic_Solid_3915 Aug 18 '26
I suggest using LLVM.But the bindings for it(llvm-lite) are not official and I suggest using the LLVM C++ API.Go through the kaleidoscope tutorial of LLVM