Compiler design lab manual
Introduction
Compiler is software that converts high-level language into a low-level
language. This process is known as compilation. And compilation takes
place in multiple steps. And the first step in the compilation is the lexical
analysis. LEX on Ubuntu or flex on window is a program that creates a
lexical analyzer and helps you to perform the task of lexical analysis.
Overview of compilation
Language
Translator
Translator is a program that takes an input program written in
one language and produces an output program in another
language.
Beside program translation, the translator performs another
very important role, error detection.
Types of translator
Interpreter
Compiler
Assembler
What is compiler?
Compiler is a program that can read a program written in high-level
language like c ,c++ and java(source language) and translate it into a low-
level language(which is machine language/target language).
Lists of compiler
C compiler
C++ compiler
Ada compiler
GCC COMPILER
The gcc compiler is an ANSI standard C compiler.
A C program goes through a lot of steps prior to becoming a running or
executing program. The gcc compiler performs a number of tasks for you.
Most notable are the following:
• Preprocesses the program code and looks for various directives.
• Generates error codes and messages, if applicable.
• Compiles program code into an object code and stores it temporarily on
disk.
• Links any necessary library to the object code and creates an executable
file and store
program structure
Let us look at a C program structure.
Hello World Example
A C program basically consists of the following parts:
Preprocessor Commands
Functions
Variables
Statements & Expressions
Comments
Let us look at a simple code that would print the words "Hello World":
#include <stdio.h>
int main(int argc, char *argv[])
/* my first program in C */
printf("Hello, world\n");
return 0;
Let us take a look at the various parts of the above program:
1. The first line of the program #include is a preprocessor command, which
tells a C compiler to include stdio.h file before going to actual compilation.
2. The next line int main() is the main function where the program
execution begins.
3. The next line /*...*/ will be ignored by the compiler and it has been put
to add additional comments in the program. So such lines are called
comments in the program.
4. The next line printf(...) is another function available in C which causes
the message "Hello, World!" to be displayed on the screen.
5. The next line return 0; terminates the main() function and returns the
value 0.
Compile and Execute C Program
1. Open a text editor and add the above-mentioned code.
2. Save the file as hello.c
3. Open a command prompt and go to the directory where you have saved
the file.
4. Type gcc hello.c and press enter to compile your code.
5. If there are no errors in your code, the command prompt will take you
to the next line and would generate [Link] executable file.
6. Now, type [Link] to execute your program.
7. You will see the output "Hello World" printed on the screen.
Exerecise
1. Write c program to the sum and average of 10 and 20.
#include <stdio.h>
int main(int argc, char *argv[])
int a=10;
int b=20;
int sum,avg;
sum=a+b;
avg=sum/2;
printf("the sum of %i and %i is =%i\n",a,b,sum);
printf("the average of %i and %i is =%i\n",a,b,avg);
return 0;
2. Write c program sum and average of any two numbers.
#include <stdio.h>
int main(int argc, char *argv[])
int a,b;
int sum,avg;
printf("enter two integer \n");
scanf("%i %i ",&a,&b);
sum=a+b;
avg=sum/2;
printf("the sum of two intrgers is :%i \n",sum);
printf("the average of two intrgers is %i",avg);
return 0;
Lexical Analysis
Compilation happens in multiple phases, and lexical analysis is the
starting Phases of Compiler. It gathers preprocessed source code, written in
high level language that comes as the preprocessor’s output. The lexical
analyzer generates a stream of tokens from the preprocessed source code
by removing white space and comments. It generates an error if it gets any
invalid token. The stream of character is read by it, and it seeks the legal
tokens, and then the data is passed to the syntax analyzer when asked for it.
Structure of flex program
Definition section:
%%
Rules section:
%%
C code section:
<Statements>
Regular Expression Basics
. : matches any single character except \n
*: matches 0 or more instances of the preceding regular expression
+: matches 1 or more instances of the preceding regular expression
? : matches 0 or 1 of the preceding regular expression
|: matches the preceding or following regular expression
[ ]: defines a character class
(): groups enclosed regular expression into a new regular expression
“…”: matches everything within the “ “ literally
Special function
• yytext
– where text matched most recently is stored
• yyleng
– number of characters in text most recently matched
• yylval
– associated value of current token
• yymore()
– append next string matched to current contents of yytext
• yyless(n)
– remove from yytext all but the first n characters
• unput(c)
– return character c to input stream
• yywrap()
– The yywrap method is called by the lexical analyser whenever it inputs
an EOF as the first character when trying to match a regular expression.
Lab one Flex program
LEX program to recognize and display keywords, number and
identifier for the given statements.
save the file with .l extension (identifier.l)
check the file type on your folder as L type
run the program using flex compiler as follow
flex file name.l
flex identifier.l
flex generate [Link].c file
run the c code using gcc compiler as follow
gcc [Link].c
execute the out put .exe file
out [Link]
accepting input stream
1. LEX program to recognize and display keywords, number and
identifier for the given statements.
%{
#include<stdio.h>
%}
%%
scanf |
switch |
printf {printf("\n %s is the keyword", yytext);}
[0-9]+ {printf("\n %s is a number",yytext);}
[a-zA-Z]+ {printf("\n %s is a Identifiers",yytext);}
.|\n {ECHO;}
%%
int main()
printf("Enter the input string \n");
yylex();
int yywrap()
return 1;
2. Write a LEX program to check weather input string is verb or not.
(list of verb are given)
%option noyywrap
%{
#include<stdio.h>
%}
%%
[\t]+
is |
am |
are |
was |
were {printf("%s: is a verb",yytext);}
[a-zA-Z]+ {printf("%s: is not a verb",yytext);}
%%
int main()
printf("enter string \n");
yylex();
return 0;
3. Write a LEX program to identify capital words from the given
input string.
%{
#include<stdio.h>
%}
%%
[A-Z]+[ \t\n] {printf("%s \n",yytext);}
.;
%%
int main()
{
printf("enter the input string: \n");
yylex();
return 0;
int yywrap(){
return 0;
4. LEX program to recognize whether a given sentence is simple or
compound.
/* LEX program to recognize whether a given sentence is simple or
compound*/
%{
#include<stdio.h>
int flag=0;
%}
%%
and |
or |
but |
because |
if |
then {flag=1;}
.;
\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;
5. write the LEX program which distinguish the vowels and
consonant and count its number.
%{
#include<stdio.h>
int v=0,c=0;
%}
%%
[ \t\n]+;
[aeiouAEIOU] {v++;}
[^aeiouAEIOU] {c++;}
%%
int main()
printf("Enter the input string \n");
yylex();
printf("then number of vowles are %d \n",v);
printf("the number of constants are %d \n",c);
int yywrap(){
return 1;
6. Write LEX program to count number lines ,spaces ,character and
words in a given statement.
%{
#include<stdio.h>
int sc=0,lc=0,cc=0,wc=0;
%}
%%
[\n] {lc++; cc+=yyleng;}
[ \t] {sc++; cc+=yyleng;}
[^\t\n ]+ {wc++; cc+=yyleng;}
%%
int main()
printf("enter input string \n");
yylex();
printf("number of lines are %d \n",lc);
printf("number of spaces are %d \n",sc);
printf("number of character are %d \n",cc);
printf("number of word are %d \n",wc);
return 0;
int yywrap()
return 1;
}
7. write a lex program to count number of character and number of
lines.
%{
#include<stdio.h>
int num_lines=0,num_chars=0;
%}
%%
\n {++ num_lines;++num_chars;}
. {++num_chars;}
%%
int main()
printf("enter string \n");
yylex();
printf("There are %s lines and %s characters. \n", num_lines,num_chars);
return 0;
int yywrap(){
return 1;
}
Syntax analysis using yacc tool
YACC is abbreviation for yet another compiler
compiler.
generate parse for the tokens generated from lexical
analyzer
it uses grammar (CFG)
The yacc program has a set of keywords that define
processing conditions for the generated parser.
Each of the keywords begin with a % (percent sign),
which is followed by a token or nonterminal name.
These keywords are as follows:
Keyword
%left Identifies tokens that are left-associative with
other tokens.
%nonassoc Identifies tokens that are not associative
with other tokens.
%right Identifies tokens that are right-associative with
other tokens.
%start Identifies a nonterminal name for the start
symbol.
%token Identifies the token names that the yacc
command accepts. Declares all token names in the
declarations section.
%type identifies the type of non-terminals. Type-
checking is performed when this construct is present.
%union Identifies the yacc value stack as the union of the
various type of values desired.
By default, the values returned are integers.
The effect of this construct is to provide the declaration of
YYSTYPE directly from the input.
How it execute the yacc
The yacc file must include the following steps to execute.
Save with file name.y extension (ex.y)
Save the token need to parse using file name.l
extension (ex.l)
execute using the following commend
– yacc -d ex.y
– The above code generates two file [Link].c
which is c code uses to parse and [Link].h which
consists header file to include in flex code used to
specify tokens
. – flex ex.l
– This also generate [Link].c which we cover on
lab one
– gcc [Link].c [Link].c -o out put
The above process can be summarized by the
following image
1. Write a flex and yacc program to display valid arithmetic
expression.
lex source code(ex.l)
%{
/* Definition section */
#include<stdio.h>
#include "[Link].h"
extern int yylval;
%}
/* Rule Section */
%%
[0-9]+ {
yylval=atoi(yytext);
return NUMBER;
}
[\t] ;
[\n] return 0;
. return yytext[0];
%%
int yywrap()
{
return 0;
}
yacc source code(ex.y)
%{
/* Definition section */
#include<stdio.h>
int flag=0;
%}
%token NUMBER
%left '+' '-'
%left '*' '/' '%'
%left '(' ')'
/* Rule Section */
%%
ArithmeticExpression: E{
printf("\nResult=%d\n", $$);
return 0;
};
E:E'+'E {$$=$1+$3;}
|E'-'E {$$=$1-$3;}
|E'*'E {$$=$1*$3;}
|E'/'E {$$=$1/$3;}
|E'%'E {$$=$1%$3;}
|'('E')' {$$=$2;}
| NUMBER {$$=$1;}
;
%%
void main()
{
printf("\nEnter Any Arithmetic Expression:\n");
yyparse();
if(flag==0)
printf("\nEntered arithmetic expression is Valid\n\n");
}
int yyerror(char* s) {
printf("\nExpression is invalid\n");
flag=1;
}