Citer : Posté le 10/09/2022 18:05 | #

---

Ow, ce projet jamais terminé !
Ça me donne envie de lui passer un petit coup de chiffon, tellement de choses à faire et si peu de temps rhaaa >.>

---

Citer : Posté le 16/10/2022 00:43 | #

---

I was just writing up a bunch of notes on a hybrid approach where the add-in's wouldn't need to be standalone (having them compile to standalone add-ins brings a lot of complexity). But, I came to one inescapable conclusion: I honestly think you'd be a lot better off first writing something like C.Basic. A lot of the work will be quite reusable for the compiler and you'll also gain valuable experience that will directly help you in writing a compiler later:

• You're going to want the program to spend as much time as possible inside library calls, because that's less code that the user has to write on the calculator. I'd imagine you'd even want to provide some kind of game engine. But, then, those library functions and the game engine are already going to be running at native speed. Unless you're writing something involving a lot of computation (chess program, raytracer, etc), I'm not seeing much of a speed advantage. And since you'll be writing a library, if you do go on to write a compiler, you can make direct use of it.

• Any approach would require a way to edit and debug the programs. This would inevitably involve F-key menus, etc. So, writing some kind of IDE is needed. And that could be later be reused for the compiler.

• There are already some painting add-ins, but you'll probably need to implement something as part of the IDE to be used for creating fonts and pixel art, where it could handle transparency, images smaller than the display, etc. It might also be nice to be able to at least import from some kind of simple standard graphics format, such as PPM.

• You're going to need to tokenize the C code using lexical analysis (and maybe even perform this as a pre-run step, as Python does). This lexer code can be directly reused later for a compiler.

• You're probably aware of this, but compilers are doing some level of interpretation during the compilation and optimization process. If you write "(3 + 4 * 5)" any decent compiler is going to turn that to 23 rather than actually emitting any multiply or add instructions. And, of course, being able to do this is something you'll need for the interpreter, so you'll gain experience for the compiler as well. I recommend researching algebraic to RPN conversion, recursive descent parsing, and LL grammars.

• You're going to end up thinking about many topics that you'll need for writing the compiler: How C expressions work at a low level, how things are arranged in memory, branching and function calls, calling conventions, etc.

Before you get to any of that, though...

I strongly recommend attempting to write a simple four-function integer calculator that respects the order of operations. Just "+", "-", "*", "/", negative numbers, and parenthesis.

When I was learning how to program, the fact that the computer could understand the order of operations was like magic to me. And, even after I'd implemented it myself and understood how it worked, it continued to be highly inspirational and motivational to me. I went on to write a number of interpreters and compilers for fun, a couple of which others used to write games. Looking back, I'm not exactly proud of the code I wrote for those, but I'm still proud of my accomplishment in doing so. And let me tell you, when someone uses a compiler you created to write and release a game, your ankles won't just swell, they will be in danger of bursting. I've also ended up writing this kind of code on the job to solve parsing problems that none of my coworkers knew how to handle, so it has professional uses as well.

There are many approaches and even automation tools you can use to write this calculator very easily. But, I'm going to recommend that you not use any tools and that you implement your calculator using a recursive descent parser. It's a simple, but very powerful approach to parsing that you can even use later to parse almost any type of familiar programming language (including C, although you might to use a tool for a compiler that complex).

To start writing your calculator, first write (by hand) a lexer that splits an input into tokens. Each token would have a type, either a number or an operator, and it would hold the value of the number or the type of operator. For the input "12 + (3 - 4) * -5" it should be able to output: Number: 12, Operator: ADD, Operator: OPEN PAREN, Number: 3, Operator: SUBTRACT, Number: 4, Operator: CLOSE PAREN, Operator: MULTIPLY, Operator: SUBTRACT, Number: 5. Don't attempt to combine "-" and "5" to "-5". Instead, that will be handled later and allows you to learn how to parse unary operators vs binary operators. Reserve an operator type of NEGATE for it, though.

Next, take those tokens, and write a recursive descent parser to convert the algebraic ordering of the syntax to RPN. Trust me, do not use the "shunting yard algorithm" for this, write an actual recursive descent parser. At first, just implement RPN output of numbers, MULTIPLY, and ADD.

Next, write a calculator that takes that RPN output and computes the answer. You now have a simple calculator that can properly compute "2 + 3 * 4"!

Once that works, output DIVIDE and SUBTRACT, and add those to the RPN calculator. Then handle parsing negative numbers and add NEGATE to RPN. Finally handle parenthesis. For me parenthesis felt extremely daunting, but the actual implementation turned out to be trivial, so in retrospect I worried for nothing.

And you've done it! Believe it or not, you're now well on your way to writing a simple compiler. Sure, maybe not some sophisticated optimizing compiler, but you'll start to see how you could write a simple compiler using what you've learned. Then you can go one study things like an AST.

If you attempt the calculator project please feel free to ask me anything. I'll try to help any way I can.

---

Citer : Posté le 16/10/2022 09:40 | #

---

For less sophisticated compilers you can skip the AST step and output tokens from the RDP. You won't get the benefit of optimization, but simple numerical calculations are almost free... you can just detect whether all the tokens are numeric and perform the calculation right in the RDP.

---

Citer : Posté le 16/10/2022 09:47 | #

---

What can I say... I wrote two fully functional Basic compilers using exactly that method. Thanks for putting a name to it, I had no idea that's what it was called.

---