def split_clauses(parse_tree):
    """Splits clauses to parse them independently. Returns a dictionary with
    the positions of the split as the keys and the split trees as the values."""
    clause_dict = {}
    clause_match = re.compile(r'\(*\s*\(S[A-Z]*')
    sbar_match = re.compile(r'\(SBAR[ \-]')
    deletion_list = []

    for position in parse_tree.treepositions():
        # We only want nodes, not leaves
        if not isinstance(parse_tree[position], Tree):
            continue

        subtree = parse_tree[position]

        # Return subtrees where the root node is an S node and there are no
        # other S nodes in the subtree
        if sbar_match.match(str(subtree)) and len(subtree) > 1:
            clause_dict[position] = (subtree[1], subtree[0].leaves())
            deletion_list.append(position)

    # Remove the clause from the tree
    for position in deletion_list:
        del parse_tree[position]

    clause_dict[(0)] = (parse_tree, '')
    
    # Code to split S nodes, not always what we want
##    for position in parse_tree.treepositions():
##        if not isinstance(parse_tree[position], Tree):
##            continue
##
##        subtree = parse_tree[position]
##        
##        if subtree.node == 'S':
##            clause_dict[position] = (subtree, ' ')
            
    return clause_dict def activize_clause(parse_tree_clause):
    """Converts passive clauses to active voice, substituting 'something' for the
    implicit agent."""

    sbj_match = re.compile(r'NP-SBJ.*')

    sbj_position = None
    null_obj_position = None
    aux_verb_position = None
        
    for position in parse_tree_clause.treepositions():

        subtree = parse_tree_clause[position]

        if isinstance(subtree, Tree) and \
           sbj_match.match(subtree.node) is not None:
            sbj_position = position
        elif isinstance(subtree[0], Tree) and subtree[0] and subtree[0][0] == '*':
            null_obj_position = position
        if isinstance(subtree, Tree) and subtree[0] in auxiliary_verbs:
            aux_verb_position = position

    if sbj_position is not None and null_obj_position is not None and \
       aux_verb_position is not None:
        parse_tree_clause[null_obj_position][0][0] = 'something'
        sbj = deepcopy(parse_tree_clause[sbj_position])
        null_obj = deepcopy(parse_tree_clause[null_obj_position])
        parse_tree_clause[sbj_position] = null_obj
        parse_tree_clause[null_obj_position] = sbj
        parse_tree_clause[aux_verb_position] = ''
        

    return parse_tree_clause def is_existential(tree_string):
    """Returns whether there is an existential there in the tree string."""
    return ('EX' in tree_string) def invert_clause(parse_tree):
    """Inverts clauses to enforce a NP-V ordering."""
    inverted = False
    vp_position = None
    np_position = None

    # Find the inverted clause tags and NP-V tags
    for position in parse_tree.treepositions():
        # We only want nodes, not leaves
        if not isinstance(parse_tree[position], Tree):
            continue

        if parse_tree[position].node == 'SINV' or \
           parse_tree[position].node == 'SQ':
            inverted = True
        
        children = [child for child in parse_tree[position]
                        if isinstance(child, Tree)]

        child_count = 0
        temp_np_position = None
        temp_vp_position = None
        
        for child in children: 
            if temp_np_position is None and child.node[:2] == 'NP':
                temp_np_position = child_count
            elif temp_vp_position is None and child.node[:1] == 'V':
                temp_vp_position = child_count
            child_count += 1

        if temp_np_position is not None and temp_vp_position is not None:
            vp_position = temp_vp_position
            np_position = temp_np_position
            break
    if position is not None:
        # Invert the NP-V ordering
        if inverted is True and vp_position is not None and np_position is not None:
            temp = parse_tree[position][vp_position]
            parse_tree[position][vp_position] = \
                                    parse_tree[position][np_position]
            parse_tree[position][np_position] = temp

        # Insert the PP into a node with a PRD tag
        prd_position = None
        pp_position = None

        if not isinstance(parse_tree[position], Tree):
            return parse_tree

        for sinv_position in parse_tree[position].treepositions():
            if not isinstance(parse_tree[position][sinv_position], Tree) or\
               sinv_position == ():
                continue
        
            if 'PRD' in parse_tree[position][sinv_position].node:
                prd_position = sinv_position
            elif 'PP' in parse_tree[position][sinv_position].node:
                pp_position = sinv_position

        if inverted is True and prd_position is not None and \
           pp_position is not None:
            parse_tree[position][prd_position] = \
                                    parse_tree[position][pp_position]
            del parse_tree[position][pp_position]

    return parse_tree def get_wh_question_type(tree_string):
    """Given a parse tree string, return the type of wh-question it is."""
    if 'WHADVP' in tree_string or \
        'WHNP' in tree_string or \
        'WHADJP' in tree_string or \
        'WHPP' in tree_string:
        tree_string_lower = tree_string.lower()
        if 'where' in tree_string_lower:
            return 'Location'
        if 'status' in tree_string_lower or 'doing' in tree_string_lower:
            return 'Status'
        if 'who' in tree_string_lower:
            return 'People'
        if 'what' in tree_string_lower:
            return 'Entity'

    return None def is_yn_question(tree_string):
    """Given a parse tree string, return whether it is a yes-no question."""
    return ('SQ' in tree_string or \
        'SINV' in tree_string or \
        'SBARQ' in tree_string or \
        '?' in tree_string) def pick_best_match(match_list):
    """From the list of tuples, with the first element being the dict containing role assignments,
    and the second element being the verb class, pick the match that maps to an action if it exists."""
    if len(match_list) == 0:
        return (None,None)

    understood_matches = [(match,sense) for match,sense in match_list if sense.split('-')[0] in UNDERSTOOD_SENSES]
    if len(understood_matches) > 0:
        return pick_most_complete_match(understood_matches)
    # Otherwise use the all matches
    return pick_most_complete_match(match_list) def existential_there_insertion(parse_tree):
    """Insert an NP into an existential there node."""
    existential_there_position = None
    np_predicate_position = None
    
    for position in parse_tree.treepositions():
        # Don't check the leaves or the root
        if not isinstance(parse_tree[position], Tree) or position == ():
            continue

        ex_children = [child for child in parse_tree[position]
                    if isinstance(child, Tree) and child.node == 'EX']

        if len(ex_children) > 0:
            existential_there_position = position
            continue

        if parse_tree[position].node == 'NP' or 'NP-PRD' in parse_tree[position].node:
            np_predicate_position = position

    if existential_there_position is not None and \
       np_predicate_position is not None:
        parse_tree[existential_there_position] = \
                            parse_tree[np_predicate_position]
        del parse_tree[np_predicate_position]

    return parse_tree def wh_movement(parse_tree):
    """Moves the WH cluase to the null element. Where are the hostages -> The hostages are where?"""
    wh_position = None
    null_position = None
    
    tag_match = re.compile(r'(?<=\()[A-Z][A-Z-]*')
    tags = tag_match.findall(str(parse_tree))
    if 'NP-PRD-A' not in tags and 'NP-SBJ' not in tags:
        # Only do WH movement if an NP predicate or NP subject exists:
        return parse_tree

    for position in parse_tree.treepositions():
        if not isinstance(parse_tree[position], Tree) or position == ():
            continue

        # Find the WH and null positions
        if parse_tree[position].node[:2] == 'WH':
            wh_position = position
        elif isinstance(parse_tree[position][0], Tree) and \
             parse_tree[position][0][0] == '*T*':
            null_position = position

        if wh_position is not None and null_position is not None:
            break

    # Move the WH branch
    if wh_position is not None and null_position is not None:
        parse_tree[null_position] = parse_tree[wh_position]
        del parse_tree[wh_position]
    
    return parse_tree             def split_conjunctions(parse_tree):
    """Find conjunctions in a given parse_tree, and create a list of parse trees
    with the conjunctions removed and the conjoined clauses in place of the
    parent node of the conjunction."""
    split_tree_list = []
    conjunction_dict = {}
    
    for position in parse_tree.treepositions():
        # We only want nodes, not leaves
        if not isinstance(parse_tree[position], Tree) or position == ():
            continue
        
        children = [child for child in parse_tree[position]
                    if isinstance(child, Tree)]

        # Get the tags to check for CC's or IN's
        children_nodes = [child.node for child in children]

        phrase_list = []
        conjunction = ''

        # Get any phrases that are siblings of a CC
        if 'CC' in children_nodes:
            for child in children:
                if child.node not in ('CC', 'DT'):
                    phrase_list.append(child)
                else:
                    conjunction = child[0]
    
        
        # Copy the tree and replace the parent node of the CC with the phrase
        # for each sibling of the CC
        for phrase in phrase_list:
            temp_tree = parse_tree.copy(deep=True)
            temp_tree[position] = phrase
            split_tree_list.append(temp_tree)
            
        if not conjunction == '':  
            conjunction_dict[position] = (split_tree_list, conjunction)

    if len(conjunction_dict.keys()) == 0:
        return {(0) : ([parse_tree], '') }

    return conjunction_dict def find_verbs(parse_tree):
    """Returns the list of tuples: (verb, negation)"""
    results = []
    ignore_positions = []
    # Depth-first traversal
    for position in parse_tree.treepositions():
        if not isinstance(parse_tree[position], Tree):
            continue
        if position in ignore_positions:
            continue
        # Check for do-insertion
        if parse_tree[position].node == 'VP' and len(parse_tree[position]) >= 2 and parse_tree[position][0].node == 'VBP' \
                and parse_tree[position][0][0].lower() == 'do' and parse_tree[position][-1].node == 'VP-A':
            # Found a do-insertion
            is_negated = parse_tree[position][1].node == 'RB' and parse_tree[position][1][0].lower() in ('not', "n't")
            results.append((parse_tree[position][-1][0][0].lower(), is_negated))
            ignore_positions.extend(position + subposition for subposition in parse_tree[position].treepositions())
        # Check for 'Never X' structures
        if isinstance(parse_tree[position][0], Tree) and parse_tree[position][0].node == 'ADVP-TMP' \
                and parse_tree[position][0][0].node == 'RB' and parse_tree[position][0][0][0].lower() == 'never':
            for child in parse_tree[position][1:]:
                if child.node == 'VP':
                    # Everything found in the VP should be negated
                    results.extend((verb, True) for verb, bad_negation in find_verbs(child))
                    # Ignore the extracted verbs
                    ignore_positions.extend(position + subposition for subposition in parse_tree[position].treepositions())
        # Check for verbs
        elif parse_tree[position].node[:2] == 'VB':
            results.append((parse_tree[position][0].lower(), False))
    return results def create_VerbFrameObjects(word):
    """Gets VerbNet data without using NLTK corpora browser."""
    vfo_list = []
    for class_id in word_sense_mapping[word]:
        vfo_list.extend(sense_frame_mapping[class_id])
    return vfo_list class Tree(list):

    r"""
    A Tree represents a hierarchical grouping of leaves and subtrees.
    For example, each constituent in a syntax tree is represented by a single Tree.

    A tree's children are encoded as a list of leaves and subtrees,
    where a leaf is a basic (non-tree) value; and a subtree is a
    nested Tree.

        >>> from nltk.tree import Tree
        >>> print(Tree(1, [2, Tree(3, [4]), 5]))
        (1 2 (3 4) 5)
        >>> vp = Tree('VP', [Tree('V', ['saw']),
        ...                  Tree('NP', ['him'])])
        >>> s = Tree('S', [Tree('NP', ['I']), vp])
        >>> print(s)
        (S (NP I) (VP (V saw) (NP him)))
        >>> print(s[1])
        (VP (V saw) (NP him))
        >>> print(s[1,1])
        (NP him)
        >>> t = Tree("(S (NP I) (VP (V saw) (NP him)))")
        >>> s == t
        True
        >>> t[1][1].node = "X"
        >>> print(t)
        (S (NP I) (VP (V saw) (X him)))
        >>> t[0], t[1,1] = t[1,1], t[0]
        >>> print(t)
        (S (X him) (VP (V saw) (NP I)))

    The length of a tree is the number of children it has.

        >>> len(t)
        2

    Any other properties that a Tree defines are known as node
    properties, and are used to add information about individual
    hierarchical groupings.  For example, syntax trees use a NODE
    property to label syntactic constituents with phrase tags, such as
    "NP" and "VP".

    Several Tree methods use "tree positions" to specify
    children or descendants of a tree.  Tree positions are defined as
    follows:

      - The tree position *i* specifies a Tree's *i*\ th child.
      - The tree position ``()`` specifies the Tree itself.
      - If *p* is the tree position of descendant *d*, then
        *p+i* specifies the *i*\ th child of *d*.

    I.e., every tree position is either a single index *i*,
    specifying ``tree[i]``; or a sequence *i1, i2, ..., iN*,
    specifying ``tree[i1][i2]...[iN]``.

    Construct a new tree.  This constructor can be called in one
    of two ways:

    - ``Tree(node, children)`` constructs a new tree with the
        specified node value and list of children.

    - ``Tree(s)`` constructs a new tree by parsing the string ``s``.
        It is equivalent to calling the class method ``Tree.parse(s)``.
    """

    def __init__(self, node_or_str, children=None):
        if children is None:
            if not isinstance(node_or_str, basestring):
                raise TypeError("%s: Expected a node value and child list "
                                "or a single string" % type(self).__name__)
            tree = type(self).parse(node_or_str)
            list.__init__(self, tree)
            self.node = tree.node
        elif isinstance(children, basestring):
            raise TypeError("%s() argument 2 should be a list, not a "
                            "string" % type(self).__name__)
        else:
            list.__init__(self, children)
            self.node = node_or_str

    #////////////////////////////////////////////////////////////
    # Comparison operators
    #////////////////////////////////////////////////////////////

    def __eq__(self, other):
        return (self.__class__ is other.__class__ and
                (self.node, list(self)) == (other.node, list(other)))

    def __lt__(self, other):
        if not isinstance(other, Tree):
            # raise_unorderable_types("<", self, other)
            # Sometimes children can be pure strings,
            # so we need to be able to compare with non-trees:
            return self.__class__.__name__ < other.__class__.__name__
        elif self.__class__ is other.__class__:
            return (self.node, list(self)) < (other.node, list(other))
        else:
            return self.__class__.__name__ < other.__class__.__name__

    # @total_ordering doesn't work here, since the class inherits from a builtin class
    __ne__ = lambda self, other: not self == other
    __gt__ = lambda self, other: not (self < other or self == other)
    __le__ = lambda self, other: self < other or self == other
    __ge__ = lambda self, other: not self < other

    #////////////////////////////////////////////////////////////
    # Disabled list operations
    #////////////////////////////////////////////////////////////

    def __mul__(self, v):
        raise TypeError('Tree does not support multiplication')

    def __rmul__(self, v):
        raise TypeError('Tree does not support multiplication')

    def __add__(self, v):
        raise TypeError('Tree does not support addition')

    def __radd__(self, v):
        raise TypeError('Tree does not support addition')

    #////////////////////////////////////////////////////////////
    # Indexing (with support for tree positions)
    #////////////////////////////////////////////////////////////

    def __getitem__(self, index):
        if isinstance(index, (int, slice)):
            return list.__getitem__(self, index)
        elif isinstance(index, (list, tuple)):
            if len(index) == 0:
                return self
            elif len(index) == 1:
                return self[index[0]]
            else:
                return self[index[0]][index[1:]]
        else:
            raise TypeError("%s indices must be integers, not %s" %
                            (type(self).__name__, type(index).__name__))

    def __setitem__(self, index, value):
        if isinstance(index, (int, slice)):
            return list.__setitem__(self, index, value)
        elif isinstance(index, (list, tuple)):
            if len(index) == 0:
                raise IndexError('The tree position () may not be '
                                 'assigned to.')
            elif len(index) == 1:
                self[index[0]] = value
            else:
                self[index[0]][index[1:]] = value
        else:
            raise TypeError("%s indices must be integers, not %s" %
                            (type(self).__name__, type(index).__name__))

    def __delitem__(self, index):
        if isinstance(index, (int, slice)):
            return list.__delitem__(self, index)
        elif isinstance(index, (list, tuple)):
            if len(index) == 0:
                raise IndexError('The tree position () may not be deleted.')
            elif len(index) == 1:
                del self[index[0]]
            else:
                del self[index[0]][index[1:]]
        else:
            raise TypeError("%s indices must be integers, not %s" %
                            (type(self).__name__, type(index).__name__))

    #////////////////////////////////////////////////////////////
    # Basic tree operations
    #////////////////////////////////////////////////////////////

    def leaves(self):
        """
        Return the leaves of the tree.

            >>> t = Tree("(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))")
            >>> t.leaves()
            ['the', 'dog', 'chased', 'the', 'cat']

        :return: a list containing this tree's leaves.
            The order reflects the order of the
            leaves in the tree's hierarchical structure.
        :rtype: list
        """
        leaves = []
        for child in self:
            if isinstance(child, Tree):
                leaves.extend(child.leaves())
            else:
                leaves.append(child)
        return leaves

    def flatten(self):
        """
        Return a flat version of the tree, with all non-root non-terminals removed.

            >>> t = Tree("(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))")
            >>> print(t.flatten())
            (S the dog chased the cat)

        :return: a tree consisting of this tree's root connected directly to
            its leaves, omitting all intervening non-terminal nodes.
        :rtype: Tree
        """
        return Tree(self.node, self.leaves())

    def height(self):
        """
        Return the height of the tree.

            >>> t = Tree("(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))")
            >>> t.height()
            5
            >>> print(t[0,0])
            (D the)
            >>> t[0,0].height()
            2

        :return: The height of this tree.  The height of a tree
            containing no children is 1; the height of a tree
            containing only leaves is 2; and the height of any other
            tree is one plus the maximum of its children's
            heights.
        :rtype: int
        """
        max_child_height = 0
        for child in self:
            if isinstance(child, Tree):
                max_child_height = max(max_child_height, child.height())
            else:
                max_child_height = max(max_child_height, 1)
        return 1 + max_child_height

    def treepositions(self, order='preorder'):
        """
            >>> t = Tree("(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))")
            >>> t.treepositions() # doctest: +ELLIPSIS
            [(), (0,), (0, 0), (0, 0, 0), (0, 1), (0, 1, 0), (1,), (1, 0), (1, 0, 0), ...]
            >>> for pos in t.treepositions('leaves'):
            ...     t[pos] = t[pos][::-1].upper()
            >>> print(t)
            (S (NP (D EHT) (N GOD)) (VP (V DESAHC) (NP (D EHT) (N TAC))))

        :param order: One of: ``preorder``, ``postorder``, ``bothorder``,
            ``leaves``.
        """
        positions = []
        if order in ('preorder', 'bothorder'):
            positions.append(())
        for i, child in enumerate(self):
            if isinstance(child, Tree):
                childpos = child.treepositions(order)
                positions.extend((i,) + p for p in childpos)
            else:
                positions.append((i,))
        if order in ('postorder', 'bothorder'):
            positions.append(())
        return positions

    def subtrees(self, filter=None):
        """
        Generate all the subtrees of this tree, optionally restricted
        to trees matching the filter function.

            >>> t = Tree("(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))")
            >>> for s in t.subtrees(lambda t: t.height() == 2):
            ...     print(s)
            (D the)
            (N dog)
            (V chased)
            (D the)
            (N cat)

        :type filter: function
        :param filter: the function to filter all local trees
        """
        if not filter or filter(self):
            yield self
        for child in self:
            if isinstance(child, Tree):
                for subtree in child.subtrees(filter):
                    yield subtree

    def pos(self):
        """
        Return a sequence of pos-tagged words extracted from the tree.

            >>> t = Tree("(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))")
            >>> t.pos()
            [('the', 'D'), ('dog', 'N'), ('chased', 'V'), ('the', 'D'), ('cat', 'N')]

        :return: a list of tuples containing leaves and pre-terminals (part-of-speech tags).
            The order reflects the order of the leaves in the tree's hierarchical structure.
        :rtype: list(tuple)
        """
        pos = []
        for child in self:
            if isinstance(child, Tree):
                pos.extend(child.pos())
            else:
                pos.append((child, self.node))
        return pos

    def leaf_treeposition(self, index):
        """
        :return: The tree position of the ``index``-th leaf in this
            tree.  I.e., if ``tp=self.leaf_treeposition(i)``, then
            ``self[tp]==self.leaves()[i]``.

        :raise IndexError: If this tree contains fewer than ``index+1``
            leaves, or if ``index<0``.
        """
        if index < 0:
            raise IndexError('index must be non-negative')

        stack = [(self, ())]
        while stack:
            value, treepos = stack.pop()
            if not isinstance(value, Tree):
                if index == 0:
                    return treepos
                else:
                    index -= 1
            else:
                for i in range(len(value) - 1, -1, -1):
                    stack.append((value[i], treepos + (i,)))

        raise IndexError('index must be less than or equal to len(self)')

    def treeposition_spanning_leaves(self, start, end):
        """
        :return: The tree position of the lowest descendant of this
            tree that dominates ``self.leaves()[start:end]``.
        :raise ValueError: if ``end <= start``
        """
        if end <= start:
            raise ValueError('end must be greater than start')
        # Find the tree positions of the start & end leaves, and
        # take the longest common subsequence.
        start_treepos = self.leaf_treeposition(start)
        end_treepos = self.leaf_treeposition(end - 1)
        # Find the first index where they mismatch:
        for i in range(len(start_treepos)):
            if i == len(end_treepos) or start_treepos[i] != end_treepos[i]:
                return start_treepos[:i]
        return start_treepos

    #////////////////////////////////////////////////////////////
    # Convert, copy
    #////////////////////////////////////////////////////////////

    @classmethod
    def convert(cls, tree):
        """
        Convert a tree between different subtypes of Tree.  ``cls`` determines
        which class will be used to encode the new tree.

        :type tree: Tree
        :param tree: The tree that should be converted.
        :return: The new Tree.
        """
        if isinstance(tree, Tree):
            children = [cls.convert(child) for child in tree]
            return cls(tree.node, children)
        else:
            return tree

    def copy(self, deep=False):
        if not deep:
            return type(self)(self.node, self)
        else:
            return type(self).convert(self)

    #////////////////////////////////////////////////////////////
    # Parsing
    #////////////////////////////////////////////////////////////

    @classmethod
    def parse(cls, s, brackets='()', parse_node=None, parse_leaf=None,
              node_pattern=None, leaf_pattern=None,
              remove_empty_top_bracketing=False):
        """
        Parse a bracketed tree string and return the resulting tree.
        Trees are represented as nested brackettings, such as::

          (S (NP (NNP John)) (VP (V runs)))

        :type s: str
        :param s: The string to parse

        :type brackets: str (length=2)
        :param brackets: The bracket characters used to mark the
            beginning and end of trees and subtrees.

        :type parse_node: function
        :type parse_leaf: function
        :param parse_node, parse_leaf: If specified, these functions
            are applied to the substrings of ``s`` corresponding to
            nodes and leaves (respectively) to obtain the values for
            those nodes and leaves.  They should have the following
            signature:

               parse_node(str) -> value

            For example, these functions could be used to parse nodes
            and leaves whose values should be some type other than
            string (such as ``FeatStruct``).
            Note that by default, node strings and leaf strings are
            delimited by whitespace and brackets; to override this
            default, use the ``node_pattern`` and ``leaf_pattern``
            arguments.

        :type node_pattern: str
        :type leaf_pattern: str
        :param node_pattern, leaf_pattern: Regular expression patterns
            used to find node and leaf substrings in ``s``.  By
            default, both nodes patterns are defined to match any
            sequence of non-whitespace non-bracket characters.

        :type remove_empty_top_bracketing: bool
        :param remove_empty_top_bracketing: If the resulting tree has
            an empty node label, and is length one, then return its
            single child instead.  This is useful for treebank trees,
            which sometimes contain an extra level of bracketing.

        :return: A tree corresponding to the string representation ``s``.
            If this class method is called using a subclass of Tree,
            then it will return a tree of that type.
        :rtype: Tree
        """
        if not isinstance(brackets, basestring) or len(brackets) != 2:
            raise TypeError('brackets must be a length-2 string')
        if re.search(r'\s', brackets):
            raise TypeError('whitespace brackets not allowed')
        # Construct a regexp that will tokenize the string.
        open_b, close_b = brackets
        open_pattern, close_pattern = (re.escape(open_b), re.escape(close_b))
        if node_pattern is None:
            node_pattern = r'[^\s%s%s]+' % (open_pattern, close_pattern)
        if leaf_pattern is None:
            leaf_pattern = r'[^\s%s%s]+' % (open_pattern, close_pattern)
        token_re = re.compile(r'%s\s*(%s)?|%s|(%s)' % (
            open_pattern, node_pattern, close_pattern, leaf_pattern))
        # Walk through each token, updating a stack of trees.
        stack = [(None, [])]  # list of (node, children) tuples
        for match in token_re.finditer(s):
            token = match.group()
            # Beginning of a tree/subtree
            if token[0] == open_b:
                if len(stack) == 1 and len(stack[0][1]) > 0:
                    cls._parse_error(s, match, 'end-of-string')
                node = token[1:].lstrip()
                if parse_node is not None:
                    node = parse_node(node)
                stack.append((node, []))
            # End of a tree/subtree
            elif token == close_b:
                if len(stack) == 1:
                    if len(stack[0][1]) == 0:
                        cls._parse_error(s, match, open_b)
                    else:
                        cls._parse_error(s, match, 'end-of-string')
                node, children = stack.pop()
                stack[-1][1].append(cls(node, children))
            # Leaf node
            else:
                if len(stack) == 1:
                    cls._parse_error(s, match, open_b)
                if parse_leaf is not None:
                    token = parse_leaf(token)
                stack[-1][1].append(token)

        # check that we got exactly one complete tree.
        if len(stack) > 1:
            cls._parse_error(s, 'end-of-string', close_b)
        elif len(stack[0][1]) == 0:
            cls._parse_error(s, 'end-of-string', open_b)
        else:
            assert stack[0][0] is None
            assert len(stack[0][1]) == 1
        tree = stack[0][1][0]

        # If the tree has an extra level with node='', then get rid of
        # it.  E.g.: "((S (NP ...) (VP ...)))"
        if remove_empty_top_bracketing and tree.node == '' and len(tree) == 1:
            tree = tree[0]
        # return the tree.
        return tree

    @classmethod
    def _parse_error(cls, s, match, expecting):
        """
        Display a friendly error message when parsing a tree string fails.
        :param s: The string we're parsing.
        :param match: regexp match of the problem token.
        :param expecting: what we expected to see instead.
        """
        # Construct a basic error message
        if match == 'end-of-string':
            pos, token = len(s), 'end-of-string'
        else:
            pos, token = match.start(), match.group()
        msg = '%s.parse(): expected %r but got %r\n%sat index %d.' % (
            cls.__name__, expecting, token, ' ' * 12, pos)
        # Add a display showing the error token itsels:
        s = s.replace('\n', ' ').replace('\t', ' ')
        offset = pos
        if len(s) > pos + 10:
            s = s[:pos + 10] + '...'
        if pos > 10:
            s = '...' + s[pos - 10:]
            offset = 13
        msg += '\n%s"%s"\n%s^' % (' ' * 16, s, ' ' * (17 + offset))
        raise ValueError(msg)

    #////////////////////////////////////////////////////////////
    # Visualization & String Representation
    #////////////////////////////////////////////////////////////

    def __repr__(self):
        childstr = ", ".join(repr(c) for c in self)
        return '%s(%s, [%s])' % (type(self).__name__, repr(self.node), childstr)

    def __str__(self):
        return self.pprint()

    def pprint(self, margin=70, indent=0, nodesep='', parens='()', quotes=False,
               force_multiline=False):
        """
        :return: A pretty-printed string representation of this tree.
        :rtype: str
        :param margin: The right margin at which to do line-wrapping.
        :type margin: int
        :param indent: The indentation level at which printing
            begins.  This number is used to decide how far to indent
            subsequent lines.
        :type indent: int
        :param nodesep: A string that is used to separate the node
            from the children.  E.g., the default value ``':'`` gives
            trees like ``(S: (NP: I) (VP: (V: saw) (NP: it)))``.
        """

        if not force_multiline:
            # Try writing it on one line.
            s = self._pprint_flat(nodesep, parens, quotes)
            if len(s) + indent < margin:
                return s

        # If it doesn't fit on one line, then write it on multi-lines.
        if isinstance(self.node, basestring):
            s = '%s%s%s' % (parens[0], self.node, nodesep)
        else:
            s = '%s%s%s' % (parens[0], repr(self.node), nodesep)
        for child in self:
            if isinstance(child, Tree):
                s += '\n' + ' ' * (indent + 2) + child.pprint(margin, indent + 2,
                                                              nodesep, parens, quotes,
                                                              force_multiline and len(child) > 1)
            elif isinstance(child, tuple):
                s += '\n' + ' ' * (indent + 2) + "/".join(child)
            elif isinstance(child, basestring) and not quotes:
                s += '\n' + ' ' * (indent + 2) + '%s' % child
            else:
                s += '\n' + ' ' * (indent + 2) + repr(child)
        return s + parens[1]

    def pprint_latex_qtree(self):
        r"""
        Returns a representation of the tree compatible with the
        LaTeX qtree package. This consists of the string ``\Tree``
        followed by the parse tree represented in bracketed notation.

        For example, the following result was generated from a parse tree of
        the sentence ``The announcement astounded us``::

          \Tree [.I'' [.N'' [.D The ] [.N' [.N announcement ] ] ]
              [.I' [.V'' [.V' [.V astounded ] [.N'' [.N' [.N us ] ] ] ] ] ] ]

        See http://www.ling.upenn.edu/advice/latex.html for the LaTeX
        style file for the qtree package.

        :return: A latex qtree representation of this tree.
        :rtype: str
        """
        reserved_chars = re.compile(r'([#\$%&~_\{\}])')

        pprint = self.pprint(indent=6, nodesep='', parens=('[.', ' ]'))
        return r'\Tree ' + re.sub(reserved_chars, r'\\\1', pprint)

    def _pprint_flat(self, nodesep, parens, quotes):
        childstrs = []
        for child in self:
            if isinstance(child, Tree):
                # pylint: disable=W0212
                childstrs.append(child._pprint_flat(nodesep, parens, quotes))
            elif isinstance(child, tuple):
                childstrs.append("/".join(child))
            elif isinstance(child, basestring) and not quotes:
                childstrs.append('%s' % child)
            else:
                childstrs.append(repr(child))
        if isinstance(self.node, basestring):
            return '%s%s%s %s%s' % (parens[0], self.node, nodesep,
                                    " ".join(childstrs), parens[1])
        else:
            return '%s%s%s %s%s' % (parens[0], repr(self.node), nodesep,
                                    " ".join(childstrs), parens[1]) def morphy(form, pos='noun', collect=0):
    """Recursively uninflect _form_, and return the first form found
    in the dictionary.  If _collect_ is true, a sequence of all forms
    is returned, instead of just the first one.
    
    >>> morphy('dogs')
    'dog'
    >>> morphy('churches')
    'church'
    >>> morphy('aardwolves')
    'aardwolf'
    >>> morphy('abaci')
    'abacus'
    >>> morphy('hardrock', 'adv')
    """
    from wordnet import _normalizePOS, _dictionaryFor
    pos = _normalizePOS(pos)
    fname = os.path.join(WNSEARCHDIR, {NOUN: 'noun', VERB: 'verb', ADJECTIVE: 'adj', ADVERB: 'adv'}[pos] + '.exc')
    excfile = open(fname)
    substitutions = MORPHOLOGICAL_SUBSTITUTIONS[pos]
    def trySubstitutions(trySubstitutions,	# workaround for lack of nested closures in Python < 2.1
                         form,		  	# reduced form
                         substitutions,		# remaining substitutions
                         lookup=1,
                         dictionary=_dictionaryFor(pos),
                         excfile=excfile,
                         collect=collect,
                         collection=[]):
        import string
        #exceptions = binarySearchFile(excfile, form)
        for line in excfile.readlines():
            if form == line.split()[0]:
                form = line.split()[1] 
        
        
