6) Program to recognize the grammar (anb, n>= 10). [VTU SS&OS]

Code:

LEXX:
YACC:

Explanation:
In this code, we match the pattern a^nb (where n>=10), there must be atleast 10 A's followed by one single B. If this is the case, we print "valid", otherwise "invalid".

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 : x B  ;
x : A A A A A A A A A A T  ;
T: T A
| ;
%%

This is nothing but grammar. Lets go line by line.

• First line, str is a string grammar, which defines, if a string s is followed by '\n' we will return control to main program and display success message. But s needs to be valid. what is s? we will see.
• 's' is defined as 'x' followed by B. This is since we have the question as more than 10 A's followed by B. Now we define x to be more than or equal to 10 A's.
• 'x' is defined as 10 A's followed by T. 10 is compulsory, any more A's is optional.
• T is defined as A|; (A or nothing).

So basically there are 10 or more A's and one B. if this is true, s will be valid. hence step 1 returns to main().

Otherwise, it will not return anything, yyerror() is called to display 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