java - 已解析句子的数据结构

Question

请找例句:

(S1 (S (S (NP (NP (NP (NN Activation)) (PP (IN of) (NP (NN protein) (NN kinase) (NN C)))) (CC and) (NP (NP (NN elevation)) (PP (IN of) (NP (NN cAMP))))) (VP (VBP interact) (ADVP (RB synergistically)) (S (VP (TO to) (VP (VB raise) (NP (NP (NP (NP (NN c-Fos)) (CC and) (NP (NN AP-1))) (NN activity)) (PP (IN in) (NP (NN Jurkat) (NNS cells))))))))) (. .)))

目标是根据这句话创建一棵树；叶子是单词，中间节点是词性标签，根是 S1。括号表示句子中包含的短语的跨度；它们不需要包含在树中。

实现上述目标的数据结构的良好组合是什么，您是否也可以分享支持您的建议的伪代码？

我想到了 HashMap 和 ArrayList，但对如何实际开始实现感到困惑。只是在这一点上我并没有直观地理解逻辑。您的建议将不胜感激。

谢谢。

Answer 1

这种事情的基本方法是将字符串lex 转换为标记 序列，然后解析 该字符串为称为抽象语法树。这是一个很大的话题，但非常简短:

Lexing 意味着将您的字符串分解为不同的逻辑标记。在您的情况下，您可能只需要一个序列分成左括号和右括号以及标签。因此，您的标记是“(”、“)”之一，或者不是那个的一系列非空白字符。

解析 意味着读取该字符序列并从中构建树结构。

首先，您需要一个树结构:在您的情况下，它可能是一个数据结构，由 Sentence 组成，该 Sentence 由词性标记和可以是单词的对象列表组成或分句。 (我假设这里没有有趣的结构:如果你知道 NN 只能包含单词而 NP 只能包含子句，或者类似的东西，你可以在这里制作更丰富的树结构。)

接下来您需要将您的标记解析到这棵树中。最简单的方法非常简单:例如，看起来你可以只编写一个函数 `parse(List tokens)，它期望第一个标记是一个左括号，第二个是一个标签，然后递归消耗序列中的标记，直到遇到右括号标记。

这些主题是大量书籍和许多图书馆等的主题，但希望这能让您充分了解如何解决问题。