• 3.3 句法结构中的递归

    3.3 句法结构中的递归

    一个语法被认为是递归的,如果语法类型出现在产生式左侧也出现在右侧,如3.3所示。产生式Nom -> Adj Nom(其中Nom是名词性的类别)包含Nom类型的直接递归,而S上的间接递归来自于两个产生式的组合S -> NP VPVP -> 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子树必须重新创建。

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