使用调车场算法的抽象语法树

Question

我有一个已标记化的中缀表达式，并希望继续创建抽象语法树。我了解这些情况下使用的调车场算法。我只找到了将中缀表达式转换为 RPN 格式的方法，而不是转换为 AST 的方法。我可以先创建 RPN 版本，然后从中创建 AST，但这似乎没有必要。

我选择的语言是 JavaScript，尽管我只需要查看任何语言的示例和/或算法的描述。我浏览过《龙之书》和特伦斯·帕尔的书，但都没有给出我想要的答案。

Answer 1

请参阅用 dart 编写的简化版本，它同时生成 RPN 和 AST。 使用来自wikipedia的伪代码进行实现。

这里是算法的一个很好的视觉解释。

尝试一下

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;
  }
}