2 * This is a really stupid C tokenizer. It doesn't do any include
3 * files or anything complex at all. That's the pre-processor.
5 * Copyright (C) 2003 Transmeta Corp.
8 * Licensed under the Open Software License version 1.1
25 int input_stream_nr
= 0;
26 struct stream
*input_streams
;
27 static int input_streams_allocated
;
29 #define BUFSIZE (8192)
34 struct token
**tokenlist
;
36 unsigned char *buffer
;
40 const char *show_special(int val
)
42 static const char *combinations
[] = COMBINATION_STRINGS
;
43 static char buffer
[4];
47 if (val
>= SPECIAL_BASE
)
48 strcpy(buffer
, combinations
[val
- SPECIAL_BASE
]);
52 const char *show_ident(const struct ident
*ident
)
54 static char buffer
[256];
57 sprintf(buffer
, "%.*s", ident
->len
, ident
->name
);
61 char *charstr(char *ptr
, unsigned char c
, unsigned char escape
, unsigned char next
)
64 if (c
== escape
|| c
== '\\')
79 return ptr
+ sprintf(ptr
, "%o", c
);
81 return ptr
+ sprintf(ptr
, "%03o", c
);
84 const char *show_string(const struct string
*string
)
86 static char buffer
[256];
92 for (i
= 0; i
< string
->length
-1; i
++) {
93 const unsigned char *p
= string
->data
+ i
;
94 ptr
= charstr(ptr
, p
[0], '"', p
[1]);
101 const char *show_token(const struct token
*token
)
103 static char buffer
[256];
107 switch (token_type(token
)) {
109 return "syntax error";
112 return "end-of-input";
115 return show_ident(token
->ident
);
118 return show_string(token
->string
);
120 case TOKEN_INTEGER
: {
121 const char *p
= token
->integer
;
126 strcpy(buffer
+1, p
+1);
137 return show_special(token
->special
);
141 int c
= token
->character
;
143 ptr
= charstr(ptr
, c
, '\'', 0);
149 case TOKEN_STREAMBEGIN
:
150 sprintf(buffer
, "<beginning of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
153 case TOKEN_STREAMEND
:
154 sprintf(buffer
, "<end of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
162 int init_stream(const char *name
, int fd
)
164 int stream
= input_stream_nr
;
165 struct stream
*current
;
167 if (stream
>= input_streams_allocated
) {
168 int newalloc
= stream
* 4 / 3 + 10;
169 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
171 die("Unable to allocate more streams space");
172 input_streams_allocated
= newalloc
;
174 current
= input_streams
+ stream
;
175 memset(current
, 0, sizeof(*current
));
176 current
->name
= name
;
178 current
->constant
= -1; // "unknown"
184 current
->dev
= st
.st_dev
;
185 current
->ino
= st
.st_ino
;
186 for (i
= 0; i
< stream
; i
++) {
187 struct stream
*s
= input_streams
+ i
;
188 if (s
->dev
== st
.st_dev
&& s
->ino
== st
.st_ino
) {
189 if (s
->constant
> 0 && lookup_symbol(s
->protect
, NS_PREPROCESSOR
))
194 input_stream_nr
= stream
+1;
198 static struct token
* alloc_token(stream_t
*stream
)
200 struct token
*token
= __alloc_token(0);
201 token
->pos
= stream
->pos
;
205 static int nextchar(stream_t
*stream
)
207 int offset
= stream
->offset
;
208 int size
= stream
->size
;
214 if (offset
>= size
) {
215 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
222 c
= stream
->buffer
[offset
];
223 stream
->offset
= ++offset
;
227 /* Ignore DOS-stype '\r' characters */
233 stream
->pos
.newline
= 1;
239 warn(stream
->pos
, "non-ASCII data stream");
244 struct token eof_token_entry
;
246 static void mark_eof(stream_t
*stream
, struct token
*end_token
)
250 end
= alloc_token(stream
);
251 token_type(end
) = TOKEN_STREAMEND
;
252 end
->pos
.newline
= 1;
254 eof_token_entry
.next
= &eof_token_entry
;
255 eof_token_entry
.pos
.newline
= 1;
258 end_token
= &eof_token_entry
;
259 end
->next
= end_token
;
260 *stream
->tokenlist
= end
;
261 stream
->tokenlist
= NULL
;
264 static void add_token(stream_t
*stream
)
266 struct token
*token
= stream
->token
;
268 stream
->token
= NULL
;
270 *stream
->tokenlist
= token
;
271 stream
->tokenlist
= &token
->next
;
274 static void drop_token(stream_t
*stream
)
276 stream
->pos
.newline
|= stream
->token
->pos
.newline
;
277 stream
->pos
.whitespace
|= stream
->token
->pos
.whitespace
;
278 stream
->token
= NULL
;
281 static int get_base_number(unsigned int base
, char **p
, int next
, stream_t
*stream
)
288 next
= nextchar(stream
);
298 static int do_fp(char *buffer
, int len
, int next
, stream_t
*stream
)
300 struct token
*token
= stream
->token
;
303 /* Get the decimal part */
305 buffer
[len
++] = next
;
306 next
= nextchar(stream
);
307 while (next
>= '0' && next
<= '9') {
308 buffer
[len
++] = next
;
309 next
= nextchar(stream
);
313 /* Get the exponential part */
314 if (next
== 'e' || next
== 'E') {
315 buffer
[len
++] = next
;
316 next
= nextchar(stream
);
317 while (next
>= '0' && next
<= '9') {
318 buffer
[len
++] = next
;
319 next
= nextchar(stream
);
323 /* Get the 'lf' type specifiers */
324 while (next
== 'f' || next
== 'F' || next
== 'l' || next
== 'L') {
325 buffer
[len
++] = next
;
326 next
= nextchar(stream
);
329 buffer
[len
++] = '\0';
330 buf
= __alloc_bytes(len
);
331 memcpy(buf
, buffer
, len
);
332 token_type(token
) = TOKEN_FP
;
338 static int do_integer(char *buffer
, int len
, int next
, stream_t
*stream
)
340 struct token
*token
= stream
->token
;
343 if (next
== '.' || next
== 'e' || next
== 'E')
344 return do_fp(buffer
, len
, next
, stream
);
346 while (next
== 'u' || next
== 'U' || next
== 'l' || next
== 'L') {
347 buffer
[len
++] = next
;
348 next
= nextchar(stream
);
350 buffer
[len
++] = '\0';
351 buf
= __alloc_bytes(len
);
352 memcpy(buf
, buffer
, len
);
353 token_type(token
) = TOKEN_INTEGER
;
354 token
->integer
= buf
;
359 static int get_one_number(int c
, stream_t
*stream
)
361 static char buffer
[256];
362 int next
= nextchar(stream
);
370 next
= get_base_number(8, &p
, next
, stream
);
375 next
= get_base_number(10, &p
, next
, stream
);
380 next
= get_base_number(16, &p
, next
, stream
);
383 return do_integer(buffer
, p
- buffer
, next
, stream
);
386 static int escapechar(int first
, int type
, stream_t
*stream
, int *valp
)
390 next
= nextchar(stream
);
394 warn(stream
->pos
, "Newline in string or character constant");
396 if (first
== '\\' && next
!= EOF
) {
398 next
= nextchar(stream
);
432 next
= escapechar(next
, type
, stream
, &value
);
437 while (next
>= '0' && next
<= '9') {
438 value
= (value
<< 3) + (next
-'0');
439 next
= nextchar(stream
);
447 int hex
= hexval(next
);
450 next
= nextchar(stream
);
451 while ((hex
= hexval(next
)) < 16) {
452 value
= (value
<< 4) + hex
;
453 next
= nextchar(stream
);
461 warn(stream
->pos
, "Unknown escape '%c'", value
);
464 /* Mark it as escaped */
471 static int get_char_token(int next
, stream_t
*stream
)
476 next
= escapechar(next
, '\'', stream
, &value
);
477 if (value
== '\'' || next
!= '\'') {
478 warn(stream
->pos
, "Bad character constant");
483 token
= stream
->token
;
484 token_type(token
) = TOKEN_CHAR
;
485 token
->character
= value
& 0xff;
488 return nextchar(stream
);
491 static int get_string_token(int next
, stream_t
*stream
)
493 static char buffer
[512];
494 struct string
*string
;
500 next
= escapechar(next
, '"', stream
, &val
);
504 warn(stream
->pos
, "Enf of file in middle of string");
507 if (len
< sizeof(buffer
)) {
515 warn(stream
->pos
, "String too long");
517 string
= __alloc_string(len
+1);
518 memcpy(string
->data
, buffer
, len
);
519 string
->data
[len
] = '\0';
520 string
->length
= len
+1;
523 token
= stream
->token
;
524 token_type(token
) = TOKEN_STRING
;
525 token
->string
= string
;
531 static int drop_stream_eoln(stream_t
*stream
)
533 int next
= nextchar(stream
);
539 next
= nextchar(stream
);
545 static int drop_stream_comment(stream_t
*stream
)
547 int next
= nextchar(stream
);
552 warn(stream
->pos
, "End of file in the middle of a comment");
555 next
= nextchar(stream
);
556 if (curr
== '*' && next
== '/')
559 return nextchar(stream
);
562 unsigned char combinations
[][3] = COMBINATION_STRINGS
;
564 #define NR_COMBINATIONS (sizeof(combinations)/3)
566 static int get_one_special(int c
, stream_t
*stream
)
569 unsigned char c1
, c2
, c3
;
573 next
= nextchar(stream
);
576 * Check for strings, character constants, and comments
580 return get_string_token(next
, stream
);
582 return get_char_token(next
, stream
);
585 return drop_stream_eoln(stream
);
587 return drop_stream_comment(stream
);
591 * Check for combinations
594 comb
= combinations
[0];
595 c1
= c
; c2
= next
; c3
= 0;
596 for (i
= 0; i
< NR_COMBINATIONS
; i
++) {
597 if (comb
[0] == c1
&& comb
[1] == c2
&& comb
[2] == c3
) {
598 value
= i
+ SPECIAL_BASE
;
599 next
= nextchar(stream
);
608 token
= stream
->token
;
609 token_type(token
) = TOKEN_SPECIAL
;
610 token
->special
= value
;
615 #define IDENT_HASH_BITS (10)
616 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
617 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
619 #define ident_hash_init(c) (c)
620 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c))
621 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
623 static struct ident
*hash_table
[IDENT_HASH_SIZE
];
624 int ident_hit
, ident_miss
;
626 void show_identifier_stats(void)
629 int distribution
[100];
631 fprintf(stderr
, "identifiers: %d hits, %d misses\n",
632 ident_hit
, ident_miss
);
634 for (i
= 0; i
< 100; i
++)
637 for (i
= 0; i
< IDENT_HASH_SIZE
; i
++) {
638 struct ident
* ident
= hash_table
[i
];
647 distribution
[count
]++;
650 for (i
= 0; i
< 100; i
++) {
652 fprintf(stderr
, "%2d: %d buckets\n", i
, distribution
[i
]);
656 static struct ident
*alloc_ident(const char *name
, int len
)
658 struct ident
*ident
= __alloc_ident(len
);
659 ident
->symbols
= NULL
;
661 memcpy(ident
->name
, name
, len
);
665 static struct ident
* insert_hash(struct ident
*ident
, unsigned long hash
)
667 ident
->next
= hash_table
[hash
];
668 hash_table
[hash
] = ident
;
673 static struct ident
*create_hashed_ident(const char *name
, int len
, unsigned long hash
)
677 ident
= hash_table
[hash
];
679 if (ident
->len
== len
&& !memcmp(ident
->name
, name
, len
)) {
686 return insert_hash(alloc_ident(name
, len
), hash
);
689 static unsigned long hash_name(const char *name
, int len
)
692 const unsigned char *p
= (const unsigned char *)name
;
694 hash
= ident_hash_init(*p
++);
696 unsigned int i
= *p
++;
697 hash
= ident_hash_add(hash
, i
);
699 return ident_hash_end(hash
);
702 struct ident
*hash_ident(struct ident
*ident
)
704 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
707 struct ident
*built_in_ident(const char *name
)
709 int len
= strlen(name
);
710 return create_hashed_ident(name
, len
, hash_name(name
, len
));
713 struct token
*built_in_token(int stream
, const char *name
)
717 token
= __alloc_token(0);
718 token
->pos
.stream
= stream
;
719 token_type(token
) = TOKEN_IDENT
;
720 token
->ident
= built_in_ident(name
);
724 static int get_one_identifier(int c
, stream_t
*stream
)
733 hash
= ident_hash_init(c
);
736 next
= nextchar(stream
);
742 if (len
< sizeof(buf
)) {
743 hash
= ident_hash_add(hash
, next
);
751 hash
= ident_hash_end(hash
);
753 ident
= create_hashed_ident(buf
, len
, hash
);
756 token
= stream
->token
;
757 token_type(token
) = TOKEN_IDENT
;
758 token
->ident
= ident
;
763 static int get_one_token(int c
, stream_t
*stream
)
767 return get_one_number(c
, stream
);
771 return get_one_identifier(c
, stream
);
773 return get_one_special(c
, stream
);
777 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
778 unsigned char *buf
, unsigned int buf_size
)
782 stream
->pos
.stream
= idx
;
783 stream
->pos
.line
= 1;
784 stream
->pos
.newline
= 1;
785 stream
->pos
.whitespace
= 0;
788 stream
->token
= NULL
;
791 stream
->size
= buf_size
;
792 stream
->buffer
= buf
;
794 begin
= alloc_token(stream
);
795 token_type(begin
) = TOKEN_STREAMBEGIN
;
796 stream
->tokenlist
= &begin
->next
;
800 static void tokenize_stream(stream_t
*stream
, struct token
*endtoken
)
802 int c
= nextchar(stream
);
805 c
= nextchar(stream
);
806 stream
->pos
.newline
= 0;
807 stream
->pos
.whitespace
= 1;
811 struct token
*token
= alloc_token(stream
);
812 stream
->token
= token
;
813 stream
->pos
.newline
= 0;
814 stream
->pos
.whitespace
= 0;
815 c
= get_one_token(c
, stream
);
818 stream
->pos
.whitespace
= 1;
819 c
= nextchar(stream
);
821 mark_eof(stream
, endtoken
);
824 struct token
* tokenize_buffer(unsigned char *buffer
, unsigned long size
, struct token
*endtoken
)
829 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
830 tokenize_stream(&stream
, endtoken
);
834 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
)
838 unsigned char buffer
[BUFSIZE
];
841 idx
= init_stream(name
, fd
);
845 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
846 tokenize_stream(&stream
, endtoken
);