Debian Codegraph @

Tools/peg_generator/pegen/grammar.py

raw
1 from __future__ import annotations
2
3 from collections.abc import Iterable, Iterator, Set
4 from typing import Any
5
6
7 class GrammarError(Exception):
8 pass
9
10
11 class GrammarVisitor:
12 def visit(self, node: Any, *args: Any, **kwargs: Any) -> Any:
13 """Visit a node."""
14 method = "visit_" + node.__class__.__name__
15 visitor = getattr(self, method, self.generic_visit)
16 return visitor(node, *args, **kwargs)
17
18 def generic_visit(self, node: Iterable[Any], *args: Any, **kwargs: Any) -> Any:
19 """Called if no explicit visitor function exists for a node."""
20 for value in node:
21 if isinstance(value, list):
22 for item in value:
23 self.visit(item, *args, **kwargs)
24 else:
25 self.visit(value, *args, **kwargs)
26
27
28 class Grammar:
29 def __init__(self, rules: Iterable[Rule], metas: Iterable[tuple[str, str | None]]):
30 # Check if there are repeated rules in "rules"
31 all_rules = {}
32 for rule in rules:
33 if rule.name in all_rules:
34 raise GrammarError(f"Repeated rule {rule.name!r}")
35 all_rules[rule.name] = rule
36 self.rules = all_rules
37 self.metas = dict(metas)
38
39 def __str__(self) -> str:
40 return "\n".join(str(rule) for name, rule in self.rules.items())
41
42 def __repr__(self) -> str:
43 lines = ["Grammar("]
44 lines.append(" [")
45 for rule in self.rules.values():
46 lines.append(f" {repr(rule)},")
47 lines.append(" ],")
48 lines.append(" {repr(list(self.metas.items()))}")
49 lines.append(")")
50 return "\n".join(lines)
51
52 def __iter__(self) -> Iterator[Rule]:
53 yield from self.rules.values()
54
55
56 # Global flag whether we want actions in __str__() -- default off.
57 SIMPLE_STR = True
58
59
60 class Rule:
61 def __init__(self, name: str, type: str | None, rhs: Rhs, memo: object | None = None):
62 self.name = name
63 self.type = type
64 self.rhs = rhs
65 self.memo = bool(memo)
66 self.left_recursive = False
67 self.leader = False
68
69 def is_loop(self) -> bool:
70 return self.name.startswith("_loop")
71
72 def is_gather(self) -> bool:
73 return self.name.startswith("_gather")
74
75 def __str__(self) -> str:
76 if SIMPLE_STR or self.type is None:
77 res = f"{self.name}: {self.rhs}"
78 else:
79 res = f"{self.name}[{self.type}]: {self.rhs}"
80 if len(res) < 88:
81 return res
82 lines = [res.split(":")[0] + ":"]
83 lines += [f" | {alt}" for alt in self.rhs.alts]
84 return "\n".join(lines)
85
86 def __repr__(self) -> str:
87 return f"Rule({self.name!r}, {self.type!r}, {self.rhs!r})"
88
89 def __iter__(self) -> Iterator[Rhs]:
90 yield self.rhs
91
92 def flatten(self) -> Rhs:
93 # If it's a single parenthesized group, flatten it.
94 rhs = self.rhs
95 if (
96 not self.is_loop()
97 and len(rhs.alts) == 1
98 and len(rhs.alts[0].items) == 1
99 and isinstance(rhs.alts[0].items[0].item, Group)
100 ):
101 rhs = rhs.alts[0].items[0].item.rhs
102 return rhs
103
104
105 class Leaf:
106 def __init__(self, value: str):
107 self.value = value
108
109 def __str__(self) -> str:
110 return self.value
111
112 def __iter__(self) -> Iterable[str]:
113 yield from ()
114
115
116 class NameLeaf(Leaf):
117 """The value is the name."""
118
119 def __str__(self) -> str:
120 if self.value == "ENDMARKER":
121 return "$"
122 return super().__str__()
123
124 def __repr__(self) -> str:
125 return f"NameLeaf({self.value!r})"
126
127
128 class StringLeaf(Leaf):
129 """The value is a string literal, including quotes."""
130
131 def __repr__(self) -> str:
132 return f"StringLeaf({self.value!r})"
133
134
135 class Rhs:
136 def __init__(self, alts: list[Alt]):
137 self.alts = alts
138 self.memo: tuple[str | None, str] | None = None
139
140 def __str__(self) -> str:
141 return " | ".join(str(alt) for alt in self.alts)
142
143 def __repr__(self) -> str:
144 return f"Rhs({self.alts!r})"
145
146 def __iter__(self) -> Iterator[list[Alt]]:
147 yield self.alts
148
149 @property
150 def can_be_inlined(self) -> bool:
151 if len(self.alts) != 1 or len(self.alts[0].items) != 1:
152 return False
153 # If the alternative has an action we cannot inline
154 if getattr(self.alts[0], "action", None) is not None:
155 return False
156 return True
157
158
159 class Alt:
160 def __init__(self, items: list[NamedItem], *, icut: int = -1, action: str | None = None):
161 self.items = items
162 self.icut = icut
163 self.action = action
164
165 def __str__(self) -> str:
166 core = " ".join(str(item) for item in self.items)
167 if not SIMPLE_STR and self.action:
168 return f"{core} {{ {self.action} }}"
169 else:
170 return core
171
172 def __repr__(self) -> str:
173 args = [repr(self.items)]
174 if self.icut >= 0:
175 args.append(f"icut={self.icut}")
176 if self.action:
177 args.append(f"action={self.action!r}")
178 return f"Alt({', '.join(args)})"
179
180 def __iter__(self) -> Iterator[list[NamedItem]]:
181 yield self.items
182
183
184 class NamedItem:
185 def __init__(self, name: str | None, item: Item, type: str | None = None):
186 self.name = name
187 self.item = item
188 self.type = type
189
190 def __str__(self) -> str:
191 if not SIMPLE_STR and self.name:
192 return f"{self.name}={self.item}"
193 else:
194 return str(self.item)
195
196 def __repr__(self) -> str:
197 return f"NamedItem({self.name!r}, {self.item!r})"
198
199 def __iter__(self) -> Iterator[Item]:
200 yield self.item
201
202
203 class Forced:
204 def __init__(self, node: Plain):
205 self.node = node
206
207 def __str__(self) -> str:
208 return f"&&{self.node}"
209
210 def __iter__(self) -> Iterator[Plain]:
211 yield self.node
212
213
214 class Lookahead:
215 def __init__(self, node: Plain, sign: str):
216 self.node = node
217 self.sign = sign
218
219 def __str__(self) -> str:
220 return f"{self.sign}{self.node}"
221
222 def __iter__(self) -> Iterator[Plain]:
223 yield self.node
224
225
226 class PositiveLookahead(Lookahead):
227 def __init__(self, node: Plain):
228 super().__init__(node, "&")
229
230 def __repr__(self) -> str:
231 return f"PositiveLookahead({self.node!r})"
232
233
234 class NegativeLookahead(Lookahead):
235 def __init__(self, node: Plain):
236 super().__init__(node, "!")
237
238 def __repr__(self) -> str:
239 return f"NegativeLookahead({self.node!r})"
240
241
242 class Opt:
243 def __init__(self, node: Item):
244 self.node = node
245
246 def __str__(self) -> str:
247 s = str(self.node)
248 # TODO: Decide whether to use [X] or X? based on type of X
249 if " " in s:
250 return f"[{s}]"
251 else:
252 return f"{s}?"
253
254 def __repr__(self) -> str:
255 return f"Opt({self.node!r})"
256
257 def __iter__(self) -> Iterator[Item]:
258 yield self.node
259
260
261 class Repeat:
262 """Shared base class for x* and x+."""
263
264 def __init__(self, node: Plain):
265 self.node = node
266 self.memo: tuple[str | None, str] | None = None
267
268 def __iter__(self) -> Iterator[Plain]:
269 yield self.node
270
271
272 class Repeat0(Repeat):
273 def __str__(self) -> str:
274 s = str(self.node)
275 # TODO: Decide whether to use (X)* or X* based on type of X
276 if " " in s:
277 return f"({s})*"
278 else:
279 return f"{s}*"
280
281 def __repr__(self) -> str:
282 return f"Repeat0({self.node!r})"
283
284
285 class Repeat1(Repeat):
286 def __str__(self) -> str:
287 s = str(self.node)
288 # TODO: Decide whether to use (X)+ or X+ based on type of X
289 if " " in s:
290 return f"({s})+"
291 else:
292 return f"{s}+"
293
294 def __repr__(self) -> str:
295 return f"Repeat1({self.node!r})"
296
297
298 class Gather(Repeat):
299 def __init__(self, separator: Plain, node: Plain):
300 self.separator = separator
301 self.node = node
302
303 def __str__(self) -> str:
304 return f"{self.separator!s}.{self.node!s}+"
305
306 def __repr__(self) -> str:
307 return f"Gather({self.separator!r}, {self.node!r})"
308
309
310 class Group:
311 def __init__(self, rhs: Rhs):
312 self.rhs = rhs
313
314 def __str__(self) -> str:
315 return f"({self.rhs})"
316
317 def __repr__(self) -> str:
318 return f"Group({self.rhs!r})"
319
320 def __iter__(self) -> Iterator[Rhs]:
321 yield self.rhs
322
323
324 class Cut:
325 def __init__(self) -> None:
326 pass
327
328 def __repr__(self) -> str:
329 return "Cut()"
330
331 def __str__(self) -> str:
332 return "~"
333
334 def __iter__(self) -> Iterator[tuple[str, str]]:
335 yield from ()
336
337 def __eq__(self, other: object) -> bool:
338 if not isinstance(other, Cut):
339 return NotImplemented
340 return True
341
342 def initial_names(self) -> Set[str]:
343 return set()
344
345
346 Plain = Leaf | Group
347 Item = Plain | Opt | Repeat | Forced | Lookahead | Rhs | Cut
348 RuleName = tuple[str, str | None]
349 MetaTuple = tuple[str, str | None]
350 MetaList = list[MetaTuple]
351 RuleList = list[Rule]
352 NamedItemList = list[NamedItem]
353 LookaheadOrCut = Lookahead | Cut