0

Update: What you suggest using Reverse Polish or Shunting Yard (Note ! works on one variable like this !x)?

I am going to implement a simple compiler in C++ that supports the following 5 signs

+     -     *     /     !

While ! is always calculated first and the rest are calculated from left to right (non has advantage on the other)

Plus, I want the compiler to support braces so the following z= x + ( y+l) will calculate y+l first then add x to it while z=x+ y+ l calculates x+y first and adds z to it and this is illegal: z=x+

I though about adding braces whenever possible and then always to follow the deepest one like turning this: z=x+ y+ l into this: z=((x+ y)+ l) But that sounds to be hard and easy to make mistakes.

Any different suggestions? I heard once about using trees but C++11 has no trees and I don't know how exactly trees may work here

Please share details ideas if possible

  • 6
    Shunting yard algorithm? – JCWasmx86 Aug 05 '20 at 17:01
  • I'd suggest to use the reverse polish notation, if possible, it's a lot more easier to parse and there's no parenthesis required – gogaz Aug 05 '20 at 17:03
  • Another approach would be ANTLR – JCWasmx86 Aug 05 '20 at 17:05
  • 1
    As an exercise, it may be interesting to implement this by yourself, but if you intend to build anything beyond a trivial language be aware that there are very good and mature libraries for language parsing (e.g. [here](https://www.boost.org/doc/libs/1_73_0/libs/spirit/doc/html/spirit/introduction.html) you have an introduction to Boost.Spirit that parses most of what you want, except `!`). – jdehesa Aug 05 '20 at 17:07
  • @JCWasmx86 does this have any advantages over reverse polish notation –  Aug 05 '20 at 17:08
  • @jdehesa thanks but I'm not looking to use ready code –  Aug 05 '20 at 17:09
  • ANTLR has the advantage, that you only have to define a grammar (Although this can be tricky, too). Then ANTLR generates a lexer and a parser from this grammar, so you can only concentrate on evaluating/verifying/generating code. – JCWasmx86 Aug 05 '20 at 17:10
  • @JCWasmx86 In wikipedia the following input 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3 turned into 3 4 2 × 1 5 − 2 3 ^ ^ ÷ + how to move on? I can't calculate the latter it is not legal –  Aug 05 '20 at 17:11
  • 2
    @programmer_dude One thing you don't want to do -- don't try to implement this by using anything but formal techniques such as the shunting yard algorithm or using stacks/postfix. If you attempt to code this using your own made-up techniques, be prepared to go crazy trying to keep track of all of the different conditions, corner cases, etc. Also, if you were to write the code in this fashion, be prepared to give up on adding any features later, such as parentheses, due to the complexity of the code. – PaulMcKenzie Aug 05 '20 at 17:13
  • 1
    Push 3 to stack, push 4 to stack, push 2 to stack. Pop 2 and 4 from stack, multiply, push 8 to stack. Push 1 to stack, push 5 to stack, pop 5,1 from stack, subtract, push 4 to stack. Push 2, push 3, pop 3,2, push 8, pop 8, 4, push 1024 to stack, pop 1024 and 8, divide, push 1/256 to stack. Pop 1/256 and 3, ==> 3+(1/256) – JCWasmx86 Aug 05 '20 at 17:15
  • A "recursive decent" parser is fairly simple to write. – Jesper Juhl Aug 05 '20 at 17:17
  • @JesperJuhl It depends, on many factors. If it's a simple language, like in the example, it's true, but parsing C++ or Java or any other more complex language is really time-consuming and hard. I would always go with ANTLR – JCWasmx86 Aug 05 '20 at 17:18
  • @JCWasmx86 But ! is a binary operand and yard algorithm doesn't work with it so what can I do? –  Aug 05 '20 at 17:19
  • You have to tweak it a bit. See here: https://stackoverflow.com/questions/16425571/unary-minus-in-shunting-yard-expression-parser It's for an unary minus, but is trivial to change – JCWasmx86 Aug 05 '20 at 17:20
  • @JCWasmx86 I agree. I was basing my comment on OPs simple example. For something simple/basic I would probably go with "recursive decent" because it's easy to understand and implement. For something *really* complicated like C++ (which doesn't have a context free grammar) I would, of course, never do that. – Jesper Juhl Aug 05 '20 at 17:22
  • @JCWasmx86 I didn't understand the solution, he replaced it with u then what... –  Aug 05 '20 at 17:25
  • May someone kindly answer this: What you suggest, using **Reverse Polish** or **Shunting Yard** (Note '!' works on one variable like this !x)? –  Aug 05 '20 at 17:54
  • You don't need a tree, you can use a stack. See here: https://stackoverflow.com/a/9329509/485343 – rustyx Aug 05 '20 at 18:26

0 Answers0