Debian Codegraph @

lib/lang/c/lexer.scm

raw
1 ;;;
2 ;;; C lexical analyzer
3 ;;;
4 ;;; Copyright (c) 2021-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; This is a submodule of lang.c.parser. Not for general public use.
35 (define-module lang.c.lexer
36 (use util.match)
37 (use parser.peg)
38 (use lang.c.type)
39 (export c-tokenize)
40 )
41 (select-module lang.c.lexer)
42
43 ;;;
44 ;;; Lexical elements (6.4)
45 ;;;
46
47 ;; Tokenizer output: sequence of <token>s.
48 ;;
49 ;; <token> := <punctuator>
50 ;; | <keyword>
51 ;; | <identifier>
52 ;; | <constant>
53 ;; | <string-literal>
54 ;;
55 ;; <punctuator> : <symbol> such as '|(| etc.
56 ;; <keyword> : <symbol>
57 ;; <identifier> : (ident <symbol>)
58 ;; <constant> : (const <const-type> <value>)
59 ;; <string-literal> : (string <value>) | (wstring <value>)
60 ;;
61 ;; <const-type> is either one of the basic type symbols defined in
62 ;; lang.c.type, or wchar_t.
63 ;;
64 ;; <value> is a Scheme string as it appears in the source, except unicode
65 ;; character sequences and excape sequences are converted to corresponding
66 ;; characters.
67
68 ;; Intertoken stuff
69
70 (define %whitespace ($one-of #[ \n\r\t]))
71 (define %long-comment ($seq ($. "/*")
72 ($many_ ($seq ($not ($. "*/"))
73 ($any)))
74 ($. "*/")))
75 (define %line-comment ($seq ($. "//")($many-till_ ($any) ($. "\n"))))
76 (define %pragma ($seq ($. #\#) ($many_ ($none-of #[\n]))))
77
78 (define %spacing
79 ($many_ ($or %whitespace %long-comment %line-comment %pragma
80 ($lazy %ignorable-keyword))))
81
82 ;; Punctuators (6.4.6)
83 ;; We return a char for paren-like stuff, and
84 ;; symbols for other punctuators.
85
86 (define ($->sym x) ($lift string->symbol ($. x)))
87
88 (define %punctuator
89 ($or ($->sym"...") ($->sym"<<=") ($->sym">>=")
90 ($->sym"->")
91 ($->sym"++") ($->sym"--")
92 ($->sym"&&") ($->sym"||")
93 ($->sym"<<") ($->sym">>")
94 ($->sym"<=") ($->sym">=") ($->sym"==") ($->sym"!=")
95 ($->sym"*=") ($->sym"/=") ($->sym"%=") ($->sym"+=")
96 ($->sym"-=") ($->sym"&=") ($->sym"^=") ($->sym"|=")
97 ($seq ($."<:") ($return #\[))
98 ($seq ($.":>") ($return #\]))
99 ($seq ($."<%") ($return #\{))
100 ($seq ($."%>") ($return #\}))
101 ($seq ($."%:%:") ($return '|##|))
102 ($seq ($."%:") ($return '|#|))
103 ($->sym"*") ($->sym"+") ($->sym"-") ($->sym "/") ($->sym "%")
104 ($->sym"&") ($->sym"|") ($->sym"^") ($->sym"~") ($->sym "!")
105 ($->sym"<") ($->sym">")
106 ($->sym"?") ($->sym":") ($->sym";") ($->sym"=")
107 ($->sym",") ($->sym"##") ($->sym"#") ($->sym".")
108 ($. #[\[\]\(\)\{\}])))
109
110 ;; Keywords (6.4.1)
111 ;; We return a symbol.
112
113 (define %hexquad ($lift (^[xs] (string->number (list->string xs) 16))
114 ($repeat ($. #[[:xdigit:]]) 4)))
115
116 (define %unichar-escaped
117 ($or ($lift (^[_ n] (integer->char n))
118 ($. #\u) %hexquad)
119 ($lift (^[_ n0 n1] (integer->char (+ (* n0 #x10000) n1)))
120 ($. #\U) %hexquad %hexquad)))
121
122 (define %unichar-name ($seq ($. #\\) %unichar-escaped))
123
124 (define %idnondigit ($or ($. #[a-zA-Z_]) %unichar-name))
125
126 (define %idchar ($or ($. #[a-zA-Z0-9_]) %unichar-name))
127
128 ;; <symbol> - standard
129 ;; (<symbol> <alt-symbol>) - match <symbol>, return <alt-symbol>
130 (define *keywords*
131 '(auto break case char const continue default double do else enum
132 extern float for goto if int inline long register restrict
133 return short signed sizeof static struct switch typedef
134 union unsigned void volatile while
135 _Bool _Complex _Imaginary
136 ;; nonstandard keywords
137 _stdcall __declspec __builtin_va_list
138 ;; gcc additional floating types
139 _Float128 (__float128 _Float128)
140 _Float64x (__float80 _Float64x)
141 __ibm128
142 ;; gcc additional keywords
143 __attribute__
144 (__restrict restrict)
145 (__restrict__ restrict)
146 (__inline inline)
147 (__inline__ inline)
148 (__volatile volatile)
149 (__volatile__ volatile)
150 (asm asm)
151 (__asm asm)
152 (__asm__ asm)
153 (__alignof__ __alignof__)
154 ;; clang additional keywords
155 _Nullable _Nonnull _Null_unspecified _Nullable_result
156 ))
157
158 (define %keyword
159 (apply $or (map (^e (if (pair? e)
160 ($try ($seq ($. (symbol->string (car e)))
161 ($not %idchar)
162 ($return (cadr e))))
163 ($try ($seq ($. (symbol->string e))
164 ($not %idchar)
165 ($return e)))))
166 *keywords*)))
167
168 ;; gcc specific
169 (define %ignorable-keyword
170 ($try ($seq ($. "__extension__") ($not %idchar))))
171
172 ;; Identifiers (6.4.2)
173 ;; (ident <symbol>)
174
175 (define %identifier
176 ($seq ($not %keyword)
177 ($lift (^[c cs]
178 `(ident ,(string->symbol (list->string (cons c cs)))))
179 %idnondigit ($many %idchar))))
180
181 ;; Constants (6.4.4)
182
183 ;; We handle integers and floating point numbers at once.
184 ;; The initial assert is to rule out suffix-only match without consuming
185 ;; input.
186 (define %dec-oct-numeric-constant
187 ($let ([ ($assert ($. #[0-9.])) ]
188 [integral ($many ($. #[0-9]))]
189 [point ($optional ($. "."))]
190 [fractional ($many ($. #[0-9]))]
191 [exponent ($optional ($lift list
192 ($. #[eE])
193 ($optional ($. #[+-]))
194 ($many1 ($. #[0-9]))))]
195 [suffix ($many %idchar)])
196 (cond
197 [(or point exponent) ;; must be flonum
198 (if (or (and (pair? integral) point)
199 (and point (pair? fractional))
200 (and (pair? integral) exponent))
201 (if-let1 suf (check-float-suffix suffix)
202 ($return `(const ,suf
203 ,(rope->string (list integral
204 point
205 fractional
206 exponent
207 suffix))))
208 ($fail (format "invalid floating point number constant suffix: ~a"
209 (list->string suffix))))
210 ($fail "malformed floating point number constant"))]
211 [(and (pair? integral) (not point) (null? fractional) (not exponent))
212 ;; TODO: check octal constant vailidity
213 (if-let1 suf (check-int-suffix suffix)
214 ($return `(const ,suf ,(rope->string (list integral suffix))))
215 ($fail (format "malformed integer constant suffix: ~a"
216 (list->string suffix))))]
217 [else ($fail "malformed numeric constant")])))
218
219 (define %hex-numeric-constant
220 ($let ([ ($. "0x") ]
221 [integral ($many ($. #[[:xdigit:]]))]
222 [point ($optional ($. "."))]
223 [fractional ($many ($. #[[:xdigit:]]))]
224 [bin-exp ($optional ($lift list
225 ($. #[pP])
226 ($optional ($. #[+-]))
227 ($many1 ($. #[[:xdigit:]]))))]
228 [suffix ($many %idchar)])
229 (cond
230 [(or point bin-exp) ;; must be flonum
231 (if (or (and (pair? integral) point)
232 (and point (pair? fractional))
233 (and (pair? integral) bin-exp))
234 (if-let1 suf (check-float-suffix suffix)
235 ($return `(const ,suf
236 ,(rope->string (list "0x"
237 integral
238 point
239 fractional
240 bin-exp
241 suffix))))
242 ($fail (format "invalid floating point number constant suffix: ~a"
243 (list->string suffix))))
244 ($fail "malformed hex floating point number constant"))]
245 [(and (pair? integral) (not point) (null? fractional) (not bin-exp))
246 (if-let1 suf (check-int-suffix suffix)
247 ($return `(const ,suf ,(rope->string (list "0x" integral suffix))))
248 ($fail (format "malformed integer constant suffix: ~a"
249 (list->string suffix))))]
250 [else ($fail "malformed numeric constant")])))
251
252 ;; we need to reject invalid suffix, so we first gather suffix characters
253 ;; then look at them, instead of using BNF rules.
254 (define (check-float-suffix chars)
255 (match chars
256 [() 'double]
257 [((or #\f #\F)) 'float]
258 [((or #\l #\L)) 'long-double]
259 [_ #f]))
260
261 (define (check-int-suffix chars)
262 (match chars
263 [() 'int]
264 [((or #\u #\U)) 'u-int]
265 [((or #\l #\L)) 'long]
266 [((or #\u #\U) (or #\l #\L)) 'u-long]
267 [((or #\l #\L) (or #\u #\U)) 'u-long]
268 [(or (#\l #\l) (#\L #\L)) 'long-long]
269 [(or ((or #\u #\U) #\l #\l) ((or #\u #\U) #\L #\L)) 'u-long-long]
270 [(or (#\l #\l (or #\u #\U)) (#\L #\L (or #\u #\U))) 'u-long-long]
271 [_ #f]))
272
273 (define %escaped-sequence
274 ($seq ($. #\\)
275 ($or ($. #[\'\"\\\?])
276 ($seq ($. #\a) ($return #\alarm))
277 ($seq ($. #\b) ($return #\backspace))
278 ($seq ($. #\f) ($return #\x0c))
279 ($seq ($. #\n) ($return #\newline))
280 ($seq ($. #\r) ($return #\return))
281 ($seq ($. #\t) ($return #\tab))
282 ($seq ($. #\v) ($return #\x0b))
283 ($lift (^s (integer->char
284 (string->number (list->string s) 8)))
285 ($many ($. #[0-7]) 1 3))
286 ($lift (^[_ s] (integer->char
287 (string->number (list->string s) 16)))
288 ($. #\x) ($many ($. #[[:xdigit:]])))
289 %unichar-escaped)))
290
291
292 (define %c-char-sequence ($many ($or ($. #[^'\\\n]) %escaped-sequence)))
293
294 (define %character-constant
295 ($or ($lift (^c `(const char ,(list->string c)))
296 ($between ($. #\') %c-char-sequence ($. #\')))
297 ($lift (^c `(const wchar ,(list->string c)))
298 ($between ($. "L'") %c-char-sequence ($. #\')))))
299
300 ;; enum-constant is syntactically identical to %identifier
301 (define %constant
302 ($or %hex-numeric-constant
303 %dec-oct-numeric-constant
304 %character-constant))
305
306 (define %s-char-sequence ($many ($or ($. #[^\"\\\n]) %escaped-sequence)))
307
308 (define %string-literal
309 ($or ($lift (^s `(string ,(list->string s)))
310 ($between ($. #\") %s-char-sequence ($. #\")))
311 ($lift (^s `(wstring ,(list->string s)))
312 ($between ($. "L\"") %s-char-sequence ($. #\")))))
313
314 ;; NB: need to match %constant first, to recognize .0 as a number instead
315 ;; of '.' followed by '0'. Also need to match %string-literal before
316 ;; %identifier, for L"..." should be a wstring instead of an identifier 'L'
317 ;; followed by a string.
318 (define %token
319 ($seq0 ($or ($try %constant)
320 %string-literal
321 %punctuator
322 %keyword
323 %identifier)
324 %spacing))
325
326 (define (make-c-tokenize-generator char-seq)
327 (receive (_ char-seq)
328 (peg-run-parser %spacing char-seq) ;skip leading whitespaces
329 (rec (gen)
330 (if (null? char-seq)
331 (eof-object)
332 (receive (tok next) (peg-run-parser %token char-seq)
333 (let1 attrs (pair-attributes char-seq)
334 (set! char-seq next)
335 (values tok attrs)))))))
336
337 ;; API - Lexer entry
338 (define (c-tokenize char-seq)
339 (generator->lseq (make-c-tokenize-generator char-seq)))