LEX is a tool used to generate a lexical analyzer. Translates a set of regular express specifications into a c implementation

Pasted image 20250808133805.png

Feeds the ExpL source code and output of tokens.

"integer" {return ID_TYPE_INTEGER;}

DECLARATIONS
%%
RULES
%%
AUXILIARY FUNCTIONS

Declarations

Auxiliary declarations - header files, define global variables, constants
Regular definitions -

// Auxiliary declarations start here
%{
    #include <stdio.h>
    int global_variable
%}
// Auxiliary declarations end and regular definitions start here
    number [0-9]+
    op [-|+|*|/|^|=]
%%

// Rules 

%%

// Auxiliary Functions

Rules

Pattern to be matched
Corresponding action to be executed

%%
    {number} {printf(" number");}
    {op} {printf(" operator");}
%%

LEX obtains the regular expressions of the symbols from the declarations section and generates code into a function yylex() in the lex.yy.c

Auxiliary Functions

LEX generates C code for the rules specified in the Rules section and places this code int a single function called yylex().

%%
%%

int main() {
    yylex();
    return 1;
}

yyin

yyin is a variable of the type FILE* and points to the input file. yyin is defined by LEX automatically.

%%

%%

int main(int argc, char* argv[]) {
    if(argc > 1) {
        FILE *f = fopen(argv[1], "r");
        if(f) {
            yyin = f;
        }
    }
    yylex();
    return 1;
}

if(!yyin) 
    yyin = stdin;

yytext

yytext is a char* and it contains the lexeme currently found. A lexeme is a sequence of characters in the input stream that matches some pattern in the Rules Section. (In fact, it is the first matching sequence in the input from the position pointed to by yyin).

%option noyywrap
% {
    #include <stdlib.h>
    #include <stdio.h>
}

number [0-9]+

%%
{number} {printf("Found: %d\n", atoi(yytext))}

%%

int main() {
    yylex();
    return 1;
}

yyleng

yyleng is a variable of the type int and it stores the length of the lexeme pointed to by yytext

/* Declarations */
%%
// Rules
%%
{number} printf("Number of digits = %d", yyleng);

yylex()

Function of return type int. LEX automatically definesyylex() but does not call it. LEX generates code for the definition of yylex() according to the rules specified in the Rules section.

%%
{number} {return atoi(yytext);}

%%

int main() {
    int num = yylex();
    printf("Found %d", num);
    return 1;
}

When yylex() is invoked, it reads the input as pointed to by yyin and scans through the input looking for the pattern. When matches, yylex() executes the corresponding action.

yywarp()

return type int

yylex communicates with yywrap, if return zero, continues scanning else terminates. It is mandatory to either define yywrap() or indicate the absense using %option feature, if not LEX will flag the error.

%{
    #include<stdio.h>
    char *file1
%}

[0-9]+ printf("number")

int yywrap() {
    FILE *newfile_pointer;
    char *file2 = "input_file_2.l";
    newfile_pointer = fopen("input_file_2.1", "r");
    if(strcmp(file1,file2) != 0) {
        file1 = file2;
        yyin = newfile_pointer;
        return 0;
    } else return 1;
}

int main() {
    file1 = "input_file.1";
    yyin = fopen("input_file.l", "r");
    yylex();
    return 1;
}

Modifications

%{
    #include<stdio.h>
    FILE *fp;
%}

%
[0-9]+ {printf("NUMBER", yytext);}
[a-zA-Z]+ {printf("WORD", yytext);}
. {/* IGNORE */}
%

int yywrap() {
    static int stage = 0;
    if(stage == 0) {
        fp = fopen("input_file.l", "r");
        if(!fp) {
            perror("Cannot open the file");
            return 1;
        }
        yyin = fp;
        stage++;
        return 0;
    } else return 1;
}

Even-Odd.l

%{
    #include <stdlib.h>
    #include <stdio.h>
    int number_1;
    int number_2;
%}

number_sequence [0-9]*

%%
{number_sequence}[0|2|4|6|8] {
    printf("Even number");
    return atoi(yytext);
}
{number_sequence}[1|3|5|7|9] {
    printf("Odd Number");
    return atoi(yytext);
}
%%

int yywrap() {
    return 1;
}

int main() {
    number_1 = yylex();
    number_2 = yylex();
}

Disambiguation Rules

LEX uses two important disambiguation rules in selecting the right action for matching pattern

Choose the first match
Longest match is preferred

"break" {return BREAK;}
[a-zA-Z][a-zA-Z0-9]* {return IDENTIFIER; }

Pattern Matching using LEX

Conceptually, LEX constructs a finite state machine to recognize all the regular expression patterns specified in the LEX program file. A transition table is stoed in lex.yy.c (current_state, input_char). To make it visible use -T flag.

%{
    #include <stdio.h>
    #define ID 1
    #define ER 2
%}

low [a-z]
upper [A-Z]
number [0-9]

%option noyywrap // important

%%
({low}|{upp})({low}|{upp})*{number} return ID;
(.)* return ER;
%%

int main() {
    int token == yylex();
    if(token == ID) {
        printf("Acceptable");
    } else printf("Unacceptable\n");
    return 1;
}

Construction of a DFA from a regular expression

Pasted image 20250809151038.png

Leaves -> operands Intermediate -> operators

