Converting BNF rules for arithmetic expression into yacc form and generating trees

-

 st.lex

******************

%{

        #include <bits/stdc++.h>

        #include "st.tab.h"

%}

%option noyywrap

%%

[a-zA-Z_][a-zA-Z_0-9]*  yylval.str=strdup(yytext);return ID ;

([0-9]*\.?[0-9]*)|(\".*?\")|(\'.\')     yylval.str=strdup(yytext);return VAL ;

";"             yylval.str=strdup(yytext);return SC ;

"+"             yylval.str=strdup(yytext);return PL ;

"-"             yylval.str=strdup(yytext);return MI ;

"*"             yylval.str=strdup(yytext);return MUL ;

"/"             yylval.str=strdup(yytext);return DIV ;

"="             yylval.str=strdup(yytext);return EQ ;

"("             yylval.str=strdup(yytext);return OP ;

")"             yylval.str=strdup(yytext);return CL ;

"^"             yylval.str=strdup(yytext);return POW ;

[\n \t]+        ;

.               yylval.str=strdup(yytext);return UNR;

%%

st.y
******************

%{

        #include<bits/stdc++.h>

        using namespace std;

        void yyerror(char *s);

        int yylex();

        typedef struct node

        {

                struct node *left,*right;

                string val;

                int label;

        }NODE;

        NODE* makeNode(string val, NODE* left , NODE* right)

        {

                NODE *temp=new NODE();

                temp->val=val;

                temp->left=left;

                temp->right=right;

                temp->label=0;

                return temp;

        }

        NODE* synTree;

%}

%token PL MI MUL DIV OP CL EQ ID VAL SC UNR POW

%union{

        typedef struct node NODE;

        char *str;

        NODE *node;

}

%type <node> s e t f g

%type <str> PL MI MUL DIV OP CL EQ ID VAL SC UNR POW

%%

s : e {$$=$1;synTree=$$;}

e : e PL t {$$=makeNode($2,$1,$3);} |

         e MI t {$$=makeNode($2,$1,$3);} |

          t {$$=$1;};

t : t MUL f {$$=makeNode($2,$1,$3);}|

         t DIV f {$$=makeNode($2,$1,$3);}|

          f {$$=$1;};

f : g POW f {$$=makeNode($2,$1,$3);} |

         g {$$=$1;};

g : OP e CL {$$=$2;} |

         ID{$$=makeNode($1,NULL,NULL);} |

          VAL{$$=makeNode($1,NULL,NULL);} /*|

           MI g{$$=makeNode($1,NULL,$2);} */;

%%

void inOrder(NODE* root)

{

        if(root)

        {

                inOrder(root->left);

                cout<<root->val<<" ";

                inOrder(root->right);

        }

}

void postOrder(NODE* root)

{

        if(root)

        {

                postOrder(root->left);

                postOrder(root->right);

                cout<<root->val<<" ";

        }

}


void preOrder(NODE* root)

{

        if(root)

        {

                cout<<root->val<<" ";

                preOrder(root->left);

                preOrder(root->right);

        }

}

void yyerror(char *s)

{

printf("%s\n",s);

}

int main(void)

{

        yyparse();

        cout<<"In Order:"<<endl;

        inOrder(synTree);

        cout<<endl<<"Pre Order:"<<endl;

        preOrder(synTree);

        cout<<endl<<"Post Order:"<<endl;

        postOrder(synTree);

        cout<<endl;

}

Execution
**************************
$ bison -d st.y
$ lex st.lex
$ g++ lex.yy.c st.tab.c
$./a.out
a+b*c -d
In Order:
a + b * c - d
Pre Order:
- + a * b c d
Post Order:
a b c * + d -



Comments

Post a Comment

Popular posts from this blog

KTU Compiler Lab CSL411 - Dr Binu V P

-
Preamble:  This course aims to offer students hands-on experience on compiler design concepts.Students will be able to familiarize with tools such as LEX and YACC and automate different phases of a compiler. This course helps the learners to enhance the capability to design and implement a compiler. Prerequisite: A sound knowledge in C programming, Data Structures, Formal languages and Automata Theory and Compiler design. About Me Syllabus and practise questions Lex yacc tutorial by Tom Neimann How to Install  flex and Bison Introduction to lex/flex Format of lex input files Lex Regular Expressions Input Matching in Lex Actions in Lex File Start Conditions in Lex Values available to the user in action section Reading and writing files Lex/Flex  Programs     Simple lexical analyser in C     count number of lines ,words and characters     check for valid identifiers     count the identifiers     converting the substring "abc...
Read more

lexical analyzer for a c program

-
 This program identifies tokens in a C program ignoring white spaces and comments.The input C program is given as argument ******************************* %{ #include <stdio.h> %} %option noyywrap /* Define regular expressions for different token types */ DIGIT      [0-9] LETTER     [a-zA-Z] IDENTIFIER {LETTER}({LETTER}|{DIGIT})* NUMBER     {DIGIT}+ WHITESPACE [ \t\n]+ COMMENT1    "//".* COMMENT2  "/*"([^*]|\*+[^/*])*\*+"/" %% {WHITESPACE}        { /* Ignore whitespace */ } {COMMENT1}           { /* Ignore comments */ } {COMMENT2}           { /* Ignore comments */ } "int"               { printf("TOKEN_INT\n"); } "return"            { printf("TOKEN_RETURN\n"); } "if"                { printf("TOKEN_IF\n"); } "else"    ...
Read more

count frequency of occurrence of a word - lex program

-
 LEX code to count the frequency of the given word(sachin)  in an input.txt file *************************************************** %{ #include<stdio.h> #include<string.h> char word [] = "sachin"; int count = 0; %} %option noyywrap /* Rule Section */ %% [a-zA-Z]+ { if(strcmp(yytext, word)==0)                                 count++; } .      ; \n      ; %% /* code section */ int main() {                 extern FILE *yyin, *yyout;                 /* open the input file                 in read mode */                 yyin=fopen("input.txt", "r");                 yylex();                 printf("No of occurance of the word ...
Read more