Algorithm for AST

Asked

Viewed 92 times

2

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

out 5 + 7 * 3

My lexer turns it into:

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

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

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

But how to make a tree algorithm?

Note Please don’t post a code, it takes all the fun out of it. Instead, tell me the logic of the algorithm.

c++ algorithm interpreter

  • Although her question is not an exact duplicate of the one she wrote, she is an approximate duplicate. I explain: Your question is different, but the answers you need are all in this other question there (both in the question itself and in the answers).

1 answer

1


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

  • Sure, it works for operators, but what if I work with something like this: var1 = 15 var2 = [156, 'txt', var1, [1..5]]? PS: my lexer identifies texts, then 'txt' will stay strl: txt

  • If you see the assignment as an operator, this will allow interesting simplifications. Lists can also be seen as operators of multiple operands, an operation that puts expressions inside a list.

  • Like, what is neither constant nor variable is operation, right? D

Browser other questions tagged c++ algorithm interpreter

You are not signed in. Login or sign up in order to post.