3.3 句法结构中的递归

一个语法被认为是递归的，如果语法类型出现在产生式左侧也出现在右侧，如3.3所示。产生式Nom -> Adj Nom（其中Nom是名词性的类别）包含Nom类型的直接递归，而S上的间接递归来自于两个产生式的组合S -> NP VP和VP -> V S。

  1. grammar2 = nltk.CFG.fromstring("""
  2.  S  -> NP VP
  3.  NP -> Det Nom | PropN
  4.  Nom -> Adj Nom | N
  5.  VP -> V Adj | V NP | V S | V NP PP
  6.  PP -> P NP
  7.  PropN -> 'Buster' | 'Chatterer' | 'Joe'
  8.  Det -> 'the' | 'a'
  9.  N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log'
  10.  Adj  -> 'angry' | 'frightened' |  'little' | 'tall'
  11.  V ->  'chased'  | 'saw' | 'said' | 'thought' | 'was' | 'put'
  12.  P -> 'on'
  13.  """)

要看递归如何从这个语法产生，思考下面的树。(10a)包括嵌套的名词短语，而(10b)包含嵌套的句子。

  1. >>> rd_parser = nltk.RecursiveDescentParser(grammar1)
  2. >>> sent = 'Mary saw a dog'.split()
  3. >>> for tree in rd_parser.parse(sent):
  4. ...     print(tree)
  5. (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))

注意

RecursiveDescentParser()接受一个可选的参数trace。如果trace大于零，则分析器将报告它解析一个文本的步骤。

递归下降分析有三个主要的缺点。首先，左递归产生式，如NP -> NP PP会进入死循环。第二，分析器浪费了很多时间处理不符合输入句子的词和结构。第三，回溯过程中可能会丢弃分析过的成分，它们将需要在之后再次重建。例如，从VP -> V NP上回溯将放弃为NP创建的子树。如果分析器之后处理VP -> V NP PP，那么NP子树必须重新创建。

递归下降分析是一种自上而下分析。自上而下分析器在检查输入之前先使用文法 预测 输入将是什么！然而，由于输入对分析器一直是可用的，从一开始就考虑输入的句子会是更明智的做法。这种方法被称为自下而上分析，在下一节中我们将看到一个例子。