How would one go about writing a lexical parser? I have several tools and containers that I've written at my disposal to contribute to the job. Ultimately, I'd like to use it in my compiler, and be able to read in a token at a time, and be able to tell its type and decide what to do based upon that, but I know it is never that simple. I plan to have it read in BNF files, and create a lexer state that processes input and returns tokens sequentially. One problem I foresee is knowing what many small tokens form when put together, and if the largest non-terminal type is returned, finding out the smaller components to operate on them, unless I return some sort of tree. I'm not sure how to go about this, and any advice would be helpful.

And please, no suggestions to abandon the project, or use one already written. Far too frequently, I receive only discouraging responses.

You seem to be trying to write a syntactic parser, not a lexical parser. A lexical parser eats characters and spits out tokens, while a syntactic parser eats tokens and spits out a parsing tree. People often refer to these as "lexer" and simply "parser", respectively.

If you want to take one token at a time and decide what to do based on that, you probably want to write an LL(1) parser. That Wikipedia page contains a section on how to build an LL(1) parsing table which I think answers your question.

I guess I could work from tokens. However, this would require me to write something like I already have for every type of input to create tokens from it. I'm also looking for re-usability. My preprocessor reads a stream and creates tokens from it, and I could use the tokens from that for something, however, I'd ideally like to have this create the tokens. However, it looks like I'll need both parsers at some point.

As for the suggestions to abandon writing this project and use an already written parser: no, thank you.

My preprocessor reads a stream and creates tokens from it...

So, it sounds like you have the tokenizer step done already. The only thing left during lexical analysis is to classify what kind of terminal each token is. For example, your terminal types might include: {identifier, keyword-void, keyword-for, keyword-if, operator-plus, operator-multiply, operator-not, ...}

After you've created terminals, you feed those to the parser (by parser, I mean the part that builds your abstract syntax tree).

I use table-based LR(0) parsing with a GLR-based state machine. This involves:

• Building the parse table from the grammar productions. This is probably the hardest to understand step. I do this at runtime, where most popular parser generators do this as a pre-compile step (generating source code for the parser). This is a reusable step you can perform on a wide variety of grammars.
  
• Create a state machine that can follow the transitions in your table. An LR state machine is easy to write, the GLR extensions are much more complicated. This is a generic algorithm which can be reused for multiple parse tables.
  
• Feed all of your tokenized terminals to the state machine, followed by a special 'end of input' terminal.
  

http://en.wikipedia...._parsing_tables

[quote name='Ectara' timestamp='1333309300' post='4927252']
My preprocessor reads a stream and creates tokens from it...

So, it sounds like you have the tokenizer step done already. The only thing left during lexical analysis is to classify what kind of terminal each token is. For example, your terminal types might include: {identifier, keyword-void, keyword-for, keyword-if, operator-plus, operator-multiply, operator-not, ...}

After you've created terminals, you feed those to the parser (by parser, I mean the part that builds your abstract syntax tree).

I use table-based LR(0) parsing with a GLR-based state machine. This involves:

• Building the parse table from the grammar productions. This is probably the hardest to understand step. I do this at runtime, where most popular parser generators do this as a pre-compile step (generating source code for the parser). This is a reusable step you can perform on a wide variety of grammars.
  
• Create a state machine that can follow the transitions in your table. An LR state machine is easy to write, the GLR extensions are much more complicated. This is a generic algorithm which can be reused for multiple parse tables.
  
• Feed all of your tokenized terminals to the state machine, followed by a special 'end of input' terminal.
  

http://en.wikipedia...._parsing_tables
[/quote]

I would like to have it tokenize, as I would think that trying to attach the type of token after it has been processed is not an easy task. Not to mention, the preprocessor does quick and imperfect tokenization, as it ensures that tokens are whole, well-formed, and are in such a state that they can be operated upon.

I would like to have it tokenize, as I would think that trying to attach the type of token after it has been processed is not an easy task. Not to mention, the preprocessor does quick and imperfect tokenization, as it ensures that tokens are whole, well-formed, and are in such a state that they can be operated upon.

It depends on the language. Some languages are designed so that the lexical stage is very easy. Natural languages like English are the exact opposite. GLR parsers are specifically designed to handle ambiguous situations like this. For example, if you see the word "run" in English, it can be a noun, intransitive verb, transitive verb. To handle this, you can pass a GLR parser multiple options per token, and it'll analyze each possibility in parallel. Most programming languages specifically avoid this ambiguity, which makes things much easier.

Your thread has the "C Language" tag on it. Does that mean you want to parse C, or are implementing it in C?

Your thread has the "C Language" tag on it. Does that mean you want to parse C, or are implementing it in C?

Both. I have a couple specialized virtual processors already implemented, and I wrote a poor compiler for it before. I have a C preprocessor already written that can either give a container of tokens and line numbers, or write the processed output to a stream.

Past that, I have nothing. Ideally, it'd be neat to use this lexer for something other than the compiler, or another compiler. I don't want to hard-code C syntax into it, and I don't want to embed it in to the compiler; I planned it out to be a separate module that the compiler makes calls to in order to process its data.

I guess, I'll first ask questions to see if I understand. First, does BNF describe a syntax for a lexical parser, or syntax parser? If BNF is not used for a lexical parser, which type of input should I use?

Second, would I simply be returning tokens, without any type information or how they might relate to each other? If so, would the next parser then take those and interpret syntactic meaning? Also, how would I determine which non-terminal is of the highest order, without scanning all of the tokens, if one terminal could be part of a non-terminal, and that non-terminal could belong to another, how would I best ascertain the highest non-terminal?