5B) Program to recognize strings ‘aaabbb’, ‘ab’, ‘aabb’ and ‘’ using the grammar (a^nb^n, n>= 0). [VTU SS&OS]

Code:

LEXX:
YACC:

Explanation:
This program recognizes equal number of A's and B's and display appropriate message.

Lexx part:

%{
#include "y.tab.h"
%}

Declaration section. Include y.tab.h for making lexer read the input symbol so that it can send tokens to Yacc parser.

%%
a {return A;}
b {return B;}
. {return yytext[0];}
\n {return yytext[0];}
%%

These are scanning input for some defined patterns and returning a token to parser. if we find 'a' or 'b' in the input, we return token A or B to Yacc parser. any other charcter, '.' will be returned as it is (by returning what was scanned as it is, yytext[0])

yywrap()
{} 

yywrap() function is responsible for checking whether there are any more inputs. If no, then yywrap() tells program to end.

Yacc part:

%{
#include<stdio.h>
#include<stdlib.h>
%}
%token A B

include header files in the declaration. inside %{ ... %}.  define tokens which are returned from lexer as in the lexer code above.

%%
str: s '\n' {  return 0;}
s : A s B   ;
 |  ;
%%

This is a grammar for str.

• str is defined as s followed by '\n'. If s is valid, then we return to main function to display success message.
• s is defined as a string AsB|; ( AsB or nothing)
• again in AsB, s substitutes to AsB, resulting in AAsBB. (hope you got it).
• this way recursively, it scans equal number of A's and B's. at the end when no more A and B's are left, (;) will be matched, indicating success. so s is valid, we return to main() and print success message.
• If s wasn't valid, yyparse() will print failure message.

main()
{
printf(" Type the String ?\n");
yyparse();
printf(" Valid String\n ");
}

main function, ask user for input, call yyparse() (to begin the process) and if no errors occured while processing, it will print the success message. 

int yyerror()
{
printf("  Invalid String.\n");  exit(0);
 }

If there were errors while processing, it will print failure message and terminate.

Author : Unknown

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!

Sharing is sexy!

Related Articles