The role of the lexical analyzer in the compiler

Upon receiving a get-next-tohen command from the parser, the lexical analyzer reads input characters until it can identify the next token.

Figure 19: Interaction of Lexical analyzer with parser.

The lexical analyzer collects also information about tokens into their associated attributes:

• the tokens influence parsing decisions,
• the attributes influence the translation of tokens.

INTERFACING LEX WITH YACC. One of the main uses of LEX is as a companion to the YACC parser-generator.

• YACC expects to call a routine named yylex() to find the next input token.
• This routine is supposed to return the type of the next token, as well as putting any associated value in the global variable yylval.
• To use LEX with YACC, one specifies the -d option to YACC to instruct it to generate the file y.tab.h containing definitions of all the tokens appearing in the YACC input. This file is then included in the LEX scanner.

Example 5   The file calculator.y below specifies the GRAMMAR of the expressions of a desk calculator. This file can be processed by the YACC program.

%{
#include <ctype.h>
#include <stdio.h>

void yyerror(const char *str)
{
  fprintf(stderr,"error: %s\n",str);
}

int yywrap()
{
  return 1;
}

main()
{
  yyparse();
}


%}

%token TOK_NUMBER TOK_PLUS TOK_TIMES TOK_MINUS TOK_DIVIDE TOK_LP TOK_RP

%%
line        : line expr '\n' {printf("%d\n", $2); }
            | /* empty word */
            ;

expr        : expr TOK_PLUS term          {$$ = $1 + $3; }
            | term                  {$$ = $1; }


term        : factor TOK_TIMES term        {$$ = $1 * $3; }
            | factor               {$$ = $1; }


factor      : TOK_LP expr TOK_RP        {$$ = $2; }
            | TOK_NUMBER           {$$ = $1; }
             ;
%%

The file calculator.l specifies how the above tokens are detected

%{
#include "y.tab.h"
extern int yylval;
#include <stdlib.h>
%}

PLUS            [\+]
MINUS           [\-]
TIMES           [\*]
DIVIDE          [/]
DIGIT           [0-9]
NUMBER          [0-9]+
WS              [ \t]*
LP              "("
RP              ")"
RET             [\n]

%%

{WS}            {
                /* eat up white space */
                }
{NUMBER}        {
                yylval = atoi( yytext ); 
                return TOK_NUMBER;
                }
{PLUS}          {
                return TOK_PLUS;
                }
{TIMES}         {
                return TOK_TIMES;
                }
{MINUS}         {
                return TOK_MINUS;
                }
{DIVIDE}        {
                return TOK_DIVIDE;
                }
{LP}            {
                return TOK_LP;
                }
{RP}            {
                return TOK_RP;
                }
.               {
                }
{RET}           {
                return yytext[0];
                }

The corresponding calculator is built and run as follows:

[moreno@iguanodon yacc]$ yacc -d src/calculator.y
yacc: 16 shift/reduce conflicts
[moreno@iguanodon yacc]$ flex src/calculator.l 
[moreno@iguanodon yacc]$ gcc lex.yy.c y.tab.c -ll -o calculator
[moreno@iguanodon yacc]$ ./calculator 
1 + 3
4
2 * 4
8
(2 + 3) * 6
30
(2 + 3) * (4 + 5)
45

ABOUT THE SEPARATION OF THE LEXER FROM THE PARSER.

• SIMPLIFICATION OF DESIGN. If the lexical analyzer has removed comments and white space, then the parser's computations will be simpler.
• EFFICIENCY. It is easier to optimize and maintain simple little components than a large sophisticated one.
• PORTABILITY. If the lexical analyzer is the only part of the compiler which has to worry about the input file (alphabetic peculiarities) and its support then the compiler portability will be enhanced.

Other possible tasks of the lexical analyzer:

• Correlating error messages from the compiler to the source pogram Indeed, the lexical analyzer may be the only component of the compiler aware of line numbers in the source pogram.
• Macro expansion. Indeed, the tokens associated with a macro can be precomputed.