CompilingPrincipleTools/grammar.py at master · ceerRep/CompilingPrincipleTools · 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
123
124
#! /usr/bin/env python3

from copy import deepcopy
from typing import *
from production import *

__all__ = ['Grammar', 'EOF']

EOF = '#'


class Grammar:
    __slots__ = ['target', 'production', 'first', 'follow', 'symbols']

    def __init__(self, target: str):
        self.target: str = target
        self.production: Dict[str, Set[Production]] = {}
        self.first: Dict[str, Set[str]] = {}
        self.follow: Dict[str, Set[str]] = {}
        self.symbols: Set[str] = set()

    @staticmethod
    def is_terminal(x: str) -> bool:
        return not x[0].isupper()

    def add_production(self, production: Production):
        if production.target not in self.production:
            self.production[production.target] = set()

        production = deepcopy(production)

        self.production[production.target].add(production)

        self.symbols.add(production.target)
        self.first[production.target] = set()
        self.follow[production.target] = set()
        for x in production.rule:
            self.symbols.add(x)
            self.first[x] = set()
            self.follow[x] = set()
        return self

    def calc_first(self):
        updated = True
        while updated:
            updated = False
            for symbol in self.symbols:
                if self.is_terminal(symbol):
                    if symbol not in self.first[symbol]:
                        self.first[symbol].add(symbol)
                        updated = True
                else:
                    for rule in self.production[symbol]:
                        if not rule.rule:
                            if '' not in self.first[symbol]:
                                self.first[symbol].add('')
                                updated = True
                        else:
                            for naive in rule.rule:
                                to_break = True
                                for item in self.first[naive]:
                                    if item:
                                        if item not in self.first[symbol]:
                                            self.first[symbol].add(item)
                                            updated = True
                                    else:
                                        to_break = False
                                if to_break:
                                    break
                            else:
                                self.first[symbol].add('')
                                updated = True

    def calc_follow(self):
        self.follow[self.target].add(EOF)
        updated = True

        while updated:
            updated = False

            for target, rules in self.production.items():
                for rule in rules:
                    for s1, s2 in zip(rule.rule[:-1], rule.rule[1:]):
                        for symbol in self.first[s2]:
                            if symbol and symbol not in self.follow[s1]:
                                self.follow[s1].add(symbol)
                                updated = True
                    for s1, s2, s3 in zip(rule.rule[:-2], rule.rule[1:-1], rule.rule[2:]):
                        if '' not in self.first[s2]:
                            continue
                        for symbol in self.first[s3]:
                            if symbol and symbol not in self.follow[s1]:
                                self.follow[s1].add(symbol)
                                updated = True

                    if len(rule.rule) >= 1:
                        last = rule.rule[-1]
                        for symbol in self.follow[target]:
                            if symbol not in self.follow[last]:
                                self.follow[last].add(symbol)
                                updated = True

                    if len(rule.rule) >= 2:
                        last1, last = rule.rule[-2:]
                        if '' in self.first[last]:
                            for symbol in self.follow[target]:
                                if symbol not in self.follow[last1]:
                                    self.follow[last1].add(symbol)
                                    updated = True


if __name__ == '__main__':
    grammar = Grammar('S') \
        .add_production(Production('S', ['a', 'F', 'S1'])) \
        .add_production(Production('S', ['+', 'a', 'F', 'S1'])) \
        .add_production(Production('S1', ['+', 'a', 'F', 'S1'])) \
        .add_production(Production('S1', [])) \
        .add_production(Production('F', ['*', 'a', 'F'])) \
        .add_production(Production('F', ['*', 'a']))

    grammar.calc_first()
    grammar.calc_follow()
    print(grammar.first)
    print(grammar.follow)