Debian Codegraph @

Tools/peg_generator/pegen/parser.py

raw
1 import argparse
2 import sys
3 import time
4 import token
5 import tokenize
6 import traceback
7 from abc import abstractmethod
8 from collections.abc import Callable
9 from typing import Any, ClassVar, TypeVar, cast
10
11 from pegen.tokenizer import Mark, Tokenizer, exact_token_types
12
13 T = TypeVar("T")
14 F = TypeVar("F", bound=Callable[..., Any])
15
16
17 def logger(method: F) -> F:
18 """For non-memoized functions that we want to be logged.
19
20 (In practice this is only non-leader left-recursive functions.)
21 """
22 method_name = method.__name__
23
24 def logger_wrapper(self: "Parser", *args: object) -> Any:
25 if not self._verbose:
26 return method(self, *args)
27 argsr = ",".join(repr(arg) for arg in args)
28 fill = " " * self._level
29 print(f"{fill}{method_name}({argsr}) .... (looking at {self.showpeek()})")
30 self._level += 1
31 tree = method(self, *args)
32 self._level -= 1
33 print(f"{fill}... {method_name}({argsr}) --> {tree!s:.200}")
34 return tree
35
36 logger_wrapper.__wrapped__ = method # type: ignore[attr-defined]
37 return cast(F, logger_wrapper)
38
39
40 def memoize(method: F) -> F:
41 """Memoize a symbol method."""
42 method_name = method.__name__
43
44 def memoize_wrapper(self: "Parser", *args: object) -> Any:
45 mark = self._mark()
46 key = mark, method_name, args
47 # Fast path: cache hit, and not verbose.
48 if key in self._cache and not self._verbose:
49 tree, endmark = self._cache[key]
50 self._reset(endmark)
51 return tree
52 # Slow path: no cache hit, or verbose.
53 verbose = self._verbose
54 argsr = ",".join(repr(arg) for arg in args)
55 fill = " " * self._level
56 if key not in self._cache:
57 if verbose:
58 print(f"{fill}{method_name}({argsr}) ... (looking at {self.showpeek()})")
59 self._level += 1
60 tree = method(self, *args)
61 self._level -= 1
62 if verbose:
63 print(f"{fill}... {method_name}({argsr}) -> {tree!s:.200}")
64 endmark = self._mark()
65 self._cache[key] = tree, endmark
66 else:
67 tree, endmark = self._cache[key]
68 if verbose:
69 print(f"{fill}{method_name}({argsr}) -> {tree!s:.200}")
70 self._reset(endmark)
71 return tree
72
73 memoize_wrapper.__wrapped__ = method # type: ignore[attr-defined]
74 return cast(F, memoize_wrapper)
75
76
77 def memoize_left_rec(
78 method: Callable[["Parser"], T | None]
79 ) -> Callable[["Parser"], T | None]:
80 """Memoize a left-recursive symbol method."""
81 method_name = method.__name__
82
83 def memoize_left_rec_wrapper(self: "Parser") -> T | None:
84 mark = self._mark()
85 key = mark, method_name, ()
86 # Fast path: cache hit, and not verbose.
87 if key in self._cache and not self._verbose:
88 tree, endmark = self._cache[key]
89 self._reset(endmark)
90 return tree
91 # Slow path: no cache hit, or verbose.
92 verbose = self._verbose
93 fill = " " * self._level
94 if key not in self._cache:
95 if verbose:
96 print(f"{fill}{method_name} ... (looking at {self.showpeek()})")
97 self._level += 1
98
99 # For left-recursive rules we manipulate the cache and
100 # loop until the rule shows no progress, then pick the
101 # previous result. For an explanation why this works, see
102 # https://github.com/PhilippeSigaud/Pegged/wiki/Left-Recursion
103 # (But we use the memoization cache instead of a static
104 # variable; perhaps this is similar to a paper by Warth et al.
105 # (http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08).
106
107 # Prime the cache with a failure.
108 self._cache[key] = None, mark
109 lastresult, lastmark = None, mark
110 depth = 0
111 if verbose:
112 print(f"{fill}Recursive {method_name} at {mark} depth {depth}")
113
114 while True:
115 self._reset(mark)
116 self.in_recursive_rule += 1
117 try:
118 result = method(self)
119 finally:
120 self.in_recursive_rule -= 1
121 endmark = self._mark()
122 depth += 1
123 if verbose:
124 print(
125 f"{fill}Recursive {method_name} at {mark} depth {depth}: {result!s:.200} to {endmark}"
126 )
127 if not result:
128 if verbose:
129 print(f"{fill}Fail with {lastresult!s:.200} to {lastmark}")
130 break
131 if endmark <= lastmark:
132 if verbose:
133 print(f"{fill}Bailing with {lastresult!s:.200} to {lastmark}")
134 break
135 self._cache[key] = lastresult, lastmark = result, endmark
136
137 self._reset(lastmark)
138 tree = lastresult
139
140 self._level -= 1
141 if verbose:
142 print(f"{fill}{method_name}() -> {tree!s:.200} [cached]")
143 if tree:
144 endmark = self._mark()
145 else:
146 endmark = mark
147 self._reset(endmark)
148 self._cache[key] = tree, endmark
149 else:
150 tree, endmark = self._cache[key]
151 if verbose:
152 print(f"{fill}{method_name}() -> {tree!s:.200} [fresh]")
153 if tree:
154 self._reset(endmark)
155 return tree
156
157 memoize_left_rec_wrapper.__wrapped__ = method # type: ignore[attr-defined]
158 return memoize_left_rec_wrapper
159
160
161 class Parser:
162 """Parsing base class."""
163
164 KEYWORDS: ClassVar[tuple[str, ...]]
165
166 SOFT_KEYWORDS: ClassVar[tuple[str, ...]]
167
168 def __init__(self, tokenizer: Tokenizer, *, verbose: bool = False):
169 self._tokenizer = tokenizer
170 self._verbose = verbose
171 self._level = 0
172 self._cache: dict[tuple[Mark, str, tuple[Any, ...]], tuple[Any, Mark]] = {}
173 # Integer tracking whether we are in a left recursive rule or not. Can be useful
174 # for error reporting.
175 self.in_recursive_rule = 0
176 # Pass through common tokenizer methods.
177 self._mark = self._tokenizer.mark
178 self._reset = self._tokenizer.reset
179
180 @abstractmethod
181 def start(self) -> Any:
182 pass
183
184 def showpeek(self) -> str:
185 tok = self._tokenizer.peek()
186 return f"{tok.start[0]}.{tok.start[1]}: {token.tok_name[tok.type]}:{tok.string!r}"
187
188 @memoize
189 def name(self) -> tokenize.TokenInfo | None:
190 tok = self._tokenizer.peek()
191 if tok.type == token.NAME and tok.string not in self.KEYWORDS:
192 return self._tokenizer.getnext()
193 return None
194
195 @memoize
196 def number(self) -> tokenize.TokenInfo | None:
197 tok = self._tokenizer.peek()
198 if tok.type == token.NUMBER:
199 return self._tokenizer.getnext()
200 return None
201
202 @memoize
203 def string(self) -> tokenize.TokenInfo | None:
204 tok = self._tokenizer.peek()
205 if tok.type == token.STRING:
206 return self._tokenizer.getnext()
207 return None
208
209 @memoize
210 def fstring_start(self) -> tokenize.TokenInfo | None:
211 FSTRING_START = getattr(token, "FSTRING_START", None)
212 if not FSTRING_START:
213 return None
214 tok = self._tokenizer.peek()
215 if tok.type == FSTRING_START:
216 return self._tokenizer.getnext()
217 return None
218
219 @memoize
220 def fstring_middle(self) -> tokenize.TokenInfo | None:
221 FSTRING_MIDDLE = getattr(token, "FSTRING_MIDDLE", None)
222 if not FSTRING_MIDDLE:
223 return None
224 tok = self._tokenizer.peek()
225 if tok.type == FSTRING_MIDDLE:
226 return self._tokenizer.getnext()
227 return None
228
229 @memoize
230 def fstring_end(self) -> tokenize.TokenInfo | None:
231 FSTRING_END = getattr(token, "FSTRING_END", None)
232 if not FSTRING_END:
233 return None
234 tok = self._tokenizer.peek()
235 if tok.type == FSTRING_END:
236 return self._tokenizer.getnext()
237 return None
238
239 @memoize
240 def op(self) -> tokenize.TokenInfo | None:
241 tok = self._tokenizer.peek()
242 if tok.type == token.OP:
243 return self._tokenizer.getnext()
244 return None
245
246 @memoize
247 def type_comment(self) -> tokenize.TokenInfo | None:
248 tok = self._tokenizer.peek()
249 if tok.type == token.TYPE_COMMENT:
250 return self._tokenizer.getnext()
251 return None
252
253 @memoize
254 def soft_keyword(self) -> tokenize.TokenInfo | None:
255 tok = self._tokenizer.peek()
256 if tok.type == token.NAME and tok.string in self.SOFT_KEYWORDS:
257 return self._tokenizer.getnext()
258 return None
259
260 @memoize
261 def expect(self, type: str) -> tokenize.TokenInfo | None:
262 tok = self._tokenizer.peek()
263 if tok.string == type:
264 return self._tokenizer.getnext()
265 if type in exact_token_types:
266 if tok.type == exact_token_types[type]:
267 return self._tokenizer.getnext()
268 if type in token.__dict__:
269 if tok.type == token.__dict__[type]:
270 return self._tokenizer.getnext()
271 if tok.type == token.OP and tok.string == type:
272 return self._tokenizer.getnext()
273 return None
274
275 def expect_forced(self, res: Any, expectation: str) -> tokenize.TokenInfo | None:
276 if res is None:
277 raise self.make_syntax_error(f"expected {expectation}")
278 return res
279
280 def positive_lookahead(self, func: Callable[..., T], *args: object) -> T:
281 mark = self._mark()
282 ok = func(*args)
283 self._reset(mark)
284 return ok
285
286 def negative_lookahead(self, func: Callable[..., object], *args: object) -> bool:
287 mark = self._mark()
288 ok = func(*args)
289 self._reset(mark)
290 return not ok
291
292 def make_syntax_error(self, message: str, filename: str = "<unknown>") -> SyntaxError:
293 tok = self._tokenizer.diagnose()
294 return SyntaxError(message, (filename, tok.start[0], 1 + tok.start[1], tok.line))
295
296
297 def simple_parser_main(parser_class: type[Parser]) -> None:
298 argparser = argparse.ArgumentParser()
299 argparser.add_argument(
300 "-v",
301 "--verbose",
302 action="count",
303 default=0,
304 help="Print timing stats; repeat for more debug output",
305 )
306 argparser.add_argument(
307 "-q", "--quiet", action="store_true", help="Don't print the parsed program"
308 )
309 argparser.add_argument("filename", help="Input file ('-' to use stdin)")
310
311 args = argparser.parse_args()
312 verbose = args.verbose
313 verbose_tokenizer = verbose >= 3
314 verbose_parser = verbose == 2 or verbose >= 4
315
316 t0 = time.time()
317
318 filename = args.filename
319 if filename == "" or filename == "-":
320 filename = "<stdin>"
321 file = sys.stdin
322 else:
323 file = open(args.filename)
324 try:
325 tokengen = tokenize.generate_tokens(file.readline)
326 tokenizer = Tokenizer(tokengen, verbose=verbose_tokenizer)
327 parser = parser_class(tokenizer, verbose=verbose_parser)
328 tree = parser.start()
329 try:
330 if file.isatty():
331 endpos = 0
332 else:
333 endpos = file.tell()
334 except OSError:
335 endpos = 0
336 finally:
337 if file is not sys.stdin:
338 file.close()
339
340 t1 = time.time()
341
342 if not tree:
343 err = parser.make_syntax_error(filename)
344 traceback.print_exception(err.__class__, err, None)
345 sys.exit(1)
346
347 if not args.quiet:
348 print(tree)
349
350 if verbose:
351 dt = t1 - t0
352 diag = tokenizer.diagnose()
353 nlines = diag.end[0]
354 if diag.type == token.ENDMARKER:
355 nlines -= 1
356 print(f"Total time: {dt:.3f} sec; {nlines} lines", end="")
357 if endpos:
358 print(f" ({endpos} bytes)", end="")
359 if dt:
360 print(f"; {nlines / dt:.0f} lines/sec")
361 else:
362 print()
363 print("Caches sizes:")
364 print(f" token array : {len(tokenizer._tokens):10}")
365 print(f" cache : {len(parser._cache):10}")
366 ## print_memstats()