A grammar is said to be recursive if a category occurring on the lefthand side of a production also appears on the righthand side of a production, as illustrated in Example 8-2. The production Nom -> Adj Nom (where Nom is the category of nominals) involves direct recursion on the category Nom, whereas indirect recursion on S arises from the combination of two productions, namely S -> NP VP and VP -> V S.
Example 8-2. A recursive context-free grammar.
grammar2 = nltk.parse_cfg(
PropN -> 'Buster' | 'Chatterer' | 'Joe' Det -> 'the' | 'a'
N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log' Adj -> 'angry' | 'frightened' | 'little' | 'tall' V -> 'chased' | 'saw' | 'said' | 'thought' | 'was' | 'put' P -> 'on' )
To see how recursion arises from this grammar, consider the following trees. (10a) involves nested nominal phrases, while (10b) contains nested sentences.
We've only illustrated two levels of recursion here, but there's no upper limit on the depth. You can experiment with parsing sentences that involve more deeply nested structures. Beware that the RecursiveDescentParser is unable to handle left-recursive productions of the form X -> X Y; we will return to this in Section 8.4.
Was this article helpful?