java - 如何从带括号的解析树中提取推导规则？

Question

我有很多像这样的解析树:

( S ( NP-SBJ ( PRP I  )  )  ( INODE@S ( VP ( VBP have  )  ( NP ( DT a  )  ( INODE@NP ( NN savings  )  ( NN account  )  )  )  )  ( . .  )  )  )

对于这样一句话:“我有一个储蓄账户。”

我需要从这些树中提取所有推导规则。推导规则如下:

S -> NP-SBJ INODE@S
NP-SBJ -> PRP 
PRP -> I
INODE@S -> VP NP
and so on.

是否有为此目的准备好的代码(最好是在 java 中)或伪代码？

编辑:

我觉得这个问题很普遍，在很多领域都很普遍。简化的问题是从括号树中找到每个父项及其子项。

Answer 1

第 1 步:解析括号中的字符串以创建 AST

你可能没有这样想过，但字符串本身是由上下文无关文法定义的:

Node :== '(' String Node* ')' |
         '(' String String ')'

我们的第一步是使用 recursive descent parser为该文法生成由以下类定义的抽象语法树:

class Node {
  string component;
  List<Node> children = new ArrayList<Node>();
  string word;
}

首先，标记括号内的字符串并将标记放入队列中。我认为 string.split("\\s+") 应该可以工作，因为所有括号和字符串都用空格分隔。

Node parse(Queue<string> tokens) throws ParseException {
  Node n = new Node();
  if (!tokens.remove().equals("(")) {
    throw new ParseException();
  }
  n.component = tokens.remove()
  if (n.component.equals("(") || n.component.equals(")")) {
    throw new ParseException();
  }
  if (tokens.element().equals("(")) {
    while (tokens.element().equals("(")) {
      Node child = parse(tokens);
      n.childen.add(child);
    }
  } else if (!tokens.element().equals(")")) {
    n.word = tokens.remove();
  } else {
    // we weren't expecting a close-paren yet
    throw new ParseException();
  }
  if (!tokens.remove.equals(")")) {
    throw new ParseException();
  }
  return n;
}

第 2 步:遍历 AST 以构建规则。

此步骤是使用 Ira Baxter 发布的伪代码执行的。

For each interior node N do:
    Use N's children C1, C2, ... Ck to generate a rule  "N = C1 C2 .. Ck". 
Eliminate duplicate rules.

就此算法而言，内部节点是 word == null 或 children 不为空的节点。 “对于每个内部节点 N”步骤可以通过树的前序或后序遍历来执行。

那么让我们定义一个规则类。

class Rule {
  string left;
  List<String> right = new ArrayList();

  // define the equals and hashcode methods appropriately.
  // We'll need them because we're inserting this class into
  // a HashSet.
}

让我们定义一个通用的树遍历函数

interface Visitor {
  void handle(Node n);
}

void traverse(Node n, Visitor v) {
  v.handle(n);
  for (Node child: n.children) {
    traverse(child, v);
  }
}

然后让我们定义构建和删除重复规则的访问者

class RuleBuilder implements Visitor {
  Set<Rule> rules = new HashSet<Rule>;

  public void handle(Node n) {
    if (n.word != null) {
      return;
    }
    Rule r = new Rule();
    r.left = n.component;
    for (Node child: n.children) {
      r.right.add(child.component);
    }
    rules.add(r);
  }
}

结合在一起

Queue<string> tokens = new LinkedList(Arrays.asList(string.split("\\s+")));
Node ast = parse(tokens);
RuleBuilder ruleCollector = new RuleBuilder();
traverse(ast, ruleCollector)

你需要的规则在ruleCollector.rules