Multi-Parser-Visualizer-with-AI-Assisted-Grammar-Analysis/first_follow.py at main · abhimanyuHatesToCode/Multi-Parser-Visualizer-with-AI-Assisted-Grammar-Analysis · 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
class FirstFollow:
    def __init__(self, grammar):
        self.grammar = grammar
        self.first = {}
        self.follow = {}

        for nt in grammar.non_terminals:
            self.first[nt] = set()
            self.follow[nt] = set()


    # ---------------- FIRST ----------------
    def compute_first(self):
        changed = True

        while changed:
            changed = False

            for lhs in self.grammar.productions:
                for production in self.grammar.productions[lhs]:

                    # If epsilon production
                    if production == ["^"]:
                        if "^" not in self.first[lhs]:
                            self.first[lhs].add("^")
                            changed = True
                        continue

                    for symbol in production:

                        # If terminal
                        if symbol in self.grammar.terminals:
                            if symbol not in self.first[lhs]:
                                self.first[lhs].add(symbol)
                                changed = True
                            break

                        # If non-terminal
                        elif symbol in self.grammar.non_terminals:
                            before = len(self.first[lhs])

                            # Add FIRST(symbol) minus epsilon
                            self.first[lhs] |= (self.first[symbol] - {"^"})

                            if len(self.first[lhs]) > before:
                                changed = True

                            # If symbol does NOT produce epsilon, stop
                            if "^" not in self.first[symbol]:
                                break

                        # If symbol is epsilon
                        elif symbol == "^":
                            if "^" not in self.first[lhs]:
                                self.first[lhs].add("^")
                                changed = True
                            break
                    else:
                        # All symbols can produce epsilon
                        if "^" not in self.first[lhs]:
                            self.first[lhs].add("^")
                            changed = True


    # ---------------- FOLLOW ----------------
    def compute_follow(self):
        self.follow[self.grammar.start_symbol].add("$")

        changed = True
        while changed:
            changed = False

            for lhs in self.grammar.productions:
                for production in self.grammar.productions[lhs]:

                    for i, symbol in enumerate(production):

                        if symbol in self.grammar.non_terminals:

                            next_symbols = production[i+1:]

                            if next_symbols:
                                first_next = set()

                                for next_symbol in next_symbols:

                                    if next_symbol in self.grammar.terminals:
                                        first_next.add(next_symbol)
                                        break

                                    first_next |= (self.first[next_symbol] - {"^"})

                                    if "^" not in self.first[next_symbol]:
                                        break
                                else:
                                    first_next.add("^")

                                before = len(self.follow[symbol])

                                self.follow[symbol] |= (first_next - {"^"})

                                if "^" in first_next:
                                    self.follow[symbol] |= self.follow[lhs]

                                if before != len(self.follow[symbol]):
                                    changed = True
                            else:
                                before = len(self.follow[symbol])
                                self.follow[symbol] |= self.follow[lhs]

                                if before != len(self.follow[symbol]):
                                    changed = True

    def display(self):
        print("\nFIRST Sets:")
        for nt in sorted(self.first):
            print(f"FIRST({nt}) = {self.first[nt]}")

        print("\nFOLLOW Sets:")
        for nt in sorted(self.follow):
            print(f"FOLLOW({nt}) = {self.follow[nt]}")