Debian Codegraph @

Tools/peg_generator/pegen/parser_generator.py

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