##        if exceptions:
##            form = exceptions[string.find(exceptions, ' ')+1:-1]

        #print dictionary.keys()
        if lookup and dictionary.has_key(form):
            if collect:
                collection.append(form)
            else:
                return form
        elif substitutions:
            old, new = substitutions[0]
            substitutions = substitutions[1:]
            substitute = None
            if endsWith(form, old):
                substitute = form[:-len(old)] + new
                #if dictionary.has_key(substitute):
                #   return substitute
            form =              trySubstitutions(trySubstitutions, form, substitutions) or \
                (substitute and trySubstitutions(trySubstitutions, substitute, substitutions))
            return (collect and collection) or form
        elif collect:
            return collection
    return trySubstitutions(trySubstitutions, form, substitutions) class Location(Entity):
    """Class representing a location entity"""

    TYPE_ID = 1 class ObjectEntity(Entity):
    """Class representing an object entity"""

    TYPE_ID = 0 class YNQuery(Query):
    """Yes/No queries."""
    def __init__(self, theme, location):
        self.theme = theme
        self.location = location

    def __str__(self, lvl=0):
        indent = '\t'*(lvl)
        return 'YNQuery: \n' + \
               indent + '\tTheme: %s\n' % self.theme.__str__(lvl + 1) + \
               indent + '\tLocation: %s' % self.location.__str__(lvl + 1) class StatusQuery(Query):
    """Status queries"""
    def __init__(self):
        pass
    def __str__(self, lvl=0):
        return 'StatusQuery' class EntityQuery(Query):
    """Who/What queries"""
    def __init__(self, location):
        self.location = location

    def __str__(self, lvl=0):
        indent = '\t'*(lvl)
        return 'EntityQuery: \n' + \
               indent + '\tLocation: %s\n' % self.location.__str__(lvl + 1) class Command(object):
    """A Command for Junior to do something."""

    def __init__(self, agent, theme, patient, location, source, destination, action,
                 condition=None, negation=False):
        self.agent = agent
        self.theme = theme
        self.patient = patient
        self.location = location
        self.source = source
        self.destination = destination
        self.action = action
        self.condition = condition
        self.negation = negation

    def __str__(self, lvl=0):
        indent = '\t'*(lvl + 1)
        return 'Command: \n' + \
               (indent + 'Agent: ' + self.agent.__str__(lvl + 1) + '\n' if self.agent else '') + \
               indent + 'Action: ' + str(self.action)  + '\n' + \
               (indent + 'Theme: ' + self.theme.__str__(lvl + 1) + '\n' if self.theme else '') + \
               (indent + 'Patient:' + self.patient.__str__(lvl + 1) + '\n' if self.patient else '') + \
               (indent + 'Location: ' + self.location.__str__(lvl + 1) + '\n' if self.location else '') + \
               (indent + 'Source: ' + self.source.__str__(lvl + 1) + '\n' if self.source else '') + \
               (indent + 'Destination: ' + self.destination.__str__(lvl + 1) + '\n' if self.destination else '') + \
               (indent + 'Condition: ' + self.condition.__str__(lvl + 1) + '\n' if self.condition else '') + \
               indent + 'Negation: ' + str(self.negation)

    def __repr__(self):
        return str(self)

    def readable(self):
        response = ''
        if self.negation:
            response += ' not'
        if not self.action:
            return ''
        else:
            response += ' %s' % self.action
        if self.theme:
            response += ' %s' % self.theme.readable(case=False)
        elif self.patient:
            response += ' %s' % self.patient.readable(case=False)
        if self.location:
            response += ' in %s' % self.location.readable()
        if self.source:
            response += ' from %s' % self.source.readable()
        if self.destination:
            response += ' to %s' % self.destination.readable()
        if self.condition:
            response += ' if %s' % self.condition.readable()
        return response class LocationQuery(Query):
    """Where queries"""
    def __init__(self, theme):
        self.theme = theme

    def __str__(self, lvl=0):
        indent = '\t'*(lvl)
        return '\n' + indent + 'LocationQuery: \n' + \
               indent + '\tTheme: %s\n' % self.theme.__str__(lvl + 1) class Assertion(object):
    """Asserts the existence or property of an Entity in the world."""

    def __init__(self, theme, location, existential=False):
        self.theme = theme
        self.location = location
        self.existential = existential

    def readable(self):
        return '{!r} is/are in {!r}'.format(self.theme.readable(case=True), self.location.readable())

    def __str__(self, lvl=0):
        indent = '\t'*(lvl)
        return 'Assertion: \n' + \
            (indent + '\tTheme: %s\n' % self.theme.__str__(lvl + 1) if self.theme else '') + \
            (indent + '\tLocation: %s\n' % self.location.__str__(lvl + 1) if self.location else '')+ \
            indent + '\tExistential: %s' % str(self.existential)

    def __repr__(self):
        return str(self) class Event(object):
    """An event in the environment."""

    def __init__(self, theme, sensor):
        self.theme = theme
        self.sensor = sensor

    def __str__(self, lvl=0):
        indent = '\t'*(lvl)
        return 'Event:\n' + \
               indent + '\tSensor: ' + str(self.sensor) + '\n' + \
               (indent + '\tTheme: ' + self.theme.__str__(lvl + 1) if self.theme else '')

    def __repr__(self):
        return str(self)

    def readable(self):
        return 'I %s %s' % (self.sensor, self.theme.readable(case=False)) ACTION_ALIASES = {
                  'appear': GO_ACTION,
                  'get': GET_ACTION,
                  'obtain': GET_ACTION,
                  'meander': GO_ACTION,
                  'slide': GO_ACTION,
                  'nonvehicle': GO_ACTION,
                  'escape': GO_ACTION,
                  'rummage': SEARCH_ACTION,
                  'characterize': SEE_ACTION,
                  'chase': FOLLOW_ACTION,
                  'lodge': STAY_ACTION,
                  SEARCH_ACTION: SEARCH_ACTION,
                  GO_ACTION: GO_ACTION,
                  GET_ACTION: GET_ACTION,
                  FOLLOW_ACTION: FOLLOW_ACTION,
                  SEE_ACTION: SEE_ACTION,
                  TELL_ACTION: TELL_ACTION,
                  BEGIN_ACTION: BEGIN_ACTION,
                  ACTIVATE_ACTION: ACTIVATE_ACTION,
                  DEACTIVATE_ACTION: DEACTIVATE_ACTION,
                  AVOID_ACTION: AVOID_ACTION,
                  PATROL_ACTION: PATROL_ACTION,
                  CARRY_ACTION: CARRY_ACTION,
                  STAY_ACTION: STAY_ACTION,
                  DEFUSE_ACTION: DEFUSE_ACTION,
                 }
