C++ scanner (string-fu!)

Question

I'm writing a scanner as part of a compiler.

I'm having a major headache trying to write this one portion:

I need to be able to parse a stream of tokens and push them one by one into a vector, ignoring whitespace and tokenizing special symbols (simple case, lets just consider parentheses and braces)

Example: int main(){ }

should parse into 6 different tokens:

1. int
2. main
3. (
4. )
5. {
6. }

How would you go about solving this? I'm writing this in C++, but a java/C# solution would be appreciated as well.

Some points:

1. and no, I can't use Boost, I can't guarantee that the libraries will be available to me. (don't ask...)

2. I don't want to use lex, or any other special tools. I've never done this before and just want to try this once to say I've done it.

Answer 1

Buy a copy of Compilers: Principles, Techniques, and Tools (the Dragon Book). What you're attempting to write is a lexer, not a "scanner".

Answer 2

Stroustrup's book, The C++ Programming Language, has a great example in it about building a lexer/parser for a simple calculator program. It should serve as a good starting point to learn how to do what you want.

Answer 3

Why write your own - look at Lex.

If youmust have your own, you just read the input character by character and maintain some minimum state to accumulate identifiers.

The problem itself is not hard. If you can't solve it, you must be burned out, you just need a rest. Look at it again in the morning.

Answer 4

Is strtok a valid answer?

Answer 5

umm.. I'd just do a while loop with iterators testing each character for type, and only an alpha to non alpha change, dump the string if it's non empty. if it's a non alpha non white space character, I'd just push it onto the token stack, this is really a trivial parsing task. Shoot, I've been meaning to learn lexx/yacc, but the level of parsing you want is really easy. I wrote a html tokenizer once which is more complicated that this.. I mean you are just looking for names, white space and single non alphanumeric characters.. just do it.

Answer 6

If you really want to learn something from this exercise, just start coding. It doesn't demand a lot of code, so you can fail repeatedly without blowing more than an afternoon.

At this point you'll have a good feel for the problem.

Then look in any random compilers book to see what the "usual" methods are, and you'll grok then immediately.

Answer 7

If you want to write this from scratch, you could look into writing a finite state machine (states in an enum, a big switch/case block for state switching). You'd have to push the state to a stack since everything can be nested.

I know that this is not the ideal method; I'm just trying to directly address the question.