I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, but I read this online notes and here is the statement

The lexical analyzer produces a single tokens each time it is called by the parser.

I can't understand this statement. How does all this stuff happens? For a program with thousands line of code there may be thousands of tokens and for every token if the parser calls the lexical analyzer this may be very much time consuming? How does parser decide that all tokens are produced and it don't need to call lexical analyzer now?

I am asking this for general compiler not a language specific.


1 Answer 1


Yes, normally a parser calls the lexical analyser every time it needs a token, and this results in many, many, many calls to the lexical analyser. It is well known by compiler writers that the lexical analysis can consume the larger proportion of the compilers execution time.

However, the lexical analysis process would normally use a Chomsky type 3 grammar, or a regular language, and thus can be implemented by a finite state automaton, which can be coded quite efficiently. The parser, by contrast, will normally be based on some form of Chomsky type 2 (context free) grammar and the algorithm would be less efficient as it may involve back-tracking or rule matching. Thus devolving some work from the less efficient parser to the more efficient lexical analyser makes the whole compiler more efficient.

It is possible also to implement the relationship between the lexical analyser and the parser in a different way. The lexical analyser could process the whole input source program from a file (of text) into a complete set of tokens, which could themselves be stored in a file. Then the parser could input that file of tokens. This would be slower because it involves the writing and reading of a file. The list of tokens could alternately be stored in memory, but now the compiler has a larger memory requirement. Historically, in early computers, with smaller memories and slower processors it was done in a similar way and perhaps the input (tape) of the source program resulted in an output (tape) of token which becomes the input (tape) of the parser program!

On a modern system this could be implemented in a pipe, for example:

lexer sourcefile.lng | parser | optimiser | codegen > program.exe

Internally, some compilers could implement it this way, but normally a parser (function) within the compiler calls a lexer (function) as described.

  • $\begingroup$ (1) If you use bison/yacc with flex and then compile with whole-program optimisation, the compiler may well be able to inline the call to the lexer, since there is exactly one place in the bison-generated parser where yylex is called. I don't know that you'll find a noticeable speedup from this, though. I should do some experiments :-) (2) It's possible to invert control flow and have the lexer invoke the parser. This is how lemon-based projects work, for example, and bison provides it as an option. It's definitely a bit slower, but it's a lot more convenient in my experience. $\endgroup$
    – rici
    Jul 5, 2021 at 17:57
  • $\begingroup$ If we have used a token two different places , does in this case also the lexical analyzer will be called twice? Or if it is called first time for a token then the entry will be saved at symbol table and after this it will be accessed through it? So what happens. $\endgroup$ Jul 17, 2021 at 2:21
  • $\begingroup$ @Brijeshjoshi Yes, the parser does not know what the next token will be. It can the the same as last time or different. The parser calls the lexer every time it needs a token, irrespective of what that token maybe. It could be the same one hundreds of times! The lexer has to look it up in the symbol table each time, otherwise it doesn't know if it is there already! That is how it know the identifiers are the same. $\endgroup$ Jul 17, 2021 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.