from semantics.frames import split_clauses, activize_clause, is_existential, invert_clause, \
    get_wh_question_type, is_yn_question, pick_best_match, existential_there_insertion, \
    wh_movement, split_conjunctions, find_verbs, create_VerbFrameObjects
from semantics.tree import Tree
from semantics.wntools import morphy
from semantics.new_structures import Location, ObjectEntity, YNQuery, StatusQuery, \
    EntityQuery, Command, LocationQuery, Assertion, Event
from semantics.lexical_constants import ACTION_ALIASES
                                print 'with'
                                print '\t', str(tree)
                            match_list.append((match, vfo.classid))

                    if EXTRACT_DEBUG:
                        print 'Match list:'

                        for m in match_list:
                            print 'Sense:', m[1]
                            for a, b in m[0].items():
                                print a, str(b)
                            print '\n\n'

                    (best_match, sense) = pick_best_match(match_list)

                    if EXTRACT_DEBUG:
                        print 'Chose: '
                        if best_match:
                            print sense
                            for a, b in best_match.items():
                                print a, str(b)
                        else:
                            print str(None)
                        print '\n\n'
                    if not best_match is None:
                        result_list.append((best_match, tree, tag_list, sense, verb, negation))

    return result_list


def extract_entity(parse_tree, semantic_role=''):
    """Creates an entity object given a snippet of a parse tree."""
    entity = Location() if semantic_role in ('Location', 'Source', 'Destination') else ObjectEntity()

    # print 'Extracting from:'
    # print str(parse_tree)

    # Ignore rescursed trees and added descriptions
    ignore_positions = []
    previous_node = None
    previous_leaves = None
    for position in parse_tree.treepositions():
        if not isinstance(parse_tree[position], Tree):
            continue
        if position in ignore_positions:
            continue
        subtree = parse_tree[position]
        node = subtree.node

        leaves = ' '.join(subtree.leaves()).lower()
        # A noun phrase might have sub-parts that we need to parse recursively
        # Recurse while there are NP's below the current node
        if subtree is not parse_tree and 'NP' in node:
            entity.merge(extract_entity(subtree))
            # ignore_positions should be relative to parse_tree
            ignore_positions.extend(position + subposition for subposition in subtree.treepositions())
        # A determiner cardinal node adds some information for the quantifier
        if 'DT' in node:
            entity.quantifier.fill_determiner(leaves)
        # Cardinal number sets the quantifier number
        elif node == 'CD':
            entity.quantifier.fill_cardinal(leaves)
            if entity.quantifier.number is None:
                # Not actually a number
                entity.name = leaves
        elif node == 'PRP':
            entity.name = 'Commander' if leaves in ('i', 'me') else leaves
        elif ('PP' in node and entity.name) or node in ('SBAR', 'JJ'):
            entity.description.append(leaves)
            # ignore_positions should be relative to parse_tree
            ignore_positions.extend(position + subposition for subposition in subtree.treepositions())
        elif 'NN' in node and previous_node and 'NN' in previous_node and entity.name == previous_leaves:
            entity.description.append(previous_leaves)
            entity.name = leaves
        elif 'NN' in node or node == '-NONE-':
            entity.name = morphy(leaves, 'n')
            if entity.name is None:
                entity.name = leaves
        elif node == 'RB' and leaves == 'there':
            entity.name = 'there'
        previous_node = node
        previous_leaves = leaves
    return entity


