Storing tokens during lexing stage

Question

I am currently implementing a lexer that breaks XML files up into tokens, I'm considering ways of passing the tokens onto a parser to create a more useful data structure out of said tokens - my current plan is to store them in an arraylist and pass this to the parser , would a link list where each token points to the next be better suited? Or is being able to access tokens by index easier to make a parser for? Or is this all a terrible strategy?

Also if anyone has used antlr , I know it uses a token stream to pass tokenized input to the parser, how can the parser make decisions on if the input is valid / create a data structure if it does not have all the tokens from the input yet?

Answer 1

Common parsing techniques rely on inspecting a single 'current' token from a stream of such tokens. In some variations a certain amount of lookahead is required, but is usually provided from within the parser and not by indexing forwards and backwards across the lexer stream.

In other words the data structure you will most likely need is some kind of stream. The usual way of implementing this is with a function-based API, with functions like peek() and movenext().

Given a 'stream of token', the details of how you structure that internally are relatively unimportant. You might use an in-memory queue, a producer-consumer queue, a yield/generator or any of a multiplicity of other techniques.

My strong recommendation would be to do the 'simplest thing that could possibly work'. The interesting and challenging parts of your problem are yet to come.

Answer 2

If you can access tokens with an index, there's the temptation to jump ahead or behind, and you can do so, however you generally wind up with very hard code to understand. Good parsers have a grammar which determines what they should look for next based on where they are in the grammar, and if the grammar is done right, you should never be faced with ambiguity (not know what type of tokens to expect next).

Doing it this way is simpler to write and condenses the problem in creating a good grammar rather than writing a good parser. It does not really matter if you're using linked lists or an array (unless you're going to be parsing very large XML files, in which case maybe linked lists would be safer). However, the parser should generally treat this input as a Queue, even if it could jump ahead otherwise with an index. Lookaheads do exist, but you shouldn't require it for XML grammar.

Hope that helps.