| 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 |