natural language toolkit recursive descent parser c 20012023 nltk project edward loper edlopergmail com steven bird stevenbird1gmail com url https www nltk org for license information see license txt recursive descent parser a simple topdown cfg parser that parses texts by recursively expanding the fringe of a tree and matching it against a text recursivedescentparser uses a list of tree locations called a frontier to remember which subtrees have not yet been expanded and which leaves have not yet been matched against the text each tree location consists of a list of child indices specifying the path from the root of the tree to a subtree or a leaf see the reference documentation for tree for more information about tree locations when the parser begins parsing a text it constructs a tree containing only the start symbol and a frontier containing the location of the tree s root node it then extends the tree to cover the text using the following recursive procedure if the frontier is empty and the text is covered by the tree then return the tree as a possible parse if the frontier is empty and the text is not covered by the tree then return no parses if the first element of the frontier is a subtree then use cfg productions to expand it for each applicable production add the expanded subtree s children to the frontier and recursively find all parses that can be generated by the new tree and frontier if the first element of the frontier is a token then match it against the next token from the text remove the token from the frontier and recursively find all parses that can be generated by the new tree and frontier see nltk grammar create a new recursivedescentparser that uses grammar to parse texts type grammar cfg param grammar the grammar used to parse texts type trace int param trace the level of tracing that should be used when parsing a text 0 will generate no tracing output and higher numbers will produce more verbose tracing output inherit docs from parseri start a recursive descent parse with an initial tree containing just the start symbol recursively expand and match each elements of tree specified by frontier to cover remainingtext return a list of all parses found return an iterator of all parses that can be generated by matching and expanding the elements of tree specified by frontier rtype itertree type tree tree param tree a partial structure for the text that is currently being parsed the elements of tree that are specified by frontier have not yet been expanded or matched type remainingtext liststr param remainingtext the portion of the text that is not yet covered by tree type frontier listtupleint param frontier a list of the locations within tree of all subtrees that have not yet been expanded and all leaves that have not yet been matched this list sorted in lefttoright order of location within the tree if the tree covers the text and there s nothing left to expand then we ve found a complete parse return it if there s still text but nothing left to expand we failed if the next element on the frontier is a tree expand it if the next element on the frontier is a token match it rtype itertree return an iterator of all parses that can be generated by matching the first element of frontier against the first token in rtext in particular if the first element of frontier has the same type as the first token in rtext then substitute the token into tree and return all parses that can be generated by matching and expanding the remaining elements of frontier if the first element of frontier does not have the same type as the first token in rtext then return empty list type tree tree param tree a partial structure for the text that is currently being parsed the elements of tree that are specified by frontier have not yet been expanded or matched type rtext liststr param rtext the portion of the text that is not yet covered by tree type frontier list of tuple of int param frontier a list of the locations within tree of all subtrees that have not yet been expanded and all leaves that have not yet been matched if it s a terminal that matches rtext0 then substitute in the token and continue parsing if it s a nonmatching terminal fail rtype itertree return an iterator of all parses that can be generated by expanding the first element of frontier with production in particular if the first element of frontier is a subtree whose node type is equal to production s left hand side then add a child to that subtree for each element of production s right hand side and return all parses that can be generated by matching and expanding the remaining elements of frontier if the first element of frontier is not a subtree whose node type is equal to production s left hand side then return an empty list if production is not specified then return a list of all parses that can be generated by expanding the first element of frontier with any cfg production type tree tree param tree a partial structure for the text that is currently being parsed the elements of tree that are specified by frontier have not yet been expanded or matched type remainingtext liststr param remainingtext the portion of the text that is not yet covered by tree type frontier listtupleint param frontier a list of the locations within tree of all subtrees that have not yet been expanded and all leaves that have not yet been matched rtype tree return the tree that is licensed by production in particular given the production lhs elt1 eltn return a tree that has a node lhs symbol and n children for each nonterminal element elti in the production the tree token has a childless subtree with node value elti symbol and for each terminal element eltj the tree token has a leaf token with type eltj param production the cfg production that licenses the tree token that should be returned type production production this will be matched set the level of tracing output that should be generated when parsing a text type trace int param trace the trace level a trace level of 0 will generate no tracing output and higher trace levels will produce more verbose tracing output rtype none print trace output displaying the fringe of tree the fringe of tree consists of all of its leaves and all of its childless subtrees rtype none print trace output displaying the parser s current state param operation a character identifying the operation that generated the current state rtype none stepping recursive descent parser a recursivedescentparser that allows you to step through the parsing process performing a single operation at a time the initialize method is used to start parsing a text expand expands the first element on the frontier using a single cfg production and match matches the first element on the frontier against the next text token backtrack undoes the most recent expand or match operation step performs a single expand match or backtrack operation parses returns the set of parses that have been found by the parser ivar history a list of rtext tree frontier tripples containing the previous states of the parser this history is used to implement the backtrack operation ivar triede a record of all productions that have been tried for a given tree this record is used by expand to perform the next untried production ivar triedm a record of what tokens have been matched for a given tree this record is used by step to decide whether or not to match a token see nltk grammar xx temporary hack warning this should be replaced with something nicer when we get the chance for pos in c treepositions leaves cpos cpos freeze start parsing a given text this sets the parser s tree to the start symbol its frontier to the root node and its remaining text to token subtokens return the portion of the text that is not yet covered by the tree rtype liststr return a list of the tree locations of all subtrees that have not yet been expanded and all leaves that have not yet been matched rtype listtupleint return a partial structure for the text that is currently being parsed the elements specified by the frontier have not yet been expanded or matched rtype tree perform a single parsing operation if an untried match is possible then perform the match and return the matched token if an untried expansion is possible then perform the expansion and return the production that it is based on if backtracking is possible then backtrack and return true otherwise return none return none if no operation was performed a token if a match was performed a production if an expansion was performed and true if a backtrack operation was performed rtype production or string or bool try matching if we haven t already try expanding try backtracking nothing left to do expand the first element of the frontier in particular if the first element of the frontier is a subtree whose node type is equal to production s left hand side then add a child to that subtree for each element of production s right hand side if production is not specified then use the first untried expandable production if all expandable productions have been tried do nothing return the production used to expand the frontier if an expansion was performed if no expansion was performed return none rtype production or none make sure we can expand if they didn t specify a production check all untried ones record that we ve tried this production now try expanding we didn t expand anything match the first element of the frontier in particular if the first element of the frontier has the same type as the next text token then substitute the text token into the tree return the token matched if a match operation was performed if no match was performed return none rtype str or none record that we ve tried matching this token make sure we can match return the token we just matched return the parser to its state before the most recent match or expand operation calling undo repeatedly return the parser to successively earlier states if no match or expand operations have been performed undo will make no changes return true if an operation was successfully undone rtype bool return a list of all the productions for which expansions are available for the current parser state rtype listproduction make sure we can expand return a list of all the untried productions for which expansions are available for the current parser state rtype listproduction return whether the first element of the frontier is a token that has not yet been matched rtype bool return whether the parser s current state represents a complete parse rtype bool a stub version of parse that sets the parsers current state to the given arguments in recursivedescentparser the parse method is used to recursively continue parsing a text steppingrecursivedescentparser overrides it to capture these recursive calls it records the parser s old state in the history to allow for backtracking and updates the parser s new state using the given arguments finally it returns 1 which is used by match and expand to detect whether their operations were successful return 1 rtype list of int is it a good parse if so record it return an iterator of the parses that have been found by this parser so far rtype list of tree change the grammar used to parse texts param grammar the new grammar type grammar cfg demonstration code a demonstration of the recursive descent parser s np vp np det n det n pp vp v np v np pp pp p np np i n man park telescope dog det the a p in with v saw natural language toolkit recursive descent parser c 2001 2023 nltk project edward loper edloper gmail com steven bird stevenbird1 gmail com url https www nltk org for license information see license txt recursive descent parser a simple top down cfg parser that parses texts by recursively expanding the fringe of a tree and matching it against a text recursivedescentparser uses a list of tree locations called a frontier to remember which subtrees have not yet been expanded and which leaves have not yet been matched against the text each tree location consists of a list of child indices specifying the path from the root of the tree to a subtree or a leaf see the reference documentation for tree for more information about tree locations when the parser begins parsing a text it constructs a tree containing only the start symbol and a frontier containing the location of the tree s root node it then extends the tree to cover the text using the following recursive procedure if the frontier is empty and the text is covered by the tree then return the tree as a possible parse if the frontier is empty and the text is not covered by the tree then return no parses if the first element of the frontier is a subtree then use cfg productions to expand it for each applicable production add the expanded subtree s children to the frontier and recursively find all parses that can be generated by the new tree and frontier if the first element of the frontier is a token then match it against the next token from the text remove the token from the frontier and recursively find all parses that can be generated by the new tree and frontier see nltk grammar create a new recursivedescentparser that uses grammar to parse texts type grammar cfg param grammar the grammar used to parse texts type trace int param trace the level of tracing that should be used when parsing a text 0 will generate no tracing output and higher numbers will produce more verbose tracing output inherit docs from parseri start a recursive descent parse with an initial tree containing just the start symbol recursively expand and match each elements of tree specified by frontier to cover remaining_text return a list of all parses found return an iterator of all parses that can be generated by matching and expanding the elements of tree specified by frontier rtype iter tree type tree tree param tree a partial structure for the text that is currently being parsed the elements of tree that are specified by frontier have not yet been expanded or matched type remaining_text list str param remaining_text the portion of the text that is not yet covered by tree type frontier list tuple int param frontier a list of the locations within tree of all subtrees that have not yet been expanded and all leaves that have not yet been matched this list sorted in left to right order of location within the tree if the tree covers the text and there s nothing left to expand then we ve found a complete parse return it if there s still text but nothing left to expand we failed if the next element on the frontier is a tree expand it if the next element on the frontier is a token match it rtype iter tree return an iterator of all parses that can be generated by matching the first element of frontier against the first token in rtext in particular if the first element of frontier has the same type as the first token in rtext then substitute the token into tree and return all parses that can be generated by matching and expanding the remaining elements of frontier if the first element of frontier does not have the same type as the first token in rtext then return empty list type tree tree param tree a partial structure for the text that is currently being parsed the elements of tree that are specified by frontier have not yet been expanded or matched type rtext list str param rtext the portion of the text that is not yet covered by tree type frontier list of tuple of int param frontier a list of the locations within tree of all subtrees that have not yet been expanded and all leaves that have not yet been matched if it s a terminal that matches rtext 0 then substitute in the token and continue parsing if it s a non matching terminal fail rtype iter tree return an iterator of all parses that can be generated by expanding the first element of frontier with production in particular if the first element of frontier is a subtree whose node type is equal to production s left hand side then add a child to that subtree for each element of production s right hand side and return all parses that can be generated by matching and expanding the remaining elements of frontier if the first element of frontier is not a subtree whose node type is equal to production s left hand side then return an empty list if production is not specified then return a list of all parses that can be generated by expanding the first element of frontier with any cfg production type tree tree param tree a partial structure for the text that is currently being parsed the elements of tree that are specified by frontier have not yet been expanded or matched type remaining_text list str param remaining_text the portion of the text that is not yet covered by tree type frontier list tuple int param frontier a list of the locations within tree of all subtrees that have not yet been expanded and all leaves that have not yet been matched rtype tree return the tree that is licensed by production in particular given the production lhs elt 1 elt n return a tree that has a node lhs symbol and n children for each nonterminal element elt i in the production the tree token has a childless subtree with node value elt i symbol and for each terminal element elt j the tree token has a leaf token with type elt j param production the cfg production that licenses the tree token that should be returned type production production this will be matched set the level of tracing output that should be generated when parsing a text type trace int param trace the trace level a trace level of 0 will generate no tracing output and higher trace levels will produce more verbose tracing output rtype none print trace output displaying the fringe of tree the fringe of tree consists of all of its leaves and all of its childless subtrees rtype none print trace output displaying the parser s current state param operation a character identifying the operation that generated the current state rtype none stepping recursive descent parser a recursivedescentparser that allows you to step through the parsing process performing a single operation at a time the initialize method is used to start parsing a text expand expands the first element on the frontier using a single cfg production and match matches the first element on the frontier against the next text token backtrack undoes the most recent expand or match operation step performs a single expand match or backtrack operation parses returns the set of parses that have been found by the parser ivar _history a list of rtext tree frontier tripples containing the previous states of the parser this history is used to implement the backtrack operation ivar _tried_e a record of all productions that have been tried for a given tree this record is used by expand to perform the next untried production ivar _tried_m a record of what tokens have been matched for a given tree this record is used by step to decide whether or not to match a token see nltk grammar xx temporary hack warning this should be replaced with something nicer when we get the chance for pos in c treepositions leaves c pos c pos freeze start parsing a given text this sets the parser s tree to the start symbol its frontier to the root node and its remaining text to token subtokens return the portion of the text that is not yet covered by the tree rtype list str return a list of the tree locations of all subtrees that have not yet been expanded and all leaves that have not yet been matched rtype list tuple int return a partial structure for the text that is currently being parsed the elements specified by the frontier have not yet been expanded or matched rtype tree perform a single parsing operation if an untried match is possible then perform the match and return the matched token if an untried expansion is possible then perform the expansion and return the production that it is based on if backtracking is possible then backtrack and return true otherwise return none return none if no operation was performed a token if a match was performed a production if an expansion was performed and true if a backtrack operation was performed rtype production or string or bool try matching if we haven t already try expanding try backtracking nothing left to do expand the first element of the frontier in particular if the first element of the frontier is a subtree whose node type is equal to production s left hand side then add a child to that subtree for each element of production s right hand side if production is not specified then use the first untried expandable production if all expandable productions have been tried do nothing return the production used to expand the frontier if an expansion was performed if no expansion was performed return none rtype production or none make sure we can expand if they didn t specify a production check all untried ones record that we ve tried this production now try expanding we didn t expand anything match the first element of the frontier in particular if the first element of the frontier has the same type as the next text token then substitute the text token into the tree return the token matched if a match operation was performed if no match was performed return none rtype str or none record that we ve tried matching this token make sure we can match return the token we just matched return the parser to its state before the most recent match or expand operation calling undo repeatedly return the parser to successively earlier states if no match or expand operations have been performed undo will make no changes return true if an operation was successfully undone rtype bool return a list of all the productions for which expansions are available for the current parser state rtype list production make sure we can expand return a list of all the untried productions for which expansions are available for the current parser state rtype list production return whether the first element of the frontier is a token that has not yet been matched rtype bool return whether the parser s current state represents a complete parse rtype bool a stub version of _parse that sets the parsers current state to the given arguments in recursivedescentparser the _parse method is used to recursively continue parsing a text steppingrecursivedescentparser overrides it to capture these recursive calls it records the parser s old state in the history to allow for backtracking and updates the parser s new state using the given arguments finally it returns 1 which is used by match and expand to detect whether their operations were successful return 1 rtype list of int is it a good parse if so record it return an iterator of the parses that have been found by this parser so far rtype list of tree change the grammar used to parse texts param grammar the new grammar type grammar cfg demonstration code a demonstration of the recursive descent parser s np vp np det n det n pp vp v np v np pp pp p np np i n man park telescope dog det the a p in with v saw
from nltk.grammar import Nonterminal
from nltk.parse.api import ParserI
from nltk.tree import ImmutableTree, Tree





class RecursiveDescentParser(ParserI):
    

    def __init__(self, grammar, trace=0):
        
        self._grammar = grammar
        self._trace = trace

    def grammar(self):
        return self._grammar

    def parse(self, tokens):
        

        tokens = list(tokens)
        self._grammar.check_coverage(tokens)

        
        
        start = self._grammar.start().symbol()
        initial_tree = Tree(start, [])
        frontier = [()]
        if self._trace:
            self._trace_start(initial_tree, frontier, tokens)
        return self._parse(tokens, initial_tree, frontier)

    def _parse(self, remaining_text, tree, frontier):
        

        
        
        if len(remaining_text) == 0 and len(frontier) == 0:
            if self._trace:
                self._trace_succeed(tree, frontier)
            yield tree

        
        elif len(frontier) == 0:
            if self._trace:
                self._trace_backtrack(tree, frontier)

        
        elif isinstance(tree[frontier[0]], Tree):
            yield from self._expand(remaining_text, tree, frontier)

        
        else:
            yield from self._match(remaining_text, tree, frontier)

    def _match(self, rtext, tree, frontier):
        

        tree_leaf = tree[frontier[0]]
        if len(rtext) > 0 and tree_leaf == rtext[0]:
            
            
            newtree = tree.copy(deep=True)
            newtree[frontier[0]] = rtext[0]
            if self._trace:
                self._trace_match(newtree, frontier[1:], rtext[0])
            yield from self._parse(rtext[1:], newtree, frontier[1:])
        else:
            
            if self._trace:
                self._trace_backtrack(tree, frontier, rtext[:1])

    def _expand(self, remaining_text, tree, frontier, production=None):
        

        if production is None:
            productions = self._grammar.productions()
        else:
            productions = [production]

        for production in productions:
            lhs = production.lhs().symbol()
            if lhs == tree[frontier[0]].label():
                subtree = self._production_to_tree(production)
                if frontier[0] == ():
                    newtree = subtree
                else:
                    newtree = tree.copy(deep=True)
                    newtree[frontier[0]] = subtree
                new_frontier = [
                    frontier[0] + (i,) for i in range(len(production.rhs()))
                ]
                if self._trace:
                    self._trace_expand(newtree, new_frontier, production)
                yield from self._parse(
                    remaining_text, newtree, new_frontier + frontier[1:]
                )

    def _production_to_tree(self, production):
        
        children = []
        for elt in production.rhs():
            if isinstance(elt, Nonterminal):
                children.append(Tree(elt.symbol(), []))
            else:
                
                children.append(elt)
        return Tree(production.lhs().symbol(), children)

    def trace(self, trace=2):
        
        self._trace = trace

    def _trace_fringe(self, tree, treeloc=None):
        

        if treeloc == ():
            print("*", end=" ")
        if isinstance(tree, Tree):
            if len(tree) == 0:
                print(repr(Nonterminal(tree.label())), end=" ")
            for i in range(len(tree)):
                if treeloc is not None and i == treeloc[0]:
                    self._trace_fringe(tree[i], treeloc[1:])
                else:
                    self._trace_fringe(tree[i])
        else:
            print(repr(tree), end=" ")

    def _trace_tree(self, tree, frontier, operation):
        
        if self._trace == 2:
            print("  %c [" % operation, end=" ")
        else:
            print("    [", end=" ")
        if len(frontier) > 0:
            self._trace_fringe(tree, frontier[0])
        else:
            self._trace_fringe(tree)
        print("]")

    def _trace_start(self, tree, frontier, text):
        print("Parsing %r" % " ".join(text))
        if self._trace > 2:
            print("Start:")
        if self._trace > 1:
            self._trace_tree(tree, frontier, " ")

    def _trace_expand(self, tree, frontier, production):
        if self._trace > 2:
            print("Expand: %s" % production)
        if self._trace > 1:
            self._trace_tree(tree, frontier, "E")

    def _trace_match(self, tree, frontier, tok):
        if self._trace > 2:
            print("Match: %r" % tok)
        if self._trace > 1:
            self._trace_tree(tree, frontier, "M")

    def _trace_succeed(self, tree, frontier):
        if self._trace > 2:
            print("GOOD PARSE:")
        if self._trace == 1:
            print("Found a parse:\n%s" % tree)
        if self._trace > 1:
            self._trace_tree(tree, frontier, "+")

    def _trace_backtrack(self, tree, frontier, toks=None):
        if self._trace > 2:
            if toks:
                print("Backtrack: %r match failed" % toks[0])
            else:
                print("Backtrack")





class SteppingRecursiveDescentParser(RecursiveDescentParser):
    

    def __init__(self, grammar, trace=0):
        super().__init__(grammar, trace)
        self._rtext = None
        self._tree = None
        self._frontier = [()]
        self._tried_e = {}
        self._tried_m = {}
        self._history = []
        self._parses = []

    
    
    def _freeze(self, tree):
        c = tree.copy()
        
        
        return ImmutableTree.convert(c)

    def parse(self, tokens):
        tokens = list(tokens)
        self.initialize(tokens)
        while self.step() is not None:
            pass
        return self.parses()

    def initialize(self, tokens):
        

        self._rtext = tokens
        start = self._grammar.start().symbol()
        self._tree = Tree(start, [])
        self._frontier = [()]
        self._tried_e = {}
        self._tried_m = {}
        self._history = []
        self._parses = []
        if self._trace:
            self._trace_start(self._tree, self._frontier, self._rtext)

    def remaining_text(self):
        
        return self._rtext

    def frontier(self):
        
        return self._frontier

    def tree(self):
        
        return self._tree

    def step(self):
        
        
        if self.untried_match():
            token = self.match()
            if token is not None:
                return token

        
        production = self.expand()
        if production is not None:
            return production

        
        if self.backtrack():
            self._trace_backtrack(self._tree, self._frontier)
            return True

        
        return None

    def expand(self, production=None):
        

        
        if len(self._frontier) == 0:
            return None
        if not isinstance(self._tree[self._frontier[0]], Tree):
            return None

        
        if production is None:
            productions = self.untried_expandable_productions()
        else:
            productions = [production]

        parses = []
        for prod in productions:
            
            self._tried_e.setdefault(self._freeze(self._tree), []).append(prod)

            
            for _result in self._expand(self._rtext, self._tree, self._frontier, prod):
                return prod

        
        return None

    def match(self):
        

        
        tok = self._rtext[0]
        self._tried_m.setdefault(self._freeze(self._tree), []).append(tok)

        
        if len(self._frontier) == 0:
            return None
        if isinstance(self._tree[self._frontier[0]], Tree):
            return None

        for _result in self._match(self._rtext, self._tree, self._frontier):
            
            return self._history[-1][0][0]
        return None

    def backtrack(self):
        
        if len(self._history) == 0:
            return False
        (self._rtext, self._tree, self._frontier) = self._history.pop()
        return True

    def expandable_productions(self):
        
        
        if len(self._frontier) == 0:
            return []
        frontier_child = self._tree[self._frontier[0]]
        if len(self._frontier) == 0 or not isinstance(frontier_child, Tree):
            return []

        return [
            p
            for p in self._grammar.productions()
            if p.lhs().symbol() == frontier_child.label()
        ]

    def untried_expandable_productions(self):
        

        tried_expansions = self._tried_e.get(self._freeze(self._tree), [])
        return [p for p in self.expandable_productions() if p not in tried_expansions]

    def untried_match(self):
        

        if len(self._rtext) == 0:
            return False
        tried_matches = self._tried_m.get(self._freeze(self._tree), [])
        return self._rtext[0] not in tried_matches

    def currently_complete(self):
        
        return len(self._frontier) == 0 and len(self._rtext) == 0

    def _parse(self, remaining_text, tree, frontier):
        
        self._history.append((self._rtext, self._tree, self._frontier))
        self._rtext = remaining_text
        self._tree = tree
        self._frontier = frontier

        
        if len(frontier) == 0 and len(remaining_text) == 0:
            self._parses.append(tree)
            self._trace_succeed(self._tree, self._frontier)

        return [1]

    def parses(self):
        
        return iter(self._parses)

    def set_grammar(self, grammar):
        
        self._grammar = grammar







def demo():
    

    from nltk import CFG, parse

    grammar = CFG.fromstring(
        
    )

    for prod in grammar.productions():
        print(prod)

    sent = "I saw a man in the park".split()
    parser = parse.RecursiveDescentParser(grammar, trace=2)
    for p in parser.parse(sent):
        print(p)


if __name__ == "__main__":
    demo()