Algorithm for AST [duplicate]

2

I'm creating a programming language in C ++. I made a simple lexer, which works perfectly fine for now.

out 5 + 7 * 3

My lexer turns this into:

kw:  out
num: 5
op:  +
num: 7
op:  *
num: 3
nl

Now I need to create an AST (abstract syntax tree), which makes the example into this:

   kw out
      |
    op +
    /  \
num 5  op *
       /  \
   num 7  num 2

But how do you do a tree algorithm?

Note Please do not post a code, that takes away all grace. Instead, tell me the logic of the algorithm.

    
asked by anonymous 03.08.2017 / 23:09

1 answer

1

Simple. You identify in the expression the last operator to be operated. Associate this operator with all its operands properly, each structured as an expression. Then you treat each of these operand expressions in the same way you just did, recursively. The recursion ends when the expression has no more operators. If it was not clear, let me know.

    
04.08.2017 / 00:25