Debian Codegraph @

Tools/cases_generator/lexer.py

raw
1 # Parser for C code
2 # Originally by Mark Shannon ([email protected])
3 # https://gist.github.com/markshannon/db7ab649440b5af765451bb77c7dba34
4
5 import re
6 from dataclasses import dataclass
7 from collections.abc import Iterator
8
9
10 def choice(*opts: str) -> str:
11 return "|".join("(%s)" % opt for opt in opts)
12
13
14 # Regexes
15
16 # Longer operators must go before shorter ones.
17
18 PLUSPLUS = r"\+\+"
19 MINUSMINUS = r"--"
20
21 # ->
22 ARROW = r"->"
23 ELLIPSIS = r"\.\.\."
24
25 # Assignment operators
26 TIMESEQUAL = r"\*="
27 DIVEQUAL = r"/="
28 MODEQUAL = r"%="
29 PLUSEQUAL = r"\+="
30 MINUSEQUAL = r"-="
31 LSHIFTEQUAL = r"<<="
32 RSHIFTEQUAL = r">>="
33 ANDEQUAL = r"&="
34 OREQUAL = r"\|="
35 XOREQUAL = r"\^="
36
37 # Operators
38 PLUS = r"\+"
39 MINUS = r"-"
40 TIMES = r"\*"
41 DIVIDE = r"/"
42 MOD = r"%"
43 NOT = r"~"
44 XOR = r"\^"
45 LOR = r"\|\|"
46 LAND = r"&&"
47 LSHIFT = r"<<"
48 RSHIFT = r">>"
49 LE = r"<="
50 GE = r">="
51 EQ = r"=="
52 NE = r"!="
53 LT = r"<"
54 GT = r">"
55 LNOT = r"!"
56 OR = r"\|"
57 AND = r"&"
58 EQUALS = r"="
59
60 # ?
61 CONDOP = r"\?"
62
63 # Delimiters
64 LPAREN = r"\("
65 RPAREN = r"\)"
66 LBRACKET = r"\["
67 RBRACKET = r"\]"
68 LBRACE = r"\{"
69 RBRACE = r"\}"
70 COMMA = r","
71 PERIOD = r"\."
72 SEMI = r";"
73 COLON = r":"
74 BACKSLASH = r"\\"
75
76 operators = {op: pattern for op, pattern in globals().items() if op == op.upper()}
77 for op in operators:
78 globals()[op] = op
79 opmap = {pattern.replace("\\", "") or "\\": op for op, pattern in operators.items()}
80
81 # Macros
82 macro = r"#.*\n"
83 CMACRO_IF = "CMACRO_IF"
84 CMACRO_ELSE = "CMACRO_ELSE"
85 CMACRO_ENDIF = "CMACRO_ENDIF"
86 CMACRO_OTHER = "CMACRO_OTHER"
87
88 id_re = r"[a-zA-Z_][0-9a-zA-Z_]*"
89 IDENTIFIER = "IDENTIFIER"
90
91
92 suffix = r"([uU]?[lL]?[lL]?)"
93 octal = r"0[0-7]+" + suffix
94 hex = r"0[xX][0-9a-fA-F]+"
95 decimal_digits = r"(0|[1-9][0-9]*)"
96 decimal = decimal_digits + suffix
97
98
99 exponent = r"""([eE][-+]?[0-9]+)"""
100 fraction = r"""([0-9]*\.[0-9]+)|([0-9]+\.)"""
101 float = "((((" + fraction + ")" + exponent + "?)|([0-9]+" + exponent + "))[FfLl]?)"
102
103 number_re = choice(octal, hex, float, decimal)
104 NUMBER = "NUMBER"
105
106 simple_escape = r"""([a-zA-Z._~!=&\^\-\\?'"])"""
107 decimal_escape = r"""(\d+)"""
108 hex_escape = r"""(x[0-9a-fA-F]+)"""
109 escape_sequence = (
110 r"""(\\(""" + simple_escape + "|" + decimal_escape + "|" + hex_escape + "))"
111 )
112 string_char = r"""([^"\\\n]|""" + escape_sequence + ")"
113 str_re = '"' + string_char + '*"'
114 STRING = "STRING"
115 char = r"\'.\'" # TODO: escape sequence
116 CHARACTER = "CHARACTER"
117
118 comment_re = r"(//.*)|/\*([^*]|\*[^/])*\*/"
119 COMMENT = "COMMENT"
120
121 newline = r"\n"
122 invalid = (
123 r"\S" # A single non-space character that's not caught by any of the other patterns
124 )
125 matcher = re.compile(
126 choice(
127 id_re,
128 number_re,
129 str_re,
130 char,
131 newline,
132 macro,
133 comment_re,
134 *operators.values(),
135 invalid,
136 )
137 )
138 letter = re.compile(r"[a-zA-Z_]")
139
140
141 kwds = []
142 AUTO = "AUTO"
143 kwds.append(AUTO)
144 BREAK = "BREAK"
145 kwds.append(BREAK)
146 CASE = "CASE"
147 kwds.append(CASE)
148 CHAR = "CHAR"
149 kwds.append(CHAR)
150 CONST = "CONST"
151 kwds.append(CONST)
152 CONTINUE = "CONTINUE"
153 kwds.append(CONTINUE)
154 DEFAULT = "DEFAULT"
155 kwds.append(DEFAULT)
156 DO = "DO"
157 kwds.append(DO)
158 DOUBLE = "DOUBLE"
159 kwds.append(DOUBLE)
160 ELSE = "ELSE"
161 kwds.append(ELSE)
162 ENUM = "ENUM"
163 kwds.append(ENUM)
164 EXTERN = "EXTERN"
165 kwds.append(EXTERN)
166 FLOAT = "FLOAT"
167 kwds.append(FLOAT)
168 FOR = "FOR"
169 kwds.append(FOR)
170 GOTO = "GOTO"
171 kwds.append(GOTO)
172 IF = "IF"
173 kwds.append(IF)
174 INLINE = "INLINE"
175 kwds.append(INLINE)
176 INT = "INT"
177 kwds.append(INT)
178 LONG = "LONG"
179 kwds.append(LONG)
180 OFFSETOF = "OFFSETOF"
181 kwds.append(OFFSETOF)
182 RESTRICT = "RESTRICT"
183 kwds.append(RESTRICT)
184 RETURN = "RETURN"
185 kwds.append(RETURN)
186 SHORT = "SHORT"
187 kwds.append(SHORT)
188 SIGNED = "SIGNED"
189 kwds.append(SIGNED)
190 SIZEOF = "SIZEOF"
191 kwds.append(SIZEOF)
192 STATIC = "STATIC"
193 kwds.append(STATIC)
194 STRUCT = "STRUCT"
195 kwds.append(STRUCT)
196 SWITCH = "SWITCH"
197 kwds.append(SWITCH)
198 TYPEDEF = "TYPEDEF"
199 kwds.append(TYPEDEF)
200 UNION = "UNION"
201 kwds.append(UNION)
202 UNSIGNED = "UNSIGNED"
203 kwds.append(UNSIGNED)
204 VOID = "VOID"
205 kwds.append(VOID)
206 VOLATILE = "VOLATILE"
207 kwds.append(VOLATILE)
208 WHILE = "WHILE"
209 kwds.append(WHILE)
210 # An instruction in the DSL
211 INST = "INST"
212 kwds.append(INST)
213 # A micro-op in the DSL
214 OP = "OP"
215 kwds.append(OP)
216 # A macro in the DSL
217 MACRO = "MACRO"
218 kwds.append(MACRO)
219 # A label in the DSL
220 LABEL = "LABEL"
221 kwds.append(LABEL)
222 SPILLED = "SPILLED"
223 kwds.append(SPILLED)
224 keywords = {name.lower(): name for name in kwds}
225
226 ANNOTATION = "ANNOTATION"
227 annotations = {
228 "specializing",
229 "override",
230 "register",
231 "replaced",
232 "pure",
233 "replicate",
234 "tier1",
235 "tier2",
236 "no_save_ip",
237 }
238
239 __all__ = []
240 __all__.extend(kwds)
241
242
243 def make_syntax_error(
244 message: str,
245 filename: str | None,
246 line: int,
247 column: int,
248 line_text: str,
249 ) -> SyntaxError:
250 return SyntaxError(message, (filename, line, column, line_text))
251
252
253 @dataclass(slots=True, frozen=True)
254 class Token:
255 filename: str
256 kind: str
257 text: str
258 begin: tuple[int, int]
259 end: tuple[int, int]
260
261 @property
262 def line(self) -> int:
263 return self.begin[0]
264
265 @property
266 def column(self) -> int:
267 return self.begin[1]
268
269 @property
270 def end_line(self) -> int:
271 return self.end[0]
272
273 @property
274 def end_column(self) -> int:
275 return self.end[1]
276
277 @property
278 def width(self) -> int:
279 return self.end[1] - self.begin[1]
280
281 def replaceText(self, txt: str) -> "Token":
282 assert isinstance(txt, str)
283 return Token(self.filename, self.kind, txt, self.begin, self.end)
284
285 def __repr__(self) -> str:
286 b0, b1 = self.begin
287 e0, e1 = self.end
288 if b0 == e0:
289 return f"{self.kind}({self.text!r}, {b0}:{b1}:{e1})"
290 else:
291 return f"{self.kind}({self.text!r}, {b0}:{b1}, {e0}:{e1})"
292
293
294 def tokenize(src: str, line: int = 1, filename: str = "") -> Iterator[Token]:
295 linestart = -1
296 for m in matcher.finditer(src):
297 start, end = m.span()
298 macro_body = ""
299 text = m.group(0)
300 if text in keywords:
301 kind = keywords[text]
302 elif text in annotations:
303 kind = ANNOTATION
304 elif letter.match(text):
305 kind = IDENTIFIER
306 elif text == "...":
307 kind = ELLIPSIS
308 elif text == ".":
309 kind = PERIOD
310 elif text[0] in "0123456789.":
311 kind = NUMBER
312 elif text[0] == '"':
313 kind = STRING
314 elif text in opmap:
315 kind = opmap[text]
316 elif text == "\n":
317 linestart = start
318 line += 1
319 kind = "\n"
320 elif text[0] == "'":
321 kind = CHARACTER
322 elif text[0] == "#":
323 macro_body = text[1:].strip()
324 if macro_body.startswith("if"):
325 kind = CMACRO_IF
326 elif macro_body.startswith("else"):
327 kind = CMACRO_ELSE
328 elif macro_body.startswith("endif"):
329 kind = CMACRO_ENDIF
330 else:
331 kind = CMACRO_OTHER
332 elif text[0] == "/" and text[1] in "/*":
333 kind = COMMENT
334 else:
335 lineend = src.find("\n", start)
336 if lineend == -1:
337 lineend = len(src)
338 raise make_syntax_error(
339 f"Bad token: {text}",
340 filename,
341 line,
342 start - linestart + 1,
343 src[linestart:lineend],
344 )
345 if kind == COMMENT:
346 begin = line, start - linestart
347 newlines = text.count("\n")
348 if newlines:
349 linestart = start + text.rfind("\n")
350 line += newlines
351 else:
352 begin = line, start - linestart
353 if macro_body:
354 linestart = end
355 line += 1
356 if kind != "\n":
357 yield Token(
358 filename, kind, text, begin, (line, start - linestart + len(text))
359 )
360
361
362 def to_text(tkns: list[Token], dedent: int = 0) -> str:
363 res: list[str] = []
364 line, col = -1, 1 + dedent
365 for tkn in tkns:
366 if line == -1:
367 line, _ = tkn.begin
368 l, c = tkn.begin
369 # assert(l >= line), (line, txt, start, end)
370 while l > line:
371 line += 1
372 res.append("\n")
373 col = 1 + dedent
374 res.append(" " * (c - col))
375 text = tkn.text
376 if dedent != 0 and tkn.kind == "COMMENT" and "\n" in text:
377 if dedent < 0:
378 text = text.replace("\n", "\n" + " " * -dedent)
379 # TODO: dedent > 0
380 res.append(text)
381 line, col = tkn.end
382 return "".join(res)
383
384
385 if __name__ == "__main__":
386 import sys
387
388 filename = sys.argv[1]
389 if filename == "-c":
390 src = sys.argv[2]
391 else:
392 src = open(filename).read()
393 # print(to_text(tokenize(src)))
394 for tkn in tokenize(src, filename=filename):
395 print(tkn)