Debian Codegraph @

Tools/peg_generator/pegen/first_sets.py

raw
1 #!/usr/bin/env python3.8
2
3 import argparse
4 import pprint
5 import sys
6
7 from pegen.build import build_parser
8 from pegen.grammar import (
9 Alt,
10 Cut,
11 Gather,
12 GrammarVisitor,
13 Group,
14 Lookahead,
15 NamedItem,
16 NameLeaf,
17 NegativeLookahead,
18 Opt,
19 Repeat0,
20 Repeat1,
21 Rhs,
22 Rule,
23 StringLeaf,
24 )
25 from pegen.parser_generator import compute_nullables
26
27 argparser = argparse.ArgumentParser(
28 prog="calculate_first_sets",
29 description="Calculate the first sets of a grammar",
30 )
31 argparser.add_argument("grammar_file", help="The grammar file")
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]:
92 return self.visit(item.node)
93
94 def visit_Repeat0(self, item: Repeat0) -> set[str]:
95 return self.visit(item.node)
96
97 def visit_Repeat1(self, item: Repeat1) -> set[str]:
98 return self.visit(item.node)
99
100 def visit_NameLeaf(self, item: NameLeaf) -> set[str]:
101 if item.value not in self.rules:
102 return {item.value}
103
104 if item.value not in self.first_sets:
105 self.first_sets[item.value] = self.visit(self.rules[item.value])
106 return self.first_sets[item.value]
107 elif item.value in self.in_process:
108 return set()
109
110 return self.first_sets[item.value]
111
112 def visit_StringLeaf(self, item: StringLeaf) -> set[str]:
113 return {item.value}
114
115 def visit_Rhs(self, item: Rhs) -> set[str]:
116 result: set[str] = set()
117 for alt in item.alts:
118 result |= self.visit(alt)
119 return result
120
121 def visit_Rule(self, item: Rule) -> set[str]:
122 if item.name in self.in_process:
123 return set()
124 elif item.name not in self.first_sets:
125 self.in_process.add(item.name)
126 terminals = self.visit(item.rhs)
127 if item in self.nullables:
128 terminals.add("")
129 self.first_sets[item.name] = terminals
130 self.in_process.remove(item.name)
131 return self.first_sets[item.name]
132
133
134 def main() -> None:
135 args = argparser.parse_args()
136
137 try:
138 grammar, parser, tokenizer = build_parser(args.grammar_file)
139 except Exception as err:
140 print("ERROR: Failed to parse grammar file", err, file=sys.stderr)
141 sys.exit(1)
142
143 firs_sets = FirstSetCalculator(grammar.rules).calculate()
144 pprint.pprint(firs_sets)
145
146
147 if __name__ == "__main__":
148 main()