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