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
);
121 return token
->number
;
124 return show_special(token
->special
);
128 int c
= token
->character
;
130 ptr
= charstr(ptr
, c
, '\'', 0);
136 case TOKEN_STREAMBEGIN
:
137 sprintf(buffer
, "<beginning of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
140 case TOKEN_STREAMEND
:
141 sprintf(buffer
, "<end of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
149 int init_stream(const char *name
, int fd
)
151 int stream
= input_stream_nr
;
152 struct stream
*current
;
154 if (stream
>= input_streams_allocated
) {
155 int newalloc
= stream
* 4 / 3 + 10;
156 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
158 die("Unable to allocate more streams space");
159 input_streams_allocated
= newalloc
;
161 current
= input_streams
+ stream
;
162 memset(current
, 0, sizeof(*current
));
163 current
->name
= name
;
165 current
->constant
= -1; // "unknown"
171 current
->dev
= st
.st_dev
;
172 current
->ino
= st
.st_ino
;
173 for (i
= 0; i
< stream
; i
++) {
174 struct stream
*s
= input_streams
+ i
;
175 if (s
->dev
== st
.st_dev
&& s
->ino
== st
.st_ino
) {
176 if (s
->constant
> 0 && lookup_symbol(s
->protect
, NS_PREPROCESSOR
))
181 input_stream_nr
= stream
+1;
185 static struct token
* alloc_token(stream_t
*stream
)
187 struct token
*token
= __alloc_token(0);
188 token
->pos
= stream
->pos
;
192 static int nextchar(stream_t
*stream
)
194 int offset
= stream
->offset
;
195 int size
= stream
->size
;
201 if (offset
>= size
) {
202 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
209 c
= stream
->buffer
[offset
];
210 stream
->offset
= ++offset
;
214 /* Ignore DOS-stype '\r' characters */
220 stream
->pos
.newline
= 1;
226 warn(stream
->pos
, "non-ASCII data stream");
231 struct token eof_token_entry
;
233 static void mark_eof(stream_t
*stream
, struct token
*end_token
)
237 end
= alloc_token(stream
);
238 token_type(end
) = TOKEN_STREAMEND
;
239 end
->pos
.newline
= 1;
241 eof_token_entry
.next
= &eof_token_entry
;
242 eof_token_entry
.pos
.newline
= 1;
245 end_token
= &eof_token_entry
;
246 end
->next
= end_token
;
247 *stream
->tokenlist
= end
;
248 stream
->tokenlist
= NULL
;
251 static void add_token(stream_t
*stream
)
253 struct token
*token
= stream
->token
;
255 stream
->token
= NULL
;
257 *stream
->tokenlist
= token
;
258 stream
->tokenlist
= &token
->next
;
261 static void drop_token(stream_t
*stream
)
263 stream
->pos
.newline
|= stream
->token
->pos
.newline
;
264 stream
->pos
.whitespace
|= stream
->token
->pos
.whitespace
;
265 stream
->token
= NULL
;
274 * pp-number identifier-nodigit
281 static int get_one_number(int c
, int next
, stream_t
*stream
)
284 static char buffer
[256];
285 char *p
= buffer
, *buf
;
294 next
= nextchar(stream
);
295 if (next
!= '-' && next
!= '+')
297 /* Fallthrough for sign of 'e'/'p' */
300 case 'a'...'d': case 'A'...'D':
301 case 'f'...'o': case 'F'...'O':
302 case 'q'...'z': case 'Q'...'Z':
304 next
= nextchar(stream
);
311 buf
= __alloc_bytes(len
);
312 memcpy(buf
, buffer
, len
);
314 token
= stream
->token
;
315 token_type(token
) = TOKEN_NUMBER
;
322 static int escapechar(int first
, int type
, stream_t
*stream
, int *valp
)
326 next
= nextchar(stream
);
330 warn(stream
->pos
, "Newline in string or character constant");
332 if (first
== '\\' && next
!= EOF
) {
334 next
= nextchar(stream
);
368 next
= escapechar(next
, type
, stream
, &value
);
373 while (next
>= '0' && next
<= '9') {
374 value
= (value
<< 3) + (next
-'0');
375 next
= nextchar(stream
);
383 int hex
= hexval(next
);
386 next
= nextchar(stream
);
387 while ((hex
= hexval(next
)) < 16) {
388 value
= (value
<< 4) + hex
;
389 next
= nextchar(stream
);
397 warn(stream
->pos
, "Unknown escape '%c'", value
);
400 /* Mark it as escaped */
407 static int get_char_token(int next
, stream_t
*stream
)
412 next
= escapechar(next
, '\'', stream
, &value
);
413 if (value
== '\'' || next
!= '\'') {
414 warn(stream
->pos
, "Bad character constant");
419 token
= stream
->token
;
420 token_type(token
) = TOKEN_CHAR
;
421 token
->character
= value
& 0xff;
424 return nextchar(stream
);
427 static int get_string_token(int next
, stream_t
*stream
)
429 static char buffer
[512];
430 struct string
*string
;
436 next
= escapechar(next
, '"', stream
, &val
);
440 warn(stream
->pos
, "Enf of file in middle of string");
443 if (len
< sizeof(buffer
)) {
451 warn(stream
->pos
, "String too long");
453 string
= __alloc_string(len
+1);
454 memcpy(string
->data
, buffer
, len
);
455 string
->data
[len
] = '\0';
456 string
->length
= len
+1;
459 token
= stream
->token
;
460 token_type(token
) = TOKEN_STRING
;
461 token
->string
= string
;
467 static int drop_stream_eoln(stream_t
*stream
)
469 int next
= nextchar(stream
);
475 next
= nextchar(stream
);
481 static int drop_stream_comment(stream_t
*stream
)
486 newline
= stream
->pos
.newline
;
488 next
= nextchar(stream
);
492 warn(stream
->pos
, "End of file in the middle of a comment");
495 next
= nextchar(stream
);
496 if (curr
== '*' && next
== '/')
499 stream
->pos
.newline
= newline
;
500 return nextchar(stream
);
503 unsigned char combinations
[][3] = COMBINATION_STRINGS
;
505 #define NR_COMBINATIONS (sizeof(combinations)/3)
507 static int get_one_special(int c
, stream_t
*stream
)
510 unsigned char c1
, c2
, c3
;
514 next
= nextchar(stream
);
517 * Check for numbers, strings, character constants, and comments
521 if (next
>= '0' && next
<= '9')
522 return get_one_number(c
, next
, stream
);
525 return get_string_token(next
, stream
);
527 return get_char_token(next
, stream
);
530 return drop_stream_eoln(stream
);
532 return drop_stream_comment(stream
);
536 * Check for combinations
539 comb
= combinations
[0];
540 c1
= c
; c2
= next
; c3
= 0;
541 for (i
= 0; i
< NR_COMBINATIONS
; i
++) {
542 if (comb
[0] == c1
&& comb
[1] == c2
&& comb
[2] == c3
) {
543 value
= i
+ SPECIAL_BASE
;
544 next
= nextchar(stream
);
553 token
= stream
->token
;
554 token_type(token
) = TOKEN_SPECIAL
;
555 token
->special
= value
;
560 #define IDENT_HASH_BITS (10)
561 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
562 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
564 #define ident_hash_init(c) (c)
565 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c))
566 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
568 static struct ident
*hash_table
[IDENT_HASH_SIZE
];
569 int ident_hit
, ident_miss
;
571 void show_identifier_stats(void)
574 int distribution
[100];
576 fprintf(stderr
, "identifiers: %d hits, %d misses\n",
577 ident_hit
, ident_miss
);
579 for (i
= 0; i
< 100; i
++)
582 for (i
= 0; i
< IDENT_HASH_SIZE
; i
++) {
583 struct ident
* ident
= hash_table
[i
];
592 distribution
[count
]++;
595 for (i
= 0; i
< 100; i
++) {
597 fprintf(stderr
, "%2d: %d buckets\n", i
, distribution
[i
]);
601 static struct ident
*alloc_ident(const char *name
, int len
)
603 struct ident
*ident
= __alloc_ident(len
);
604 ident
->symbols
= NULL
;
607 memcpy(ident
->name
, name
, len
);
611 static struct ident
* insert_hash(struct ident
*ident
, unsigned long hash
)
613 ident
->next
= hash_table
[hash
];
614 hash_table
[hash
] = ident
;
619 static struct ident
*create_hashed_ident(const char *name
, int len
, unsigned long hash
)
623 ident
= hash_table
[hash
];
625 if (ident
->len
== len
&& !memcmp(ident
->name
, name
, len
)) {
632 return insert_hash(alloc_ident(name
, len
), hash
);
635 static unsigned long hash_name(const char *name
, int len
)
638 const unsigned char *p
= (const unsigned char *)name
;
640 hash
= ident_hash_init(*p
++);
642 unsigned int i
= *p
++;
643 hash
= ident_hash_add(hash
, i
);
645 return ident_hash_end(hash
);
648 struct ident
*hash_ident(struct ident
*ident
)
650 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
653 struct ident
*built_in_ident(const char *name
)
655 int len
= strlen(name
);
656 return create_hashed_ident(name
, len
, hash_name(name
, len
));
659 struct token
*built_in_token(int stream
, const char *name
)
663 token
= __alloc_token(0);
664 token
->pos
.stream
= stream
;
665 token_type(token
) = TOKEN_IDENT
;
666 token
->ident
= built_in_ident(name
);
670 static int get_one_identifier(int c
, stream_t
*stream
)
679 hash
= ident_hash_init(c
);
682 next
= nextchar(stream
);
688 if (len
< sizeof(buf
)) {
689 hash
= ident_hash_add(hash
, next
);
697 hash
= ident_hash_end(hash
);
699 ident
= create_hashed_ident(buf
, len
, hash
);
702 token
= stream
->token
;
703 token_type(token
) = TOKEN_IDENT
;
704 token
->ident
= ident
;
709 static int get_one_token(int c
, stream_t
*stream
)
713 return get_one_number(c
, nextchar(stream
), stream
);
717 return get_one_identifier(c
, stream
);
719 return get_one_special(c
, stream
);
723 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
724 unsigned char *buf
, unsigned int buf_size
)
728 stream
->pos
.stream
= idx
;
729 stream
->pos
.line
= 1;
730 stream
->pos
.newline
= 1;
731 stream
->pos
.whitespace
= 0;
733 stream
->pos
.noexpand
= 0;
735 stream
->token
= NULL
;
738 stream
->size
= buf_size
;
739 stream
->buffer
= buf
;
741 begin
= alloc_token(stream
);
742 token_type(begin
) = TOKEN_STREAMBEGIN
;
743 stream
->tokenlist
= &begin
->next
;
747 static void tokenize_stream(stream_t
*stream
, struct token
*endtoken
)
749 int c
= nextchar(stream
);
752 c
= nextchar(stream
);
753 stream
->pos
.newline
= 0;
754 stream
->pos
.whitespace
= 1;
758 struct token
*token
= alloc_token(stream
);
759 stream
->token
= token
;
760 stream
->pos
.newline
= 0;
761 stream
->pos
.whitespace
= 0;
762 c
= get_one_token(c
, stream
);
765 stream
->pos
.whitespace
= 1;
766 c
= nextchar(stream
);
768 mark_eof(stream
, endtoken
);
771 struct token
* tokenize_buffer(unsigned char *buffer
, unsigned long size
, struct token
*endtoken
)
776 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
777 tokenize_stream(&stream
, endtoken
);
781 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
)
785 unsigned char buffer
[BUFSIZE
];
788 idx
= init_stream(name
, fd
);
792 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
793 tokenize_stream(&stream
, endtoken
);