| 32 | |
| 33 | |
| 34 | class FirstSetCalculator(GrammarVisitor): |
| 35 | def __init__(self, rules: dict[str, Rule]) -> None: |
| 36 | self.rules = rules |
| 37 | self.nullables = compute_nullables(rules) |
| 38 | self.first_sets: dict[str, set[str]] = dict() |
| 39 | self.in_process: set[str] = set() |
| 40 | |
| 41 | def calculate(self) -> dict[str, set[str]]: |
| 42 | for name, rule in self.rules.items(): |
| 43 | self.visit(rule) |
| 44 | return self.first_sets |
| 45 | |
| 46 | def visit_Alt(self, item: Alt) -> set[str]: |
| 47 | result: set[str] = set() |
| 48 | to_remove: set[str] = set() |
| 49 | for other in item.items: |
| 50 | new_terminals = self.visit(other) |
| 51 | if isinstance(other.item, NegativeLookahead): |
| 52 | to_remove |= new_terminals |
| 53 | result |= new_terminals |
| 54 | if to_remove: |
| 55 | result -= to_remove |
| 56 | |
| 57 | # If the set of new terminals can start with the empty string, |
| 58 | # it means that the item is completely nullable and we should |
| 59 | # also considering at least the next item in case the current |
| 60 | # one fails to parse. |
| 61 | |
| 62 | if "" in new_terminals: |
| 63 | continue |
| 64 | |
| 65 | if not isinstance(other.item, (Opt, NegativeLookahead, Repeat0)): |
| 66 | break |
| 67 | |
| 68 | # Do not allow the empty string to propagate. |
| 69 | result.discard("") |
| 70 | |
| 71 | return result |
| 72 | |
| 73 | def visit_Cut(self, item: Cut) -> set[str]: |
| 74 | return set() |
| 75 | |
| 76 | def visit_Group(self, item: Group) -> set[str]: |
| 77 | return self.visit(item.rhs) |
| 78 | |
| 79 | def visit_PositiveLookahead(self, item: Lookahead) -> set[str]: |
| 80 | return self.visit(item.node) |
| 81 | |
| 82 | def visit_NegativeLookahead(self, item: NegativeLookahead) -> set[str]: |
| 83 | return self.visit(item.node) |
| 84 | |
| 85 | def visit_NamedItem(self, item: NamedItem) -> set[str]: |
| 86 | return self.visit(item.item) |
| 87 | |
| 88 | def visit_Opt(self, item: Opt) -> set[str]: |
| 89 | return self.visit(item.node) |
| 90 | |
| 91 | def visit_Gather(self, item: Gather) -> set[str]: |
no outgoing calls
searching dependent graphs…