2

Estou criando uma linguagem de programação no C++. Fiz um lexer simples, que funciona perfeitamente bem por enquanto.

out 5 + 7 * 3

Meu lexer transforma isso em:

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

Agora preciso criar uma AST (árvore de sintaxe abstrata), que transforme o exemplo em isso:

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

Mas, como se faz um algoritmo de árvore?

Nota Por favor não postem um código, isso tira toda a graça. Em vez disso, me falem a lógica do algoritmo.

1
  • Embora a sua pergunta não seja duplicata exata dessa outra que linkei, ela é uma duplicata aproximada. Explico: A sua pergunta é diferente, mas as respostas que você precisa estão todas nessa outra pergunta aí (tanto na pergunta em si como nas respostas). Commented 4/08/2017 às 0:48

1 Resposta 1

1

Simples. Você identifica na expressão o último operador a ser operado. Associe a esse operador todos os seus operandos adequadamente, cada um estruturado como expressão. Aí você trata cada uma dessas expressões de operandos da mesma forma que você acabou de fazer, recursivamente. A recursão termina quando a expressão não tiver mais operadores. Se não ficou claro, me avise.

3
  • Claro, isso funciona para operadores, mas e se eu trabalhar com algo assim: var1 = 15 var2 = [156, 'txt', var1, [1..5]]? PS: meu lexer identifica textos, então 'txt' ficará strl: txt Commented 3/08/2017 às 22:32
  • Se ver a atribuição como operador, isso possibilitará simplificações interessantes. Listas também podem ser vistas como operadores de múltiplos operandos, uma operação que bota expressões dentro de uma lista.
    – RHER WOLF
    Commented 3/08/2017 às 22:33
  • Tipo, o que não é constante nem variável é operação, correto? :D
    – RHER WOLF
    Commented 3/08/2017 às 23:21

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .