natural language toolkit shiftreduce parser c 20012023 nltk project edward loper edlopergmail com steven bird stevenbird1gmail com url https www nltk org for license information see license txt shiftreduce parser a simple bottomup cfg parser that uses two operations shift and reduce to find a single parse for a text shiftreduceparser maintains a stack which records the structure of a portion of the text this stack is a list of strings and trees that collectively cover a portion of the text for example while parsing the sentence the dog saw the man with a typical grammar shiftreduceparser will produce the following stack which covers the dog saw np det the n dog v saw shiftreduceparser attempts to extend the stack to cover the entire text and to combine the stack elements into a single tree producing a complete parse for the sentence initially the stack is empty it is extended to cover the text from left to right by repeatedly applying two operations shift moves a token from the beginning of the text to the end of the stack reduce uses a cfg production to combine the rightmost stack elements into a single tree often more than one operation can be performed on a given stack in this case shiftreduceparser uses the following heuristics to decide which operation to perform only shift if no reductions are available if multiple reductions are available then apply the reduction whose cfg production is listed earliest in the grammar note that these heuristics are not guaranteed to choose an operation that leads to a parse of the text also if multiple parses exists shiftreduceparser will return at most one of them see nltk grammar create a new shiftreduceparser that uses grammar to parse texts type grammar grammar 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 initialize the stack trace output iterate through the text pushing the token onto the stack then reducing the stack did we reduce everything did we end up with the right category move a token from the beginning of remainingtext to the end of stack type stack liststr and tree param stack a list of strings and trees encoding the structure of the text that has been parsed so far type remainingtext liststr param remainingtext the portion of the text that is not yet covered by stack rtype none rtype bool return true if the right hand side of a cfg production matches the rightmost elements of the stack rhs matches rightmoststack if they are the same length and each element of rhs matches the corresponding element of rightmoststack a nonterminal element of rhs matches any tree whose node value is equal to the nonterminal s symbol a terminal element of rhs matches any string whose type is equal to the terminal type rhs listterminal and nonterminal param rhs the right hand side of a cfg production type rightmoststack liststring and tree param rightmoststack the rightmost elements of the parser s stack find a cfg production whose right hand side matches the rightmost stack elements and combine those stack elements into a single tree with the node specified by the production s lefthand side if more than one cfg production matches the stack then use the production that is listed earliest in the grammar the new tree replaces the elements in the stack rtype production or none return if a reduction is performed then return the cfg production that the reduction is based on otherwise return false type stack liststring and tree param stack a list of strings and trees encoding the structure of the text that has been parsed so far type remainingtext liststr param remainingtext the portion of the text that is not yet covered by stack try each production in order check if the rhs of a production matches the top of the stack combine the tree to reflect the reduction we reduced something we didn t reduce anything 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 1 just show shifts 2 show shifts reduces 3 display which tokens productions are shifedreduced print trace output displaying the given stack and text rtype none param marker a character that is printed to the left of the stack this is used with trace level 2 to print s before shifted stacks and r before reduced stacks print trace output displaying that a token has been shifted rtype none print trace output displaying that production was used to reduce stack rtype none check to make sure that all of the cfg productions are potentially useful if any productions can never be used then print a warning rtype none any production whose rhs is an extension of another production s rhs will never be used stepping shiftreduce parser a shiftreduceparser that allows you to setp through the parsing process performing a single operation at a time it also allows you to change the parser s grammar midway through parsing a text the initialize method is used to start parsing a text shift performs a single shift operation and reduce performs a single reduce operation step will perform a single reduce operation if possible otherwise it will perform a single shift operation parses returns the set of parses that have been found by the parser ivar history a list of stack remainingtext pairs containing all of the previous states of the parser this history is used to implement the undo operation see nltk grammar return the parser s stack rtype liststr and tree return the portion of the text that is not yet covered by the stack rtype liststr start parsing a given text this sets the parser s stack to and sets its remaining text to tokens perform a single parsing operation if a reduction is possible then perform that reduction and return the production that it is based on otherwise if a shift is possible then perform it and return true otherwise return false return false if no operation was performed true if a shift was performed and the cfg production used to reduce if a reduction was performed rtype production or bool move a token from the beginning of the remaining text to the end of the stack if there are no more tokens in the remaining text then do nothing return true if the shift operation was successful rtype bool use production to combine the rightmost stack elements into a single tree if production does not match the rightmost stack elements then do nothing return the production used to reduce the stack if a reduction was performed if no reduction was performed return none rtype production or none return the parser to its state before the most recent shift or reduce operation calling undo repeatedly return the parser to successively earlier states if no shift or reduce operations have been performed undo will make no changes return true if an operation was successfully undone rtype bool return a list of the productions for which reductions are available for the current parser state rtype listproduction return an iterator of the parses that have been found by this parser so far rtype itertree copied from nltk parser change the grammar used to parse texts param grammar the new grammar type grammar cfg demonstration code a demonstration of the shiftreduce 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 shift reduce 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 shift reduce parser a simple bottom up cfg parser that uses two operations shift and reduce to find a single parse for a text shiftreduceparser maintains a stack which records the structure of a portion of the text this stack is a list of strings and trees that collectively cover a portion of the text for example while parsing the sentence the dog saw the man with a typical grammar shiftreduceparser will produce the following stack which covers the dog saw np det the n dog v saw shiftreduceparser attempts to extend the stack to cover the entire text and to combine the stack elements into a single tree producing a complete parse for the sentence initially the stack is empty it is extended to cover the text from left to right by repeatedly applying two operations shift moves a token from the beginning of the text to the end of the stack reduce uses a cfg production to combine the rightmost stack elements into a single tree often more than one operation can be performed on a given stack in this case shiftreduceparser uses the following heuristics to decide which operation to perform only shift if no reductions are available if multiple reductions are available then apply the reduction whose cfg production is listed earliest in the grammar note that these heuristics are not guaranteed to choose an operation that leads to a parse of the text also if multiple parses exists shiftreduceparser will return at most one of them see nltk grammar create a new shiftreduceparser that uses grammar to parse texts type grammar grammar 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 initialize the stack trace output iterate through the text pushing the token onto the stack then reducing the stack did we reduce everything did we end up with the right category move a token from the beginning of remaining_text to the end of stack type stack list str and tree param stack a list of strings and trees encoding the structure of the text that has been parsed so far type remaining_text list str param remaining_text the portion of the text that is not yet covered by stack rtype none rtype bool return true if the right hand side of a cfg production matches the rightmost elements of the stack rhs matches rightmost_stack if they are the same length and each element of rhs matches the corresponding element of rightmost_stack a nonterminal element of rhs matches any tree whose node value is equal to the nonterminal s symbol a terminal element of rhs matches any string whose type is equal to the terminal type rhs list terminal and nonterminal param rhs the right hand side of a cfg production type rightmost_stack list string and tree param rightmost_stack the rightmost elements of the parser s stack find a cfg production whose right hand side matches the rightmost stack elements and combine those stack elements into a single tree with the node specified by the production s left hand side if more than one cfg production matches the stack then use the production that is listed earliest in the grammar the new tree replaces the elements in the stack rtype production or none return if a reduction is performed then return the cfg production that the reduction is based on otherwise return false type stack list string and tree param stack a list of strings and trees encoding the structure of the text that has been parsed so far type remaining_text list str param remaining_text the portion of the text that is not yet covered by stack try each production in order check if the rhs of a production matches the top of the stack combine the tree to reflect the reduction we reduced something we didn t reduce anything 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 1 just show shifts 2 show shifts reduces 3 display which tokens productions are shifed reduced print trace output displaying the given stack and text rtype none param marker a character that is printed to the left of the stack this is used with trace level 2 to print s before shifted stacks and r before reduced stacks print trace output displaying that a token has been shifted rtype none print trace output displaying that production was used to reduce stack rtype none check to make sure that all of the cfg productions are potentially useful if any productions can never be used then print a warning rtype none any production whose rhs is an extension of another production s rhs will never be used stepping shift reduce parser a shiftreduceparser that allows you to setp through the parsing process performing a single operation at a time it also allows you to change the parser s grammar midway through parsing a text the initialize method is used to start parsing a text shift performs a single shift operation and reduce performs a single reduce operation step will perform a single reduce operation if possible otherwise it will perform a single shift operation parses returns the set of parses that have been found by the parser ivar _history a list of stack remaining_text pairs containing all of the previous states of the parser this history is used to implement the undo operation see nltk grammar return the parser s stack rtype list str and tree return the portion of the text that is not yet covered by the stack rtype list str start parsing a given text this sets the parser s stack to and sets its remaining text to tokens perform a single parsing operation if a reduction is possible then perform that reduction and return the production that it is based on otherwise if a shift is possible then perform it and return true otherwise return false return false if no operation was performed true if a shift was performed and the cfg production used to reduce if a reduction was performed rtype production or bool move a token from the beginning of the remaining text to the end of the stack if there are no more tokens in the remaining text then do nothing return true if the shift operation was successful rtype bool use production to combine the rightmost stack elements into a single tree if production does not match the rightmost stack elements then do nothing return the production used to reduce the stack if a reduction was performed if no reduction was performed return none rtype production or none return the parser to its state before the most recent shift or reduce operation calling undo repeatedly return the parser to successively earlier states if no shift or reduce operations have been performed undo will make no changes return true if an operation was successfully undone rtype bool return a list of the productions for which reductions are available for the current parser state rtype list production return an iterator of the parses that have been found by this parser so far rtype iter tree copied from nltk parser change the grammar used to parse texts param grammar the new grammar type grammar cfg demonstration code a demonstration of the shift reduce 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 Tree





class ShiftReduceParser(ParserI):
    

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

    def grammar(self):
        return self._grammar

    def parse(self, tokens):
        tokens = list(tokens)
        self._grammar.check_coverage(tokens)

        
        stack = []
        remaining_text = tokens

        
        if self._trace:
            print("Parsing %r" % " ".join(tokens))
            self._trace_stack(stack, remaining_text)

        
        
        while len(remaining_text) > 0:
            self._shift(stack, remaining_text)
            while self._reduce(stack, remaining_text):
                pass

        
        if len(stack) == 1:
            
            if stack[0].label() == self._grammar.start().symbol():
                yield stack[0]

    def _shift(self, stack, remaining_text):
        
        stack.append(remaining_text[0])
        remaining_text.remove(remaining_text[0])
        if self._trace:
            self._trace_shift(stack, remaining_text)

    def _match_rhs(self, rhs, rightmost_stack):
        

        if len(rightmost_stack) != len(rhs):
            return False
        for i in range(len(rightmost_stack)):
            if isinstance(rightmost_stack[i], Tree):
                if not isinstance(rhs[i], Nonterminal):
                    return False
                if rightmost_stack[i].label() != rhs[i].symbol():
                    return False
            else:
                if isinstance(rhs[i], Nonterminal):
                    return False
                if rightmost_stack[i] != rhs[i]:
                    return False
        return True

    def _reduce(self, stack, remaining_text, production=None):
        
        if production is None:
            productions = self._grammar.productions()
        else:
            productions = [production]

        
        for production in productions:
            rhslen = len(production.rhs())

            
            if self._match_rhs(production.rhs(), stack[-rhslen:]):

                
                tree = Tree(production.lhs().symbol(), stack[-rhslen:])
                stack[-rhslen:] = [tree]

                
                if self._trace:
                    self._trace_reduce(stack, production, remaining_text)
                return production

        
        return None

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

    def _trace_stack(self, stack, remaining_text, marker=" "):
        
        s = "  " + marker + " [ "
        for elt in stack:
            if isinstance(elt, Tree):
                s += repr(Nonterminal(elt.label())) + " "
            else:
                s += repr(elt) + " "
        s += "* " + " ".join(remaining_text) + "]"
        print(s)

    def _trace_shift(self, stack, remaining_text):
        
        if self._trace > 2:
            print("Shift %r:" % stack[-1])
        if self._trace == 2:
            self._trace_stack(stack, remaining_text, "S")
        elif self._trace > 0:
            self._trace_stack(stack, remaining_text)

    def _trace_reduce(self, stack, production, remaining_text):
        
        if self._trace > 2:
            rhs = " ".join(production.rhs())
            print(f"Reduce {production.lhs()!r} <- {rhs}")
        if self._trace == 2:
            self._trace_stack(stack, remaining_text, "R")
        elif self._trace > 1:
            self._trace_stack(stack, remaining_text)

    def _check_grammar(self):
        
        productions = self._grammar.productions()

        
        
        for i in range(len(productions)):
            for j in range(i + 1, len(productions)):
                rhs1 = productions[i].rhs()
                rhs2 = productions[j].rhs()
                if rhs1[: len(rhs2)] == rhs2:
                    print("Warning: %r will never be used" % productions[i])





class SteppingShiftReduceParser(ShiftReduceParser):
    

    def __init__(self, grammar, trace=0):
        super().__init__(grammar, trace)
        self._stack = None
        self._remaining_text = None
        self._history = []

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

    def stack(self):
        
        return self._stack

    def remaining_text(self):
        
        return self._remaining_text

    def initialize(self, tokens):
        
        self._stack = []
        self._remaining_text = tokens
        self._history = []

    def step(self):
        
        return self.reduce() or self.shift()

    def shift(self):
        
        if len(self._remaining_text) == 0:
            return False
        self._history.append((self._stack[:], self._remaining_text[:]))
        self._shift(self._stack, self._remaining_text)
        return True

    def reduce(self, production=None):
        
        self._history.append((self._stack[:], self._remaining_text[:]))
        return_val = self._reduce(self._stack, self._remaining_text, production)

        if not return_val:
            self._history.pop()
        return return_val

    def undo(self):
        
        if len(self._history) == 0:
            return False
        (self._stack, self._remaining_text) = self._history.pop()
        return True

    def reducible_productions(self):
        
        productions = []
        for production in self._grammar.productions():
            rhslen = len(production.rhs())
            if self._match_rhs(production.rhs(), self._stack[-rhslen:]):
                productions.append(production)
        return productions

    def parses(self):
        
        if (
            len(self._remaining_text) == 0
            and len(self._stack) == 1
            and self._stack[0].label() == self._grammar.start().symbol()
        ):
            yield self._stack[0]

    

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







def demo():
    

    from nltk import CFG, parse

    grammar = CFG.fromstring(
        
    )

    sent = "I saw a man in the park".split()

    parser = parse.ShiftReduceParser(grammar, trace=2)
    for p in parser.parse(sent):
        print(p)


if __name__ == "__main__":
    demo()