pyformlang/pyformlang/cfg/parse_tree.py at e63bd9d745feb057f332b74a2e0a2121b1b2d663 · FormalLanguageConstrainedPathQuerying/pyformlang · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
""" A parse Tree """

from typing import List

from networkx import DiGraph
from networkx.drawing.nx_pydot import write_dot

from ..objects.cfg_objects import CFGObject, Variable


class ParseTree:
    """ A parse tree """

    def __init__(self, value: CFGObject) -> None:
        self.value = value
        self.sons: List[ParseTree] = []

    def __repr__(self) -> str:
        return "ParseTree(" + str(self.value) + ", " + str(self.sons) + ")"

    def get_leftmost_derivation(self) -> List[List[CFGObject]]:
        """
        Get the leftmost derivation

        Returns
        -------
        derivation : list of list of :class:`~pyformlang.cfg.CFGObject`
            The derivation

        """
        if len(self.sons) == 0 and isinstance(self.value, Variable):
            return [[self.value], []]
        if len(self.sons) == 0:
            return [[self.value]]
        res = [[self.value]]
        start = []
        for i, son in enumerate(self.sons):
            end = [x.value for x in self.sons[i + 1:]]
            derivation = []
            derivations = son.get_leftmost_derivation()
            if i != 0 and derivations and derivations[0]:
                del derivations[0]
            for derivation in derivations:
                res.append(start + derivation + end)
            if derivation:
                start = start + derivation
            else:
                start.append(son.value)
        return res

    def get_rightmost_derivation(self) -> List[List[CFGObject]]:
        """
        Get the leftmost derivation

        Returns
        -------
        derivation : list of list of :class:`~pyformlang.cfg.CFGObject`
            The derivation

        """
        if len(self.sons) == 0 and isinstance(self.value, Variable):
            return [[self.value], []]
        if len(self.sons) == 0:
            return [[self.value]]
        res = [[self.value]]
        end = []
        for i, son in enumerate(self.sons[::-1]):
            start = [x.value for x in self.sons[:-1 - i]]
            derivation = []
            derivations = son.get_rightmost_derivation()
            if i != 0 and derivations and derivations[0]:
                del derivations[0]
            for derivation in derivations:
                res.append(start + derivation + end)
            end = derivation + end
        return res

    def to_networkx(self) -> DiGraph:
        """
        Transforms the tree into a Networkx Directed Graph

        Returns
        -------
        tree : networkx.Digraph
            The tree in Networkx format.

        """
        tree = DiGraph()
        tree.add_node("ROOT", label=self.value.value)
        to_process = [("ROOT", son) for son in self.sons[::-1]]
        counter = 0
        while to_process:
            previous_node, current_node = to_process.pop()
            new_node = str(counter)
            if isinstance(current_node.value, str):
                tree.add_node(new_node, label=current_node.value)
            else:
                tree.add_node(new_node, label=current_node.value.value)
            counter += 1
            tree.add_edge(previous_node, new_node)
            to_process += [(new_node, son) for son in current_node.sons[::-1]]
        return tree

    def write_as_dot(self, filename: str) -> None:
        """
        Write the parse tree in dot format into a file

        Parameters
        ----------
        filename : str
            The filename where to write the dot file

        """
        write_dot(self.to_networkx(), filename)


class DerivationDoesNotExist(Exception):
    """Exception raised when the word cannot be derived"""


class NotParsableException(Exception):
    """When the grammar cannot be parsed (parser not powerful enough)"""