def create_semantic_structures(frame_semantic_list):
    """Take in the list of VerbNet frames and generate the semantic
    representation structures from them."""
    semantic_representation_list = []
    isConditionalNext = False
    # Whether there is a conditional in the semantic representation list waiting to be picked up
    hasConditional = False

    # Frame semantic list is a list of conjunction strings and tuples, where the
    # first element of the tuple is the frame semantics, the second element is
    # the original tree branch it came from, the third is a list of tags, and
    # the fourth is the sense.
    for frame in frame_semantic_list:
        # Check that this is a VerbNet frame and not a conjunction
        try:
            frame_items = frame[0].items()
        except AttributeError:
            if 'if' in str(frame):
                isConditionalNext = True
            frame_items = None
            #semantic_representation_list.append(frame)
            continue

        sense = frame[3].split('-')[0]
        # Get the action associated with the sense
        # If such a mapping does not exist, use the original verb
        action = ACTION_ALIASES.get(sense, frame[4])

        item_to_entity = {key: extract_entity(value, key) for key, value in frame_items}

        wh_question_type = get_wh_question_type(str(frame[1]))

        # If it's a WH-question, find the type of question it is and add the object
        if wh_question_type is not None:
            if wh_question_type == 'Status':

                semantic_representation_list.append(StatusQuery())