使用正则表达式处理句法分析树

1， 正则表达式如何处理嵌套结构

a.        .net 处理嵌套结构的方法

举例说明：

问题描述：从 before (nope (yes (here) okay) after 中匹配得到最大的被 ”()” 包含的文本。即显示红色的部分。

答案： .net ： \((?>[^()]+|\((?<DEPTH>)|\)(?<-DEPTH>))*(?(DEPTH)(?!))\)

        分析：

        (1) 、 \( 匹配左括号； \) 匹配右括号； [^()]+ 匹配非括号字符串

(2) 、 (?> … .) 固化分组，固化分组的作用在于：一旦括号内的子表达式匹配之后，匹配的内容就固定下来，在接下来的匹配过程中不会改变，除非整个固化分组的括号都被弃用，在外部回溯中重新应用。该处使用固化分组的作用在于提高匹配速度。

(3) 、 DEPTH 的使用 :DEPTH 实际使用了命名捕获的 <?>…> ，它总是能够匹配成功。正则表达式引擎的回溯堆栈保存了当前匹配成功分组的相关信息，而 (?<DEPTH>) 跟在 \( 后，所以它的成功匹配便可以保存 \( 的个数。跟随在 \) 后的结构 (?<-DEPTH>) 是 .NET 独有的结构，它会在匹配 \) 成功之后去掉最近的 ”successful DEPTH” 标记。如果不存在这样的 ”successful DEPTH” 标记，就会报告失败，整个正则表达式匹配失败： 1, 每匹配一个 \( 会把正则表达式保存的当前括号嵌套深度值加 1 ； 2, 每匹配一个 \) 会把正则表达式保存的当前括号嵌套深度值减 1 ； 3, (?(DEPTH)(?!)) 确保匹配最后的 \) 时，深度为 0 。

2， 如何使用正则表达式处理句法分析树

如何使用正则表达式识别一棵类似如下表示的句法分析树？

(TOP (S (NPB (DT The) (NN question) ) (VP (VBZ remains) (SBAR-A (IN whether) (S-A (NPB (PRP they) ) (VP (MD will) (VP-A (VB be) (ADJP (JJ able) (SG (VP (TO to) (VP-A (VB help) (PUNC. us.) ) ) ) ) ) ) ) ) ) ) )

答案： \((?>[^()]+|\([^()\s]+\s(?<DEPTH>)|\)\s(?<-DEPTH>))*(?(DEPTH)(?!))\)

分析类似。

3， 使用正则表达式处理句法分析树实例

a.        使用正则表达式获取所有的叶结点 :    \((?<POS>[^()]+)\s(?<Leaf>[^()]+)\)

b.       使用正则表达式获取所有的名词短语 NP:

\(NP\s(?>[^()]+|\([^()\s]+\s(?<DEPTH>)|\)\s(?<-DEPTH>))*(?(DEPTH)(?!))\)

c.        使用正则表达式获取满足如下性质的子树

        i.   该子句的标记为 SBAR[^()]*

                   ii.       该子句根节点的第一个儿子为一个词性为 IN 的词。

                  iii.       该子句的第二个儿子为一个子句：使用 S[^()]* 识别

                 iv.       该子句没有其他的儿子

 

 

(?<Clause>\(S[^() ]*\s(?<INWH>\(IN\s[^()]+\)\s)(?<ClauseAfterInWh>\(S[^() ]*\s(?>[^()]+|\([^()\s]+\s(?<DEPTH>)|\)\s(?<-DEPTH>))*(?(DEPTH)(?!))\)\s)\)\s(?#Clause))