如何从带括号的解析树中提取推导规则？
How to extract derivation rules from a bracketed parse tree?
我有很多这样的解析树：
( 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中）或伪代码？
编辑：
我觉得这个问题很普遍，在很多地方都很常见。简化的问题是从括号树中找到每个父项及其子项。
许多解析器构建的 AST 与语法的确切形状不匹配。
在这些情况下，应该清楚您不能从 AST 重新生成原始语法。因此，这不是一个广泛可用的解决方案的问题。
在 AST 与语法完全匹配的罕见情况下，您可以做得更好。
（您可以使用不匹配的 AST 来执行此操作以获得语法的粗略近似值）：
For each interior node N do:
Use N's children C1, C2, ... Ck to generate a rule "N = C1 C2 .. Ck".
Eliminate duplicate rules.
这提供了语法的一个子集，涵盖了您拥有的实例树。如果解析器未在此实例上使用语法规则，则它不会出现在集合中。您可能需要通过此过程 运行 大量实例树来很好地覆盖规则，但您无法在任何时候确定您是否拥有完整的集合。
我为 python 写了这篇文章。我相信您可以将其阅读为伪代码。 稍后我会为 Java 编辑 post。我后来添加了 Java 实现。
import re
# grammar repository
grammar_repo = []
s = "( S ( NP-SBJ ( PRP I ) ) ( INODE@S ( VP ( VBP have ) ( NP ( DT a ) ( INODE@NP ( NN savings ) ( NN account ) ) ) ) ( . . ) ) )"
# clean the string (make sure there is no double space in it)
s = s.replace(" ", " ").replace(" ", " ")
# find inner parenthesis (no-need-to-parse-grammar) or (lhs rhs) format
simple_grammars = re.findall("\([^\(\)]*\)", s)
# repeat until you cannot find any ( lhs rhs ) grammar
while len(simple_grammars) > 0:
# add all simple grammar into grammar repository
# replace them with their head
for simple_grammar in simple_grammars:
grammar = simple_grammar.split(" ")
# '(' == grammar[0] and ')' == grammar[-1]
lhs = grammar[1]
rhs = grammar[2:-1]
grammar_repo.append((lhs, rhs))
s = s.replace(simple_grammar, lhs)
simple_grammars = re.findall("\([^\(\)]*\)", s)
简而言之，从最简单的语法开始，您可以找到并用它们的左侧替换它们，然后继续。例如找到(PRP I)保存，然后用PRP替换。重复直到找到所有语法。
更新：
Java 的实现有点不同，但思路是一样的。完整代码在这里：http://ideone.com/0eE8bd
PrintStream ps = new PrintStream(System.out);
ArrayList grammarRepo = new ArrayList();
String item, grammar;
String str = "( S ( NP-SBJ ( PRP I ) ) ( INODE@S ( VP ( VBP have ) ( NP ( DT a ) ( INODE@NP ( NN savings ) ( NN account ) ) ) ) ( . . ) ) )";
// cleanup double spaces
while (str.contains(" ")){
str = str.replaceAll(" ", " ");
}
// find no parenthesis zones!
Matcher m = Pattern.compile("\([^\(\)]*\)").matcher(str);
// loop until nothing left:
while (m.find()) {
item = m.group();
// make the grammar:
grammar = item.substring(1, item.length()-1).trim().replaceFirst(" ", " -> ");
if (!grammarRepo.contains(grammar)) {
grammarRepo.add(grammar);
ps.print(grammar + "\n");
}
str = str.replace(item, grammar.split(" -> ")[0]);
m = Pattern.compile("\([^\(\)]*\)").matcher(str);
}
输出：
PRP -> I
NP-SBJ -> PRP
VBP -> have
DT -> a
NN -> savings
NN -> account
INODE@NP -> NN NN
NP -> DT INODE@NP
VP -> VBP NP
. -> .
INODE@S -> VP .
S -> NP-SBJ INODE@S
第 1 步：解析括号中的字符串以创建 AST
你可能没有这样想过，但字符串本身是由上下文无关文法定义的：
Node :== '(' String Node* ')' |
'(' String String ')'
我们的第一步是对这个文法使用一个recursive descent parser来生成一个抽象语法树，定义如下class：
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 不为空的节点。 "For each interior node N" 步骤可以通过树的前序或后序遍历来执行。
那么让我们定义一个规则class。
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
我有很多这样的解析树：
( 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中）或伪代码？
编辑：
我觉得这个问题很普遍，在很多地方都很常见。简化的问题是从括号树中找到每个父项及其子项。
许多解析器构建的 AST 与语法的确切形状不匹配。
在这些情况下，应该清楚您不能从 AST 重新生成原始语法。因此，这不是一个广泛可用的解决方案的问题。
在 AST 与语法完全匹配的罕见情况下，您可以做得更好。 （您可以使用不匹配的 AST 来执行此操作以获得语法的粗略近似值）：
For each interior node N do:
Use N's children C1, C2, ... Ck to generate a rule "N = C1 C2 .. Ck".
Eliminate duplicate rules.
这提供了语法的一个子集，涵盖了您拥有的实例树。如果解析器未在此实例上使用语法规则，则它不会出现在集合中。您可能需要通过此过程 运行 大量实例树来很好地覆盖规则，但您无法在任何时候确定您是否拥有完整的集合。
我为 python 写了这篇文章。我相信您可以将其阅读为伪代码。 稍后我会为 Java 编辑 post。我后来添加了 Java 实现。
import re
# grammar repository
grammar_repo = []
s = "( S ( NP-SBJ ( PRP I ) ) ( INODE@S ( VP ( VBP have ) ( NP ( DT a ) ( INODE@NP ( NN savings ) ( NN account ) ) ) ) ( . . ) ) )"
# clean the string (make sure there is no double space in it)
s = s.replace(" ", " ").replace(" ", " ")
# find inner parenthesis (no-need-to-parse-grammar) or (lhs rhs) format
simple_grammars = re.findall("\([^\(\)]*\)", s)
# repeat until you cannot find any ( lhs rhs ) grammar
while len(simple_grammars) > 0:
# add all simple grammar into grammar repository
# replace them with their head
for simple_grammar in simple_grammars:
grammar = simple_grammar.split(" ")
# '(' == grammar[0] and ')' == grammar[-1]
lhs = grammar[1]
rhs = grammar[2:-1]
grammar_repo.append((lhs, rhs))
s = s.replace(simple_grammar, lhs)
simple_grammars = re.findall("\([^\(\)]*\)", s)
简而言之，从最简单的语法开始，您可以找到并用它们的左侧替换它们，然后继续。例如找到(PRP I)保存，然后用PRP替换。重复直到找到所有语法。
更新： Java 的实现有点不同，但思路是一样的。完整代码在这里：http://ideone.com/0eE8bd
PrintStream ps = new PrintStream(System.out);
ArrayList grammarRepo = new ArrayList();
String item, grammar;
String str = "( S ( NP-SBJ ( PRP I ) ) ( INODE@S ( VP ( VBP have ) ( NP ( DT a ) ( INODE@NP ( NN savings ) ( NN account ) ) ) ) ( . . ) ) )";
// cleanup double spaces
while (str.contains(" ")){
str = str.replaceAll(" ", " ");
}
// find no parenthesis zones!
Matcher m = Pattern.compile("\([^\(\)]*\)").matcher(str);
// loop until nothing left:
while (m.find()) {
item = m.group();
// make the grammar:
grammar = item.substring(1, item.length()-1).trim().replaceFirst(" ", " -> ");
if (!grammarRepo.contains(grammar)) {
grammarRepo.add(grammar);
ps.print(grammar + "\n");
}
str = str.replace(item, grammar.split(" -> ")[0]);
m = Pattern.compile("\([^\(\)]*\)").matcher(str);
}
输出：
PRP -> I
NP-SBJ -> PRP
VBP -> have
DT -> a
NN -> savings
NN -> account
INODE@NP -> NN NN
NP -> DT INODE@NP
VP -> VBP NP
. -> .
INODE@S -> VP .
S -> NP-SBJ INODE@S
第 1 步：解析括号中的字符串以创建 AST
你可能没有这样想过，但字符串本身是由上下文无关文法定义的：
Node :== '(' String Node* ')' |
'(' String String ')'
我们的第一步是对这个文法使用一个recursive descent parser来生成一个抽象语法树，定义如下class：
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 不为空的节点。 "For each interior node N" 步骤可以通过树的前序或后序遍历来执行。
那么让我们定义一个规则class。
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