Run LEX program on windows platform

This post is about to run the LEX program in Windows Platform instead of wasteing your time in installing LINUX into your machine..
First of all download a files named "flex.exe" and "Bison.exe" from the following sites..
http://www.monmouth.com/~wstreett/lex-yacc/flex.exe
http://www.monmouth.com/~wstreett/lex-yacc/bison.exe

Now you can start from here:
1. Create a folder and place the flex and bison files in them.

2. Create the lex program and save in the folder(like 'program.l' or 'program.txt')

3. Open the command prompt and reach the directory.

4. Call the flex by the command "flex <filename.extension>" (like 'flex program.l')

5. If the program contain any error it will showed to you, otherwise it will generate the file named "lex.yy.c".I suggest you rename “lex.yy.c” to some other more sensible name like “lex.c”, because double extensions is not a good idea in windows environment. Move the file to the folder of your compiler.

6. Call the compiler and input lex.c to it (eg: “tcc lex.c”, where tcc is the Turbo C compiler; use any C/C++ compiler you have). If what you have is a more sophisticated environment like visual studio, you have to do the normal procedure to get a program to compile. If you use Turbo C, an object file “lex.obj’ and the executable “lex.exe” will be generated if there are no compilation problems

7. Thats it. Now just run lex.exe. Its your lexical analyser.

It is very similar to the way you do it in linux.

All the seven steps look like a complicated procedure. I created a batch file(.bat files similar to shell scrpits in linux) , to do the whole job from calling flex to get the lex.exe up and running. My batch file(rflex.bat) looks like below.

flex program.txt
ren lex.yy.c lex.c
copy lex.c c:\tc\bin\
c:
cd tc
cd bin
tcc lex.c
lex
c:
cd “Compiler Design”

del lex.yy.c
del lex.c

All the program can be carried out likewise.

Implementation of LALR bottom up parser

#include <iostream>
#include <sstream>
#include <cctype>
#include <deque>
#include <stack>
#include <vector>

struct Token{
    enum TokenType{
        END,
        INTEGER,
        PLUS,
        MINUS,
    } type;
    long intValue;
    Token(TokenType type=END):type(type),intValue(0){}
    Token(long val):type(INTEGER),intValue(val){}
    Token(char character){
        //...
    }
};

class NonTerminal{
    enum NonTerminalType{
        terminal,
        expr,
    } type;
    NonTerminal *trunk;
    std::vector<NonTerminal> branches;
    bool reduced;
public:
    Token leaf;
private:
    void reduce_terminal(){
        this->reduced=1;
        switch (this->leaf.type){
            case Token::INTEGER:
                this->type=expr;
        }
    }
    void reduce_expr(){
        if (!this->branches.size())
            return;
        if (this->branches.size()<3)
            this->leaf=this->branches[0].leaf;
        else{
            this->leaf.type=Token::INTEGER;
            switch (this->branches[1].leaf.type){
                case Token::PLUS:
                    this->leaf.intValue=this->branches[0].leaf.intValue+this->branches[2].leaf.intValue;
                    break;
                case Token::MINUS:
                    this->leaf.intValue=this->branches[0].leaf.intValue-this->branches[2].leaf.intValue;
                    break;
                default:;
            }
        }
        this->reduced=1;
        this->branches.clear();
    }
public:
    NonTerminal(NonTerminal *trunk=0){
        this->type=expr;
        this->trunk=trunk;
        this->reduced=0;
    }
    NonTerminal(const Token &token,NonTerminal *trunk=0){
        this->leaf=token;
        this->type=terminal;
        this->trunk=trunk;
        this->reduced=0;
    }
    void set(const Token &token){
        this->leaf=token;
        this->type=terminal;
        this->trunk=trunk;
        this->reduced=0;
    }
    void push(const Token &token){
        if (this->type==terminal)
            return;
        this->branches.push_back(NonTerminal(token));
    }
    NonTerminal *newBranch(const Token &token){
        this->branches.push_back(NonTerminal(this));
        return &this->branches.back();
    }
    bool isComplete(){
        if (this->type==terminal)
            return 1;
        if (!this->branches.size())
            return 0;
        for (unsigned a=0;a<this->branches.size();a++)
            if (this->branches[a].type!=terminal && !this->branches[a].reduced)
                return 0;
        switch (this->branches.size()){
            case 1:
                return this->branches[0].leaf.type==Token::INTEGER;
            case 3:
                if (this->branches[0].leaf.type!=Token::INTEGER ||
                        this->branches[1].leaf.type!=Token::PLUS &&
                        this->branches[1].leaf.type!=Token::MINUS ||
                        this->branches[2].leaf.type!=Token::INTEGER)
                    return 0;
                return 1;
            default:
                return 0;
        }
    }
    NonTerminal *reduce(){
        if (!this->isComplete())
            return 0;
        switch (this->type){
            case terminal:
                this->reduce_terminal();
                break;
            case expr:
                this->reduce_expr();
                break;
        }
        return this->trunk?this->trunk:this;
    }
};

