2

我有更多的表达式解析器在工作（Dart PetitParser 可以使用 ExpressionBuilder 创建的 AST 数据结构）。它似乎正在为数​​字和表达式前面的浮点数、括号、幂、乘法、除法、加法、减法、一元负数生成准确的 AST。（节点要么是文字字符串，要么是一个优先于 List 有效负载的对象，该有效负载被遍历和连接。）

我现在被困在访问节点上。我可以完全访问顶部节点（感谢 Lukas），但我一直在决定是否添加括号。例如，在 20+30*40 中，我们不需要 30*40 左右的括号，并且解析树正确地具有更接近根的节点，因此我将在遍历期间首先点击它。但是，在查看 30*40 节点时，我似乎没有足够的数据来确定它是否需要括号，然后再转到 20+.. 一个非常相似的情况是 (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');
}
4

1 回答 1

0

正如您所观察到的，ExpressionBuilder已经根据您指定的运算符组以正确的优先顺序组装了树。

这也发生在此处创建的包装括号节点..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, ... 有点冗长，但如果每个运算符都可以访问（打印、评估、优化, ...) 本身。

于 2020-11-08T08:41:01.940 回答