Debian Codegraph @

Tools/peg_generator/pegen/parser_generator.py

raw
1 import ast
2 import contextlib
3 import re
4 from abc import abstractmethod
5 from collections.abc import Iterable, Iterator, Set
6 from typing import (
7 IO,
8 Any,
9 )
10
11 from pegen import sccutils
12 from pegen.grammar import (
13 Alt,
14 Cut,
15 Forced,
16 Gather,
17 Grammar,
18 GrammarError,
19 GrammarVisitor,
20 Group,
21 Lookahead,
22 NamedItem,
23 NameLeaf,
24 Opt,
25 Plain,
26 Repeat0,
27 Repeat1,
28 Rhs,
29 Rule,
30 StringLeaf,
31 )
32
33
34 class RuleCollectorVisitor(GrammarVisitor):
35 """Visitor that invokes a provieded callmaker visitor with just the NamedItem nodes"""
36
37 def __init__(self, rules: dict[str, Rule], callmakervisitor: GrammarVisitor) -> None:
38 self.rules = rules
39 self.callmaker = callmakervisitor
40
41 def visit_Rule(self, rule: Rule) -> None:
42 self.visit(rule.flatten())
43
44 def visit_NamedItem(self, item: NamedItem) -> None:
45 self.callmaker.visit(item)
46
47
48 class KeywordCollectorVisitor(GrammarVisitor):
49 """Visitor that collects all the keywords and soft keywords in the Grammar"""
50
51 def __init__(self, gen: "ParserGenerator", keywords: dict[str, int], soft_keywords: set[str]):
52 self.generator = gen
53 self.keywords = keywords
54 self.soft_keywords = soft_keywords
55
56 def visit_StringLeaf(self, node: StringLeaf) -> None:
57 val = ast.literal_eval(node.value)
58 if re.match(r"[a-zA-Z_]\w*\Z", val): # This is a keyword
59 if node.value.endswith("'") and node.value not in self.keywords:
60 self.keywords[val] = self.generator.keyword_type()
61 else:
62 return self.soft_keywords.add(node.value.replace('"', ""))
63
64
65 class RuleCheckingVisitor(GrammarVisitor):
66 def __init__(self, rules: dict[str, Rule], tokens: set[str]):
67 self.rules = rules
68 self.tokens = tokens
69
70 def visit_NameLeaf(self, node: NameLeaf) -> None:
71 if node.value not in self.rules and node.value not in self.tokens:
72 raise GrammarError(f"Dangling reference to rule {node.value!r}")
73
74 def visit_NamedItem(self, node: NamedItem) -> None:
75 if node.name and node.name.startswith("_"):
76 raise GrammarError(f"Variable names cannot start with underscore: '{node.name}'")
77 self.visit(node.item)
78
79
80 class ParserGenerator:
81 callmakervisitor: GrammarVisitor
82
83 def __init__(self, grammar: Grammar, tokens: set[str], file: IO[str] | None):
84 self.grammar = grammar
85 self.tokens = tokens
86 self.keywords: dict[str, int] = {}
87 self.soft_keywords: set[str] = set()
88 self.rules = grammar.rules
89 self.validate_rule_names()
90 if "trailer" not in grammar.metas and "start" not in self.rules:
91 raise GrammarError("Grammar without a trailer must have a 'start' rule")
92 checker = RuleCheckingVisitor(self.rules, self.tokens)
93 for rule in self.rules.values():
94 checker.visit(rule)
95 self.file = file
96 self.level = 0
97 self.first_graph, self.first_sccs = compute_left_recursives(self.rules)
98 self.counter = 0 # For name_rule()/name_loop()
99 self.keyword_counter = 499 # For keyword_type()
100 self.all_rules: dict[str, Rule] = self.rules.copy() # Rules + temporal rules
101 self._local_variable_stack: list[list[str]] = []
102
103 def validate_rule_names(self) -> None:
104 for rule in self.rules:
105 if rule.startswith("_"):
106 raise GrammarError(f"Rule names cannot start with underscore: '{rule}'")
107
108 @contextlib.contextmanager
109 def local_variable_context(self) -> Iterator[None]:
110 self._local_variable_stack.append([])
111 yield
112 self._local_variable_stack.pop()
113
114 @property
115 def local_variable_names(self) -> list[str]:
116 return self._local_variable_stack[-1]
117
118 @abstractmethod
119 def generate(self, filename: str) -> None:
120 raise NotImplementedError
121
122 @contextlib.contextmanager
123 def indent(self) -> Iterator[None]:
124 self.level += 1
125 try:
126 yield
127 finally:
128 self.level -= 1
129
130 def print(self, *args: object) -> None:
131 if not args:
132 print(file=self.file)
133 else:
134 print(" " * self.level, end="", file=self.file)
135 print(*args, file=self.file)
136
137 def printblock(self, lines: str) -> None:
138 for line in lines.splitlines():
139 self.print(line)
140
141 def collect_rules(self) -> None:
142 keyword_collector = KeywordCollectorVisitor(self, self.keywords, self.soft_keywords)
143 for rule in self.all_rules.values():
144 keyword_collector.visit(rule)
145
146 rule_collector = RuleCollectorVisitor(self.rules, self.callmakervisitor)
147 done: set[str] = set()
148 while True:
149 computed_rules = list(self.all_rules)
150 todo = [i for i in computed_rules if i not in done]
151 if not todo:
152 break
153 done = set(self.all_rules)
154 for rulename in todo:
155 rule_collector.visit(self.all_rules[rulename])
156
157 def keyword_type(self) -> int:
158 self.keyword_counter += 1
159 return self.keyword_counter
160
161 def artifical_rule_from_rhs(self, rhs: Rhs) -> str:
162 self.counter += 1
163 name = f"_tmp_{self.counter}" # TODO: Pick a nicer name.
164 self.all_rules[name] = Rule(name, None, rhs)
165 return name
166
167 def artificial_rule_from_repeat(self, node: Plain, is_repeat1: bool) -> str:
168 self.counter += 1
169 if is_repeat1:
170 prefix = "_loop1_"
171 else:
172 prefix = "_loop0_"
173 name = f"{prefix}{self.counter}"
174 self.all_rules[name] = Rule(name, None, Rhs([Alt([NamedItem(None, node)])]))
175 return name
176
177 def artifical_rule_from_gather(self, node: Gather) -> str:
178 self.counter += 1
179 name = f"_gather_{self.counter}"
180 self.counter += 1
181 extra_function_name = f"_loop0_{self.counter}"
182 extra_function_alt = Alt(
183 [NamedItem(None, node.separator), NamedItem("elem", node.node)],
184 action="elem",
185 )
186 self.all_rules[extra_function_name] = Rule(
187 extra_function_name,
188 None,
189 Rhs([extra_function_alt]),
190 )
191 alt = Alt(
192 [NamedItem("elem", node.node), NamedItem("seq", NameLeaf(extra_function_name))],
193 )
194 self.all_rules[name] = Rule(
195 name,
196 None,
197 Rhs([alt]),
198 )
199 return name
200
201 def dedupe(self, name: str) -> str:
202 origname = name
203 counter = 0
204 while name in self.local_variable_names:
205 counter += 1
206 name = f"{origname}_{counter}"
207 self.local_variable_names.append(name)
208 return name
209
210
211 class NullableVisitor(GrammarVisitor):
212 def __init__(self, rules: dict[str, Rule]) -> None:
213 self.rules = rules
214 self.visited: set[Any] = set()
215 self.nullables: set[Rule | NamedItem] = set()
216
217 def visit_Rule(self, rule: Rule) -> bool:
218 if rule in self.visited:
219 return False
220 self.visited.add(rule)
221 if self.visit(rule.rhs):
222 self.nullables.add(rule)
223 return rule in self.nullables
224
225 def visit_Rhs(self, rhs: Rhs) -> bool:
226 for alt in rhs.alts:
227 if self.visit(alt):
228 return True
229 return False
230
231 def visit_Alt(self, alt: Alt) -> bool:
232 for item in alt.items:
233 if not self.visit(item):
234 return False
235 return True
236
237 def visit_Forced(self, force: Forced) -> bool:
238 return True
239
240 def visit_LookAhead(self, lookahead: Lookahead) -> bool:
241 return True
242
243 def visit_Opt(self, opt: Opt) -> bool:
244 return True
245
246 def visit_Repeat0(self, repeat: Repeat0) -> bool:
247 return True
248
249 def visit_Repeat1(self, repeat: Repeat1) -> bool:
250 return False
251
252 def visit_Gather(self, gather: Gather) -> bool:
253 return False
254
255 def visit_Cut(self, cut: Cut) -> bool:
256 return False
257
258 def visit_Group(self, group: Group) -> bool:
259 return self.visit(group.rhs)
260
261 def visit_NamedItem(self, item: NamedItem) -> bool:
262 if self.visit(item.item):
263 self.nullables.add(item)
264 return item in self.nullables
265
266 def visit_NameLeaf(self, node: NameLeaf) -> bool:
267 if node.value in self.rules:
268 return self.visit(self.rules[node.value])
269 # Token or unknown; never empty.
270 return False
271
272 def visit_StringLeaf(self, node: StringLeaf) -> bool:
273 # The string token '' is considered empty.
274 return not node.value
275
276
277 def compute_nullables(rules: dict[str, Rule]) -> set[Any]:
278 """Compute which rules in a grammar are nullable.
279
280 Thanks to TatSu (tatsu/leftrec.py) for inspiration.
281 """
282 nullable_visitor = NullableVisitor(rules)
283 for rule in rules.values():
284 nullable_visitor.visit(rule)
285 return nullable_visitor.nullables
286
287
288 class InitialNamesVisitor(GrammarVisitor):
289 def __init__(self, rules: dict[str, Rule]) -> None:
290 self.rules = rules
291 self.nullables = compute_nullables(rules)
292
293 def generic_visit(self, node: Iterable[Any], *args: Any, **kwargs: Any) -> set[Any]:
294 names: set[str] = set()
295 for value in node:
296 if isinstance(value, list):
297 for item in value:
298 names |= self.visit(item, *args, **kwargs)
299 else:
300 names |= self.visit(value, *args, **kwargs)
301 return names
302
303 def visit_Alt(self, alt: Alt) -> set[Any]:
304 names: set[str] = set()
305 for item in alt.items:
306 names |= self.visit(item)
307 if item not in self.nullables:
308 break
309 return names
310
311 def visit_Forced(self, force: Forced) -> set[Any]:
312 return set()
313
314 def visit_LookAhead(self, lookahead: Lookahead) -> set[Any]:
315 return set()
316
317 def visit_Cut(self, cut: Cut) -> set[Any]:
318 return set()
319
320 def visit_NameLeaf(self, node: NameLeaf) -> set[Any]:
321 return {node.value}
322
323 def visit_StringLeaf(self, node: StringLeaf) -> set[Any]:
324 return set()
325
326
327 def compute_left_recursives(
328 rules: dict[str, Rule]
329 ) -> tuple[dict[str, Set[str]], list[Set[str]]]:
330 graph = make_first_graph(rules)
331 sccs = list(sccutils.strongly_connected_components(graph.keys(), graph))
332 for scc in sccs:
333 if len(scc) > 1:
334 for name in scc:
335 rules[name].left_recursive = True
336 # Try to find a leader such that all cycles go through it.
337 leaders = set(scc)
338 for start in scc:
339 for cycle in sccutils.find_cycles_in_scc(graph, scc, start):
340 # print("Cycle:", " -> ".join(cycle))
341 leaders -= scc - set(cycle)
342 if not leaders:
343 raise ValueError(
344 f"SCC {scc} has no leadership candidate (no element is included in all cycles)"
345 )
346 # print("Leaders:", leaders)
347 leader = min(leaders) # Pick an arbitrary leader from the candidates.
348 rules[leader].leader = True
349 else:
350 name = min(scc) # The only element.
351 if name in graph[name]:
352 rules[name].left_recursive = True
353 rules[name].leader = True
354 return graph, sccs
355
356
357 def make_first_graph(rules: dict[str, Rule]) -> dict[str, Set[str]]:
358 """Compute the graph of left-invocations.
359
360 There's an edge from A to B if A may invoke B at its initial
361 position.
362
363 Note that this requires the nullable flags to have been computed.
364 """
365 initial_name_visitor = InitialNamesVisitor(rules)
366 graph = {}
367 vertices: set[str] = set()
368 for rulename, rhs in rules.items():
369 graph[rulename] = names = initial_name_visitor.visit(rhs)
370 vertices |= names
371 for vertex in vertices:
372 graph.setdefault(vertex, set())
373 return graph