Abstract syntax tree using the shunting yard algorithm

Question

I have an infix expression that I have tokenised and would like to proceed to create an abstract syntax tree. I understand the shunting-yard algorithm used in these cases. I have only found ways to convert the infix expression to RPN format, not into an AST. I could create the RPN version first and then AST from it, but it seems unnecessary.

My language of choice is JavaScript, though I only need to see an example in any language and/or a description of the algorithm. I have skimmed through the Dragon Book and Terence Parr's book, but neither gave the answer I was looking for.

Livable

This blog article shows this in Java, and might be useful. – Septempartite

I just happened to post a gist gist.github.com/gene-ressler/8278298 that makes a DAG rather than an AST. But if you remove the dict.lookup calls, it makes an AST. This does not use the shunting yard algorithm, but a recursive descent parser. – Deberadeberry

Possible duplicate of How to construct an abstract syntax tree – Kid

If you’re just looking for an example, here is a truth table generator I wrote in JavaScript that uses the shunting yard algorithm to directly build an AST. – Drennen

#74909607 – Regardant

Answer 1

Please see a simplified version written in dart, it produces both RPN and AST. Used pseudocode from wikipedia for the implementation.

Here is a nice visual explanation of the algorithm.

Try it out

void main() {
  final ast = shunting('(2*3*x+5*y-3*z)/(1+3+2*2)'.split(''), 'xyz'.split(''));
  print(ast);
}

/// imm - immediate value
Ast shunting(
  List<String> body,
  List<String> arguments,
) {
  final tree = <Ast>[];
  final outputQueue = <String>[];
  final operatorStack = <String>[];
  for (final token in body) {
    if (int.tryParse(token) is int) {
      final operand = UnOp('imm', int.parse(token));
      outputQueue.add(token);
      tree.add(operand);
    } else if (arguments.contains(token)) {
      final operand = UnOp('arg', arguments.indexOf(token));
      outputQueue.add(token);
      tree.add(operand);
    } else if (token.isOperator) {
      while (operatorStack.isNotEmpty && (operatorStack.last > token || operatorStack.last.isSamePrecedence(token))) {
        final lastOp = operatorStack.removeLast();
        outputQueue.add(lastOp);
        final second = tree.removeLast();
        final first = tree.removeLast();
        tree.add(BinOp(lastOp, first, second));
      }
      operatorStack.add(token);
    } else if (token == '(') {
      operatorStack.add(token);
    } else if (token == ')') {
      assert(operatorStack.isNotEmpty, 'mismatched parenthesis');
      while (operatorStack.last != '(') {
        final lastOp = operatorStack.removeLast();
        outputQueue.add(lastOp);
        final second = tree.removeLast();
        final first = tree.removeLast();
        tree.add(BinOp(lastOp, first, second));
      }
      operatorStack.removeLast();
    }
  }
  while (operatorStack.isNotEmpty) {
    final lastOp = operatorStack.removeLast();
    outputQueue.add(lastOp);
    final second = tree.removeLast();
    final first = tree.removeLast();
    tree.add(BinOp(lastOp, first, second));
  }
  print('RPN: ${outputQueue.join()}');
  return tree.first;
}

abstract class Ast {
  abstract final String op;
}

class BinOp implements Ast {
  BinOp(
    this.op,
    this._a,
    this._b,
  );

  final Ast _a;
  final Ast _b;

  @override
  final String op;

  Ast a(Ast a) => _a;
  Ast b(Ast b) => _b;

  @override
  String toString() => '{op: $op, a: $_a, b: $_b}';
}

class UnOp implements Ast {
  UnOp(this.op, this.n);

  final int n;

  @override
  final String op;

  @override
  String toString() => '{op: $op, n: $n}';
}

extension Operators on String {
  bool operator >(Object other) {
    assert(other is String, 'Incompatible type comparison');
    return '*/'.split('').contains(this) && '+-'.split('').contains(other);
  }

  bool operator <(Object other) {
    assert(other is String, 'Incompatible type comparison');
    return '-+'.split('').contains(this) && '*/'.split('').contains(other);
  }

  bool get isOperator => '*/+-'.split('').contains(this);

  bool isSamePrecedence(Object other) {
    assert(other is String, 'Incompatible type comparison');
    if ('+-'.split('').contains(this) && '+-'.split('').contains(other)) return true;
    if ('/*'.split('').contains(this) && '/*'.split('').contains(other)) return true;
    return false;
  }
}

Abstemious