Intermediate Syntax Tree

Just a meaningful tree

Pasted image 20250809153243.png

YACC

YACC translates CFG specifications into a C implementation of a corresponding push down automata.

Parser - checks whether its input meet a given grammar specification. Syntax of SIL can be specified using a Context Free Grammer.

CFG

(NTPS) - Each production consists of a non terminal on the left and a sequence of tokens and non terminals on the right side.

// infix to postfix converter

start: expr '\n'  {exit(1);}
    ;
expr: expr '+' expr {printf("+ );}
    | expr '*' expr {printf("* );}
    | '(' expr ')'
    | DIGIT {printf("NUM%d ", pos);}
    ;

Each rule has a production part and an action part. The action part consists of C statements. Each production has a head and body separated by a ':'

yyparse()

===y.tab.c ===contains yyparse() - implementation of a push down automata yyparse() invokes to read the tokens.

DECLARATIONS

%%

RULES 

%% 

AUXILIARY FUNCTIONS

Declarations

Declarations section consists of two parts (i) C declarations and (ii) YACC declarations. YACC declarations part comprises of declarations of tokens. The parser reads the tokens by invoking yylex()

Rules

(i) Production Part (ii) Action part

production_head : production_body {action in C};

Productions

Each production consists of a production head and a production body.

expr : expr '+' expr

Auxiliary Functions

Auxiliary functions section contains the definitions of three mandatory function in main(), yylex() and yyerror().

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

    void print_operator(char op);
    int pos = 0;
%} 

// y.tab.c 

%token DIGIT
%left '+'
%left '*'

%%
start: expr '\n' {exit(1);}
    ;
expr: expr '+' expr {print_operator('+')}
    | expr '*' expr {print_operator('*');}
    | '(' expr ')' 
    | DIGIT {printf("NUM%d ", pos);}
    ;
%%

void print_operator(char op) {
    switch(c) {
        case '+' : {
            printf("PLUS ");
            break;
        }
        case '*': {
            printf("MUL ");
            break;
        }
        return;
    }
}

yyerror(const char* s) {
    printf("yyerror %s", s);
}

Shift-Reduce parsing

Shift reduce parsing is a push down automata.

STACK: $       I/P BUFFER:  <Input to be parsed> $

Shift-reduce parser can take four possible parser-actions

Shift - removing the next unread terminal from the input buffer and push to stack
Reduce - replacing one or more grammar symbols from the top of stack that matches a body of a production with production head.
Accept - indicating that the entire input has been parsed successfully.
Error YACC uses LALR(1)parsing method (Look ahead + left-right)

Initialize the stack with the end-marker $
new_token = yylex() /* read the first token from the input */
while (true)
    switch(parser_action(stack, new_token))
        case 'reduce':
                  pop the handle from stack, replace it with the
                  head of the handle's production.Execute action
                  part in the yacc file corresponding to the handle's production
        case 'shift':
                  push new_token into the stack.
                  new_token = yylex()  /* read the next token from the input */
        case 'accept':
            return 0
        case 'error':
            return 1

Shift/Reduce Conflicts

Ambiguity in choosing shifting/reducing

%left - decides reduction %right - decides shift %nonassoc - makes the parser return an error on inputs like (a<b<c)

%left '+' => + is left associative %left '*' => * is left associative and higher

Reduce/Reduce Conflicts

Happens where there are two same production bodies with different production heads.

program     :  statement
            |   conditional
statement   :  if boolean then stmt else stmt
            |  stmt
conditional :  if boolean then stmt else stmt

Passing values from yylex() to yyparse()

yylex() only returns token type, not the actual value

We need to pass extra data with each token - attribute value

yyval

%%
[0-9] {yylval = atoi(yytext), return DIGIT;}
%%

%token DIGIT
%%
expr:
      expr '+' expr { printf("+ "); }
    | expr '*' expr { printf("* "); }
    | '(' expr ')'
    | DIGIT         { printf("%d ", yylval); }
;
%%

Using Lex With Yacc

start: expr NEWLINE {
    printf("\nComplete\n");
    exit(1);
}

expr: expr '+' expr {printf("+ ");}
    | expr '-' expr {printf("- ")}

integrate y.parse.h with lexer

Introduction Attributes

{number} {
    yylval = atoi(yytext);
    return DIGIT;
}

expr: expr '+' expr {printf("+ ");}
    | DIGIT {printf("%d ",$1);}

%{
  #include <stdio.h>
  int yyerror();
%}

%token DIGIT

%%

start : pair '\n'       {printf("\nComplete"); }
    ;

pair: num ',' num   { printf("pair(%d,%d)",$1,$3); }
  ;
num: DIGIT          { $$=$1; }
  ;

%%

int yyerror()
{
    printf("Error");
}

int main()
{
    yyparse();
    return 1;
}

Customising Attribute Types

YYSTYPE - int

#define YYSTYPE char
expr: expr OP expr {printf("%c %c %c", $1,$2,$3);}

Multiple custom attribute values %union

%union {
    char character; 
    int integer;
}

%token OP
%token NUMBER

%type <character> OP
%type <integer> NUMBER

%%
expr: expr OP expr {printf("%c %d %d), $<character>2, %<integer>1, %<integer>3}
    | DIGIT {$<integer>$=$<integer>1;}