class Parser{
    std::deque<Token> expression;
    std::stack<Token> stack;
    long result;
    unsigned state;
    NonTerminal tree,
        *current_node;
    Token read(std::stringstream &stream){
        //(lexer)
    }
    unsigned run_state(){
        Token::TokenType front_token_type;
        switch (this->state){
            case 0:
                front_token_type=this->expression.front().type;
                if (front_token_type==Token::INTEGER)
                    return 3;
                if (front_token_type==Token::END)
                    return 1;
                return 2;
            case 3:
                this->current_node->push(this->expression.front());
                this->expression.pop_front();
                if (this->current_node->isComplete())
                    this->current_node=this->current_node->reduce();
                front_token_type=this->expression.front().type;
                if (front_token_type==Token::PLUS ||
                        front_token_type==Token::MINUS)
                    return 4;
                if (front_token_type==Token::END)
                    return 1;
                return 2;
            case 4:
                this->current_node->push(this->expression.front());
                this->expression.pop_front();
                front_token_type=this->expression.front().type;
                if (front_token_type==Token::INTEGER)
                    return 3;
                return 2;
            default:
                return this->state;
        }
    }
    //1: continue, 0: accept, -1: abort
    int to_state(unsigned n){
        this->state=n;
        switch (n){
            case 1:
                return 0;
            case 2:
                return -1;
            default:
                return 1;
        }
    }
public:
    Parser(const std::string &str){
        std::stringstream stream(str);
        do
            this->expression.push_back(this->read(stream));
        while (this->expression.back().type!=Token::END);
        this->result=0;
        this->state=0;
        this->current_node=&this->tree;
    }
    bool eval(long &res){
        int ret;
        while ((ret=this->to_state(this->run_state()))==1);
        if (!ret){
            this->tree.reduce();
            res=this->tree.leaf.intValue;
        }
        return !ret;
    }
};

int main(){
    Parser evaluator("12+3-2");
    long res;
    std::cout <<evaluator.eval(res)<<std::endl;
    std::cout <<res<<std::endl;
    return 0;
}

Implementation of predictive parser in LEX.

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define SIZE 128
#define NONE -1
#define EOS '\0'
#define NUM 257
#define KEYWORD 258
#define ID 259
#define DONE 260
#define MAX 999
char lexemes[MAX];
char buffer[SIZE];
int lastchar =  - 1;
int lastentry = 0;
int tokenval = DONE;
int lineno = 1;
int lookahead;
struct entry
{
  char *lexptr;
  int token;
} symtable[100];
struct entry keywords[] =
{
  "if", KEYWORD, "else", KEYWORD, "for", KEYWORD, "int", KEYWORD, "float",
    KEYWORD, "double", KEYWORD, "char", KEYWORD, "struct", KEYWORD,"return ",KEYWORD,0,0};

