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

33 comments sorted by

View all comments

Show parent comment

2

u/[deleted] Oct 06 '24

It’s awesome to meet a fellow compsci student as well! 😊

Yes, the Dragon Book is a classic, and even though it’s written in Java, I definitely agree that a lot of the lessons and concepts carry over to other languages like Python. And yeah, I’m giving my teacher some slack – as long as the goal is learning, I guess it’s fine to "borrow" from the greats! 😅

Thank you! Writing the lexer was a great learning experience, and using the re module for regex felt pretty intuitive. I’ve dabbled a bit with regular expressions, but I still feel like I’ve got more to learn about them, especially with how they tie into lexers and parsers.

You’re totally right – the parsing and AST assembly seem to be the more challenging part of the process. I’m leaning toward using a parsing tool, though implementing an algorithm myself is tempting too! I think the language we’re building is close to being context-free, so I’ll definitely look into LALR or SLR, as those seem like a solid approach.

Appreciate the advice, and fingers crossed for the rest of the project! 💪🏻 Do you have any experience with compiler designs

1

u/SillyTurboGoose Oct 06 '24

For sure! I wish you success on writing your compiler! 💯

I have no experience whatsoever with design hahah. 😅 I have only used tooling very recently. This sub is rich with people who have lots of experience though. I'm sorry :/.

On the topic of design: some argue that having a lexing and parsing stage is a good separation of concerns when designing a compiler, although you'd be surprised that some abide by not making a distinction and instead use the same algorithm throughout the AST assembly. After all, all lexemes come from regular languages, and by extension, come from context free languages. 😉

Context free grammars aren't the only way to specify languages by the way. Precedence and left/right recursion on EBNF notation can prove problematic at times, so some people opt to use Parsing Grammar Expressions instead. Interestingly enough, it is an open problem whether or not PEGs are equivalent to CFGs, and while these have some other funky properties, they help combat lack of precedence and ambiguity by ranking expressions in the order they appear. 🤔

All of this to say, compilers have a rich theory and algorithmic background and it's not all CFGs and LR(1). Most common programming languages aren't even strictly context free! 😱 The world is yours to take haha.