Compiler Design (3170701) 230763107014
PRACTICAL-1
AIM:- Implementation of Finite Automata and String Validation.
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main(){
char word[50];
int l;
printf("Enter a Word:");
scanf("%s",word);
l=strlen(word);
char first=tolower(word[0]);
char last=tolower(word[l-1]);
if(first!=last){//if(first==last)same
printf("Valid");
}else{
printf("InValid");
return 0;}
OUTPUT:
1
Compiler Design (3170701) 230763107014
PRACTICAL-2
Aim:- Introduction to Lex & Flex Tool.
1.LEX:
Lex is a tool or a computer program that generates Lexical Analyzers (converts the stream of
characters into tokens). The Lex tool itself is a compiler. The Lex compiler takes the input and
transforms that input into input patterns. It is commonly used with YACC (Yet Another
Compiler Compiler). It was written by Mike Lesk and Eric Schmidt.
FUNCTION OF LEX:
1. In the first step the source code which is in the Lex language having the file name
‘File.l’ gives as input to the Lex Compiler commonly known as Lex to get the output
as lex.yy.c.
2. After that, the output lex.yy.c will be used as input to the C compiler which gives the
output in the form of an ‘a.out’ file, and finally, the output file a.out will take the stream
of character and generates tokens as output.
3. Lex.yy.c: It is a C Program.
File.l: It is Lex source Program.
a.out: It is a Lexical analyzer.
2
Compiler Design (3170701) 230763107014
LEX FILE FORMATE:
A Lex program consists of three parts and is separated by %% delimiters:-
2. FLEX:
FLEX (fast lexical analyzer generator) is a tool/computer program for generating lexical
analyzers written by Vern Paxson in C around 1987. Flex and Bison both are more flexible
than Lex and Yacc and produces faster code.
Bison produces parser from the input file provided by the user. The function yylex() is
automatically generated by the flex when it is provided with a.l file and this yylex() function
is expected by parser to call to retrieve tokens from current/this token stream.
Step 1: An input file describes the lexical analyzer to be generated named lex.l is written in
lex language. The lex compiler transforms lex.l to C program, in a file that is always named
lex.yy.c.
Step 2: The C compiler compile lex.yy.c file into an executable file called a.out.
Step 3: The output file a.out take a stream of input characters and produce a stream of tokens.
3
Compiler Design (3170701) 230763107014
Program Structure:
In the input file, there are 3 sections:
1. Definition Section: The definition section contains the declaration of variables, regular
definitions, manifest constants. In the definition section, text is enclosed in “%{ %}”
brackets. Anything written in this brackets is copied directly to the file lex.yy.c
Syntax:
%{
// Definitions
%}
2. Rules Section: The rules section contains a series of rules in the form: pattern action and
pattern must be unintended and action begin on the same line in {} brackets. The rule section
is enclosed in “%% %%”.
Syntax:
%%
pattern action
%%
3. User Code Section: This section contains C statements and additional functions. We can
also compile these functions separately and load with the lexical analyzer.
Basic Program Structure:
%{
// Definitions
%}
%%
Rules
%%
User code section
4
Compiler Design (3170701) 230763107014
PRACTICAL-3
Aim: Implementation following Programs Using Lex.
a. Generate Histogram of words
b. Check Cypher
c. Extract single and multiline comments from C Program
A. Generate Histogram of words :
/*lex program to count number of words*/
%{
#include<stdio.h>
#include<string.h>
int i = 0;
%}
/* Rules Section*/
%%
([a-zA-Z0-9])* {i++;} /* Rule for counting
number of words*/
"\n" {printf("%d\n", i); i = 0;}
%%
int yywrap(void){}
int main()
{
// The function that starts the analysis
yylex();
return 0;
}
Output:
5
Compiler Design (3170701) 230763107014
B. Check Cypher
%{
#include<stdio.h>
#include<string.h>
void encrypt(char *text, int shift);
%}
%option noyywrap
%%
[a-zA-Z]+ {
encrypt(yytext, 3);
}
.|\n {
putchar(yytext[0]);
}
%%
void encrypt(char *text, int shift)
{
while(*text)
{
char c = *text;
if(c>='a' && c<='z')
{
c='a'+(c-'a'+shift) % 26;
}
else if(c>='A' && c<='Z'){
c='A'+(c-'A'+shift) % 26;
}
putchar(c);
text++;
}
}
int main(){
yylex();
return 0;
}
6
Compiler Design (3170701) 230763107014
Output:
7
Compiler Design (3170701) 230763107014
c. Extract single and multiline comments from C Program
%{
#include<stdio.h>
int sl=0,ml=0,c;
%}
%%
[/]{1}[/]{1}[a-zA-Z0-9_]* {sl++;} printf("Single Line Comment %d",sl);
[/]{1}[*]{1}[a-zA-Z0-9_]*[*]{1}[/]{1} {ml++;} printf("Multiple Comment %d",ml);
%%
int yywrap(void){return 1;}
int main()
{
yylex();
return 0;
}
Output:
8
Compiler Design (3170701) 230763107014
PRACTICAL-4
AIM:- Implement following Programs Using Lex.
A. Convert Roman to Decimal
B. Check weather given statement is compound or simple
C. Extract html tags from .html file
a) Convert Roman to Decimal
%{
#include <stdio.h>
int total = 0;
%}
WS [ \t]+
%%
I { total += 1; }
IV { total += 4; }
V { total += 5; }
IX { total += 9; }
X { total += 10; }
XL { total += 40; }
L { total += 50; }
XC { total += 90; }
C { total += 100; }
CD { total += 400; }
D { total += 500; }
CM { total += 900; }
M { total += 1000; }
{WS} ; /* ignore whitespace */
\n { return 0; } /* stop at newline */
. ; /* ignore any other characters */
%%
int main(void) {
printf("Enter Roman Number: ");
yylex(); // process input
printf("Decimal Number is: %d\n", total);
return 0;
}
int yywrap(void) {
return 1;
}
9
Compiler Design (3170701) 230763107014
OUTPUT:-
10
Compiler Design (3170701) 230763107014
b) Check weather given statement is compound or simple
%{
#include<stdio.h>
int flag=0;
%}
%%
and { flag=1; }
or { flag=1; }
but { flag=1; }
because { flag=1; }
if { flag=1; }
then { flag=1; }
nevertheless { flag=1; }
. { /* ignore other characters */ }
\n { return 0; }
%%
int main()
{
printf("Enter the sentence:\n");
yylex();
if(flag==0)
printf("Simple sentence\n");
else
printf("Compound sentence\n");
return 0;
}
int yywrap()
{
return 1;
}
OUTPUT:
11
Compiler Design (3170701) 230763107014
c) Extract html tags from .html file
%{
#include <stdio.h>
FILE *yyin, *yyout;
%}
%%
\<[^>]*\> { fprintf(yyout, "%s\n", yytext); }
.|\n { /* ignore everything else */ }
%%
int yywrap()
{
return 1;
}
int main()
{
yyin = fopen("pr4.html", "r");
yyout = fopen("output4.txt", "w"); // uncomment if you want file output
if(!yyin) {
printf("Could not open input file\n");
return 1;
}
yylex();
fclose(yyin);
fclose(yyout);
return 0;
}
Pr4.html
<html>
<head>
<title>Sample Program</title>
</head>
<body>
<p>HELLO!! GOOD MORNING...</p>
</body>
</html>
OUTPUT:
12
Compiler Design (3170701) 230763107014
PRACTICAL-5
AIM: Implementation of Recursive descent parser without backtracking input:
the string to be parsed. output: whether string passed successfully or not.
explanation: Student have to implement the recursive procedure for RDP for a
typical grammar. The production number are displayed as they are used to
derive string.
#include <stdio.h>
#include <string.h>
#define SUCCESS 1
#define FAILED 0
int E(), Edash(), T(), Tdash(), F();
const char *cursor;
char string[64];
int main() {
puts("Enter the string");
scanf("%s", string);
cursor = string;
puts("");
puts("Input Action");
puts("--------------------------------");
if (E() && *cursor == '\0') {
puts("--------------------------------");
puts("String is successfully parsed");
return 0;
} else {
puts("--------------------------------");
13
Compiler Design (3170701) 230763107014
puts("Error in parsing String");
return 1;
int E() {
printf("%-16s E -> T E'\n", cursor);
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
int Edash() {
if (*cursor == '+') {
printf("%-16s E' -> + T E'\n", cursor);
cursor++;
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
} else {
printf("%-16s E' -> $\n", cursor);
14
Compiler Design (3170701) 230763107014
return SUCCESS;
int T() {
printf("%-16s T -> F T'\n", cursor);
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
int Tdash() {
if (*cursor == '*') {
printf("%-16s T' -> * F T'\n", cursor);
cursor++;
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
} else {
printf("%-16s T' -> $\n", cursor);
return SUCCESS;
15
Compiler Design (3170701) 230763107014
int F() {
if (*cursor == '(') {
printf("%-16s F -> ( E )\n", cursor);
cursor++;
if (E()) {
if (*cursor == ')') {
cursor++;
return SUCCESS;
} else
return FAILED;
} else
return FAILED;
} else if (*cursor == 'i') {
printf("%-16s F -> i\n", cursor);
cursor++;
return SUCCESS;
} else
return FAILED;
OUTPUT:-
16
Compiler Design (3170701) 230763107014
PRACTICAL-6
AIM:- Find the “First” set.
Input: The string consists of grammar symbols.
Output: The First set for a given string.
Explanation: The student has to assume a typical grammar. The program when
run will ask for the string to be entered. The program will find the first set of the
given string.
#include <ctype.h>
#include <stdio.h>
#include <string.h>
// Function to calculate FIRST
void findfirst(char, int, int);
int count, n = 0;
char production[10][10];
char first[10]; // temporary storage
char calc_first[10][100]; // final FIRST sets
int main() {
int i, j;
int jm = 0;
int point1 = 0, point2, xxx;
char c;
// Grammar (productions)
count = 8;
strcpy(production[0], "A=BnC");
strcpy(production[1], "A=Ds");
17
Compiler Design (3170701) 230763107014
strcpy(production[2], "B=q");
strcpy(production[3], "B=#");
strcpy(production[4], "C=p");
strcpy(production[5], "C=+");
strcpy(production[6], "D=ab");
strcpy(production[7], "D=BC");
char done[count];
int ptr = -1;
// initialize calc_first with !
for (i = 0; i < count; i++) {
for (j = 0; j < 100; j++) {
calc_first[i][j] = '!';
for (int k = 0; k < count; k++) {
c = production[k][0];
point2 = 0;
xxx = 0;
// check if already calculated
for (int kay = 0; kay <= ptr; kay++) {
if (c == done[kay]) {
xxx = 1;
}
}
if (xxx == 1)
18
Compiler Design (3170701) 230763107014
continue;
// reset temporary FIRST
n = 0;
findfirst(c, 0, 0);
ptr++;
done[ptr] = c;
printf("First(%c) = { ", c);
for (i = 0; i < n; i++) {
int found = 0;
for (j = 0; j < point2; j++) {
if (first[i] == calc_first[point1][j]) {
found = 1;
break;
if (!found) {
printf("%c ", first[i]);
calc_first[point1][point2++] = first[i];
printf("}\n");
point1++;
return 0;
}
void findfirst(char c, int q1, int q2) {
19
Compiler Design (3170701) 230763107014
int j;
// terminal symbol
if (!isupper(c)) {
first[n++] = c;
return;
for (j = 0; j < count; j++) {
if (production[j][0] == c) {
// epsilon case
if (production[j][2] == '#') {
if (production[q1][q2] == '\0')
first[n++] = '#';
else if (production[q1][q2] != '\0'
&& (q1 != 0 || q2 != 0)) {
findfirst(production[q1][q2], q1, q2 + 1);
} else {
first[n++] = '#';
}
// if terminal on RHS
else if (!isupper(production[j][2])) {
first[n++] = production[j][2];
// if nonterminal on RHS
else {
findfirst(production[j][2], j, 3);
}
20
Compiler Design (3170701) 230763107014
OUTPUT:
21