void Error_Message(char *m)
  {
    fprintf(stderr, "line %d, %s \n", lineno, m);
    exit(1);
  } int look_up(char s[])
  {
    int k;
    for (k = lastentry; k > 0; k--)
      if (strcmp(symtable[k].lexptr, s) == 0)
        return k;
    return 0;
  }
  int insert(char s[], int tok)
  {
    int len;
    len = strlen(s);
    if (lastentry + 1 >= MAX)
      Error_Message("Symbpl table is full");
    if (lastchar + len + 1 >= MAX)
      Error_Message("Lexemes array is full");
    lastentry = lastentry + 1;
    symtable[lastentry].token = tok;
    symtable[lastentry].lexptr = &lexemes[lastchar + 1];
    lastchar = lastchar + len + 1;
    strcpy(symtable[lastentry].lexptr, s);
    return lastentry;
  } /*void Initialize()
  {
  struct entry *ptr;
  for(ptr=keywords;ptr->token;ptr+1)
  insert(ptr->lexptr,ptr->token);
  }*/
  int lexer()
  {
    int t;
    int val, i = 0;
    while (1)
    {
      t = getchar();
      if (t == ' ' || t == '\t')
        ;
      else if (t == '\n')
        lineno = lineno + 1;
      else if (isdigit(t))
      {
        ungetc(t, stdin);
        scanf("%d", &tokenval);
        return NUM;
      }
      else if (isalpha(t))
      {
        while (isalnum(t))
        {
          buffer[i] = t;
          t = getchar();
          i = i + 1;
          if (i >= SIZE)
            Error_Message("Compiler error");
        }
        buffer[i] = EOS;
        if (t != EOF)
          ungetc(t, stdin);
        val = look_up(buffer);
        if (val == 0)
          val = insert(buffer, ID);
        tokenval = val;
        return symtable[val].token;
      }
      else if (t == EOF)
        return DONE;
      else
      {
        tokenval = NONE;
        return t;
      }
    }
  }
  void Match(int t)
  {
    if (lookahead == t)
      lookahead = lexer();
    else
      Error_Message("Syntax error");
  }
  void display(int t, int tval)
  {
    if (t == '+' || t == '-' || t == '*' || t == '/')
      printf("\nArithmetic Operator: %c", t);
    else if (t == NUM)
      printf("\n Number: %d", tval);
    else if (t == ID)
      printf("\n Identifier: %s", symtable[tval].lexptr);
    else
      printf("\n Token %d tokenval %d", t, tokenval);
  }
  void F()
  {
    //void E();
    switch (lookahead)
    {
      case '(':
        Match('(');
        E();
        Match(')');
        break;
      case NUM:
        display(NUM, tokenval);
        Match(NUM);
        break;
      case ID:
        display(ID, tokenval);
        Match(ID);
        break;
      default:
        Error_Message("Syntax error");
    }
  }
  void T()
  {
    int t;
    F();
    while (1)
    {
      switch (lookahead)
      {
        case '*':
          t = lookahead;
          Match(lookahead);
          F();
          display(t, NONE);
          continue;
        case '/':
          t = lookahead;
          Match(lookahead);
          display(t, NONE);
          continue;
        default:
          return ;
      }
    }
  }
  void E()
  {
    int t;
    T();
    while (1)
    {
      switch (lookahead)
      {
        case '+':
          t = lookahead;
          Match(lookahead);
          T();
          display(t, NONE);
          continue;
        case '-':
          t = lookahead;
          Match(lookahead);
          T();
          display(t, NONE);
          continue;
        default:
          return ;
      }
    }
  }
  void parser()
  {
    lookahead = lexer();
    while (lookahead != DONE)
    {
      E();
      Match(';');
    }
  }
  main()
  {
    char ans[10];
    printf("\n Program for recursive decent parsing ");
    printf("\n Enter the expression ");
    printf("And place ; at the end\n");
    printf("Press Ctrl-Z to terminate\n");
    parser();
  }

Program to generate follow of grammar.

