dart - 使用Dart petitparser构建表达式解析器，卡在节点访问者上

Question

我有更多的表达式解析器在工作(Dart PetitParser to get at AST datastructure created with ExpressionBuilder)。它似乎正在为数​​字，表达式前面的浮点数，括号，幂，乘，除，加，减，一元负数生成准确的AST。 (节点可以是文字字符串，也可以是具有优先级的对象，该对象的优先级会随即被遍历和连接在一起。)
我现在停留在访问节点上。我可以访问顶层节点(感谢Lukas)，但是我一直在决定是否添加括号。例如，在20 + 30 * 40中，我们不需要30 * 40左右的解析器，而解析树正确地使该解析器的节点更靠近根，因此在遍历期间首先将其击中。但是，在查看30 * 40节点时，我似乎没有足够的数据来确定在进入20+节点之前是否需要parens。非常相似的情况是(20 + 30)* 40，得到可以正确解析，并且离根更近20 + 30，因此再次访问20 + 30节点时，我需要在添加到* 40之前添加括号。
这必须是一个已解决的问题，但是我从来没有上过编译器学校，所以我对AST的了解足够多，这很危险。我想念什么“哈”？

// rip-common.dart:

import 'package:petitparser/petitparser.dart';
// import 'package:petitparser/debug.dart';

class Node {
  int precedence;
  List<dynamic> args;

  Node([this.precedence = 0, this.args = const []]) {
    // nodeList.add(this);
  }

  @override
  String toString() => 'Node($precedence $args)';

  String visit([int fromPrecedence = -1]) {
    print('=== visiting $this ===');
    var buf = StringBuffer();

    var parens = (precedence > 0) &&
        (fromPrecedence > 0) &&
        (precedence < fromPrecedence);
    print('<$fromPrecedence $precedence $parens>');

    // for debugging:
    var curlyOpen = '';
    var curlyClose = '';

    buf.write(parens ? '(' : curlyOpen);

    for (var arg in args) {
      if (arg is Node) {
        buf.write(arg.visit(precedence));
      } else if (arg is String) {
        buf.write(arg);
      } else {
        print('not Node or String: $arg');
        buf.write('$arg');
      }
    }

    buf.write(parens ? ')' : curlyClose);
    print('$buf for buf');
    return '$buf';
  }
}

class RIPParser {
  Parser _make_parser() {
    final builder = ExpressionBuilder();

    var number = char('-').optional() &
        digit().plus() &
        (char('.') & digit().plus()).optional();

    // precedence 5
    builder.group()
      ..primitive(number.flatten().map((a) => Node(0, [a])))
      ..wrapper(char('('), char(')'), (l, a, r) => Node(0, [a]));

    // negation is a prefix operator
    // precedence 4
    builder.group()..prefix(char('-').trim(), (op, a) => Node(4, [op, a]));

    // power is right-associative
    // precedence 3
    builder.group()..right(char('^').trim(), (a, op, b) => Node(3, [a, op, b]));

    // multiplication and addition are left-associative
    // precedence 2
    builder.group()
      ..left(char('*').trim(), (a, op, b) => Node(2, [a, op, b]))
      ..left(char('/').trim(), (a, op, b) => Node(2, [a, op, b]));
    // precedence 1
    builder.group()
      ..left(char('+').trim(), (a, op, b) => Node(1, [a, op, b]))
      ..left(char('-').trim(), (a, op, b) => Node(1, [a, op, b]));

    final parser = builder.build().end();

    return parser;
  }

  Result _result(String input) {
    var parser = _make_parser(); // eventually cache
    var result = parser.parse(input);

    return result;
  }

  String parse(String input) {
    var result = _result(input);
    if (result.isFailure) {
      return result.message;
    } else {
      print('result.value = ${result.value}');
      return '$result';
    }
  }

  String visit(String input) {
    var result = _result(input);
    var top_node = result.value; // result.isFailure ...
    return top_node.visit();
  }
}

// rip_cmd_example.dart
import 'dart:io';

import 'package:rip_common/rip_common.dart';

void main() {
  print('start');
  String input;
  while (true) {
    input = stdin.readLineSync();
    if (input.isEmpty) {
      break;
    }
    print(RIPParser().parse(input));
    print(RIPParser().visit(input));
  }
  ;
  print('done');
}

Answer 1

如您所见，ExpressionBuilder已经根据您指定的运算符组以正确的优先顺序组装了树。
对于在此处创建的包装parens节点，也是如此:..wrapper(char('('), char(')'), (l, a, r) => Node(0, [a]))。如果我对此节点进行测试，则将返回示例表达式的输入字符串:var parens = precedence == 0 && args.length == 1 && args[0] is Node;。
除非我缺少任何内容，否则您没有理由手动跟踪优先级。我还建议您为不同的运算符创建不同的节点类:ValueNode，ParensNode，NegNode，PowNode，MulNode……有点冗长，但是如果它们中的每一个都可以访问，则会更容易理解发生了什么(打印，评估，优化...)本身。