#include<stdio.h>
#include<type.h>
int n,m=0,p,i=0,j=0;
char a[10][10],r[10];
void follow (char c);
void first(char c);
int main()
{
int  i,z;
char c,ch;
printf("Enter the number of production");
scanf("%d",&n);
printf("Enter the production )(epsilon =$):\n");
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
do
{
n=0;
printf("Enter the element whose FOLLOW is to be found");
scanf("%c",&c);
FOLLOW(c);
printf("FOLLOW (%c)"={",c);
for(i=0;i<m;i++)
printf("%c" &f[i]);
printf("\n");
printf("Do you want to cintinue (Y/N)?");
scanf("%d%c", &z, &ch);
}
void first(char c)
{
int k;
if(!super(c))
f[m++]=c;
for(k=0;k<n;k++)
{
if(a[k][0]==c)
{
if(a[k][z]=='$')
FOLLOW(a[i][o]);
elseif(islower (a[k][z]))
f[m++]=a[k][2];
else first(a[k][2]);
}
}
}

Program for generate the Grammar

#include<stdio.h>
#include<type.h>
void first(char);
int count,n=0;
char produn[10][10], FIRST[10];
main()
{
int i,choice;
char c,ch;
printf("How many productions??");
scanf("%d",&count);
printf("Enter %d production epsilon =$ "\n\n");
for(i=0;i<count;i++)
scanf("%s%c",prodn[i],&ch);
do
{
n=0;
printf("Elements:");
scanf("%c",&c);
FIRST(c);
printf("\n FIRST (%c) ={","c);
for(i=0;i<=n;i++)
printf("%c",FIRST(i));
printf("} \n");
printf("press 1 to continue:");
scanf("%d %c", &choice, &ch);
}
while(choice ==1);
}
void FIRST(char c)
{
int i;
if (!(isuper(c))first[n++]=c);
for(j=0;j<count;j++)
{
if(prodn[j][2]=="$")FIRST[n++]='$';
}
else
FIRST(prodn[j][2]);
}
}
}

Develop a lexical analyzer to recognize a pattern.

%{
#include<stdio.h>
#include<type.h>
#include<string.h>
int yy,invalid,flag,pp=-1;
char token[20],i;
struct symbol table
{
    char token[20];
    int ind;
}
s[20];
%}
digit[0-9]
letter[a-z A-Z]
id{letter}({letter}|{digit)*digit{digit}+num{digit}(%{digit})* relop "<" | ">" i "<=" | "i" ==" | "l=" relop "<" | ">" i "<=" | "l" == "|=" bop [-+*/%]
shift ">>" | "<<" nop "--" | "++" pun [, , \ {|}\] rey "if" | "else" | "while" delin [\t\n]
ws{delin} + com "/\*" (.) * " \* / assop "=" invalid {digit} * {letter} + ({letter}) | {digit}) * |[$] %%yytext);}
{{us}}
%%
int main()
{
yylex();
}
int install_id(char token[20])
{
int i,flag;
for(i=0;i<=fop;i++)
{
if(stramp(s[i].token,token)==0)
{
flag=1;
break;
}
else
flag=0;
}
if(flag==1)
{
printf("\n token is already present in symbol table");
}
else
{
strcopy(s[++top].token,token);
s[top].ind=top;
printf("\n token is installed in symbol table");
}
printf("\n \t\t symbol table \n");
for(i=0;i<=top;i++)
{
printf("\n %d \t\t %s \n"s[i].ind,s[i].token);
}
}
int yywrap()
{
return ();
}

A Program in C for counting lines, spaces, words, character and tab of a given text.

#include<stdio.h>
#define <max 1000>
void lines(char t)
void space_tab(char c[])
void characters(char g[])
void main()
{
    char s[max];
    int i,c;
    i=0;
    for(i=0;i<max-1&&c=getchar()1=EDE;i++)
    s[i]=c;
    lines(s);
    character(s);
    space_tab(s);
}
void lines(char s[])
{
    int i=0;
    while(s[i]!=10)
    {
        ++i;
    }
    if(s[i]=="\n")
    ++i;
    }
    printf("%d" \t,i);
    }
    void space_tab(char s[])
    {
        int i=0;t=0;
        while(s[i]='10')
        {
            ++i;
            if(s[i]=="||s[i]=='\t');
            ++t;
        }
        printf("%d"+/t"t);
    }
void characters(char g[])
{
    int i=0,c=0;
    while(g[i]!='10')
    {
        ++i;
        if(g[i]!="\n"&&g[i]!=='/t'&&g[i]!=" ")
        ++i;
    }
    printf("%d \t \t",());
    getch();
}