Ss Lab Manual

S J C INSTITUTE OF TECHNOLOGY
CHICKBALLAPUR-562101
Department of Computer Science and Engineering
System Software Laboratory Manual
18CSL66
VI – SEMESTER

VISION
To build competent professionals embedded with human values to meet the challenges in the
field of Computer Science & Engineering.
MISSION
Empower the graduates with the fundamentals in design and implementation of
M1 computational systems through curriculum and research in collaboration with
Industry and other organization.
Imparting Center of Excellence in state-of-Art Infrastructure to make competent

M2
graduates by providing professionally committed Faculties
Inculcate Ethical values, Technical Capabilities & Leadership abilities for meeting
M3
the current and future demands of Industry and Society
PROGRAM EDUCATIONAL OBJECTIVES

Graduates will have strong foundation in fundamentals to solve Engineering
PEO-1
problems in different domains.
Graduates will have successful careers as computer Science Engineers and be able
PEO-2
to lead & manage teams.
Graduates will instill interpersonal skills and attitudes in the process of Life long
PEO-3
learning.
ii
PROGRAM OUTCOMES (POs)
Engineering Graduates will be able to:
1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex engineering
problems.
2. Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.
3. Design/development of solutions: Design solutions for complex engineering problems
and design system components or processes that meet the specified needs with
appropriate consideration for the public health and safety, and the cultural, societal, and
environmental considerations.
4. Conduct investigations of complex problems: Use research-based knowledge and
research methods including design of experiments, analysis and interpretation of data,
and synthesis of the information to provide valid conclusions.
5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and
modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.
6. The engineer and society: Apply reasoning informed by the contextual knowledge to
assess societal, health, safety, legal and cultural issues and the consequent
responsibilities relevant to the professional engineering practice.
7. Environment and sustainability: Understand the impact of the professional engineering
solutions in societal and environmental contexts, and demonstrate the knowledge of, and
need for sustainable development.
8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities
and norms of the engineering practice.
9. Individual and team work: Function effectively as an individual, and as a member or
leader in diverse teams, and in multidisciplinary settings.
10. Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and
write effective reports and design documentation, make effective presentations, and give
and receive clear instructions.
11. Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member
and leader in a team, to manage projects and in multidisciplinary environments.
12. Life-long learning: Recognize the need for, and have the preparation and ability to
engage in independent and life-long learning in the broadest context of technological
change.
iii
PROGRAM SPECIFIC OUTCOMES (PSOs)

Ability to adapt to a rapidly changing environment by learning and employing
PSO-1
new programming skills and technologies
Ability to use diverse knowledge across the domains with inter-personnel skills
PSO-2
to deliver the Industry need
iv
Course Learning Objectives
This course will help students to achieve the following objectives:
1. To make students familiar with Lexical Analysis and Syntax Analysis phases of
Compiler Design and implement programs on these phases using LEX & YACC tools
and/or C/C++/Java
2. To enable students to learn different types of CPU scheduling algorithms used in
operating system.
3. To make students able to implement memory management - page replacement and
deadlock handling algorithms.
Course Outcomes
At the end of the course students should be able to:
1. Implement and demonstrate the scanning process using Lex tool.

2. Develop and demonstrate the parsing techniques using YACC tool or C
programming.
3. Evaluate different algorithms required for scheduling and deadlock.
4. Devise different algorithms required for memory management used in operating
system.
CO-PO MAPPING
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 3 1 2
CO2 3 1 2
CO3 3 2
CO4 3 2
v
CO-PO MAPPING JUSTIFICATION
Apply the knowledge of lexical analysis to define different tokens of a particular

PO1 3
language.
CO1 Analyse the usage of regular expressions to provide solution for different language
PO2 1
constructs.
PO5 2 Apply the knowledge of Lex tool usage for different patterns.
Apply the knowledge of syntax analysis to design various context free grammars for
PO1 3
a particular language constructs.
CO2 PO2 1 Analyse the usage of type -2 grammar to build a syntax analyzer.
18CSL66 Apply the knowledge of YACC tool or C language to explain control flow of an
PO5 2
application.
Apply the knowledge of process scheduling and dead lock concepts to develop real
PO1 3
CO3 time application.
PO2 2 Analyze and devise the performance of different scheduling algorithms.
Apply the knowledge of memory management concepts to develop real time
PO1 3
application.
CO4
Analyze and devise the better optimization methods for memory management using
PO2 2
different algorithm.
vi
System Software Laboratory
Subject Code: 18CSL66 I.A. Marks : 40
Hours/Week : 04 Exam Hours: 3
Total Hours : 36 Exam Marks: 60
List of Programs
Sl. Name of the Experiment Page No.
No
1 a) Write a LEX program to recognize valid arithmetic expression.
Identifiers in the expression could be only integers and operators could 1
be + and *. Count the identifiers & operators present and print them
separately.
b) Write YACC program to evaluate arithmetic expression involving
operators: +, -, *, and /
2 Develop, Implement and Execute a program using YACC tool to

recognize all strings ending with b preceded by n a’s using the 5
grammar an b (note: input n value)
3 Design, develop and implement YACC/C program to construct
Predictive / LL(1) Parsing Table for the grammar rules: A →aBa , B 7
→bB | ε. Use this table to parse the sentence: abba$
4 Design, develop and implement YACC/C program to demonstrate Shift
Reduce Parsing technique for the grammar rules: E →E+T | T, T →T*F 14
| F, F →(E) | id and parse the sentence: id + id * id.
5 Design, develop and implement a C/Java program to generate the
machine code using Triples for the statement A = -B * (C +D) whose
intermediate code in three-address form:
T1 = -B 18
T2 = C + D
T3 = T1 *T2
A = T3
6 a) Write a LEX program to eliminate comment lines in a C program
and copy the resulting program into a separate file.
20
b) Write YACC program to recognize valid identifier, operators and
keywords in the given text (C program) file.
7 Design, develop and implement a C/C++/Java program to simulate the
working of Shortest remaining time and Round Robin (RR) scheduling 24
algorithms. Experiment with different quantum sizes for RR algorithm.
8 Design, develop and implement a C/C++/Java program to implement
Banker’s algorithm. Assume suitable input required to demonstrate the 29
results.
9 Design, develop and implement a C/C++/Java program to implement
page replacement algorithms LRU and FIFO. Assume suitable input 35
required to demonstrate the results
vii
INTRODUCTION TO LEX
Lex and YACC helps you write programs that transforms structured input. Lex
generates C code for lexical analyzer whereas YACC generates Code for Syntax analyzer.
Lexical analyzer is build using a tool called LEX. Input is given to LEX and lexical analyzer
is generated.
Lex is a UNIX utility. It is a program generator designed for lexical processing of
character input streams. Lex generates C code for lexical analyzer. It uses the patterns that
match strings in the input and converts the strings to tokens. Lex helps you by taking a set
of descriptions of possible tokens and producing a C routine, which we call a lexical
analyzer. The token descriptions that Lex uses are known as regular expressions.
1.1Steps in writing LEX Program:
1st Step: Using gedit create a file with extension l. For example: prg1.l
2nd Step: lex prg1.l
3rd Step: cc lex.yy.c –ll
4th Step: ./a.out
1.2 Structure of LEX source program:
{definitions}
%%
{rules}
%%
{user subroutines/code section}
%% is a delimiter to the mark the beginning of the Rule section. The second %% is optional,
but the first is required to mark the beginning of the rules. The definitions and the code
/subroutines are often omitted.
viii
Lex variables
yyin Of the type FILE*. This points to the current file being parsed by the lexer.
yyout Of the type FILE*. This points to the location where the output of the lexer
will be written. By default, both yyin and yyout point to standard input and
output.
yytext The text of the matched pattern is stored in this variable (char*).
yyleng Gives the length of the matched pattern.
yylineno Provides current line number information. (May or may not be supported by
the lexer.)
Lex functions
yylex() The function that starts the analysis. It is automatically generated by Lex.
yywrap() This function is called when end of file (or input) is encountered. If this
function returns 1, the parsing stops. So, this can be used to parse multiple
files. Code can be written in the third section, which will allow multiple
files to be parsed. The strategy is to make yyin file pointer (see the
preceding table) point to a different file until all the files are parsed. At the
end, yywrap() can return 1 to indicate end of parsing.
yyless(int n) This function can be used to push back all but first „n‟ characters of the
read token.
yymore() This function tells the lexer to append the next token to the current token.
1.3 Regular Expressions
It is used to describe the pattern. It is widely used to in lex. It uses meta language. The
character used in this meta language are part of the standard ASCII character set. An
expression is made up of symbols. Normal symbols are characters and numbers, but there
are other symbols that have special meaning in Lex. The following two tables define some
of the symbols used in Lex and give a few typical examples.
Character Meaning
A-Z, 0-9, a-z Characters and numbers that form part of the pattern.
. Matches any character except \n.
Used to denote range. Example: A-Z implies all characters from A
- to Z.
A character class. Matches any character in the brackets. If the first
[] character is ^ then it indicates a negation pattern. Example: [abC]
matches either of a, b, and C.
* Match zero or more occurrences of the preceding pattern.
Matches one or more occurrences of the preceding pattern.(no
empty string).
+ Ex: [0-9]+ matches “1”,”111” or “123456” but not an empty string.
ix
Matches zero or one occurrences of the preceding pattern. Ex:
-?[0-9]+ matches a signed number including an optional
? leading minus.
$ Matches end of line as the last character of the pattern.
1) Indicates how many times a pattern can be present. Example:
A{1,3} implies one to three occurrences of A may be present.
2) If they contain name, they refer to a substitution by that name.
{} Ex: {digit}
Used to escape meta characters. Also used to remove the special
\ meaning of characters as defined in this table.
Ex: \n is a newline character, while “\*” is a literal asterisk.
^ Negation.
Matches either the preceding regular expression or the following
regular expression.
| Ex: cow|sheep|pig matches any of the three words.
"< symbols>" Literal meanings of characters. Meta characters hold.
Look ahead. Matches the preceding pattern only if followed by the
succeeding expression. Example: A0/1 matches A0 only if A01 is
/ the input.
Groups a series of regular expressions together into a new regular
expression.
Ex: (01) represents the character sequence 01. Parentheses are
() useful when building up complex patterns with *,+ and |
Examples of regular expressions

Regular Meaning
expression
joke[rs] Matches either jokes or joker.
A{1,2}shis+ Matches AAshis, Ashis, AAshi, Ashi.
Matches zero or one occurrences of A followed by any character
(A[b-e])+ from b to e.
[0-9] 0 or 1 or 2 or………9
[0-9]+ 1 or 111 or 12345 or …At least one occurrence of preceding exp
[0-9]* Empty string (no digits at all) or one or more occurrence.
-?[0-9]+ -1 or +1 or +2 …..
[0.9]*\.[0.9]+ 0.0,4.5 or .31415 But won‟t match 0 or 2
Examples of token declarations

Token Associated expression Meaning
number ([0-9])+ 1 or more occurrences of a
digit
chars [A-Za-z] Any character
Blank "" A blank space
Word (chars)+ 1 or more occurrences of chars
Variable (chars)+(number)*(chars)*( number)*
x
INTRODUCTION TO YACC
YACC provides a general tool for imposing structure on the input to a computer
program. The input specification is a collection of grammar rules. Each rule describes an
allowable structure and gives it a name. YACC prepares a specification of the input process.
YACC generates a function to control the input process. This function is called a parser.
The name is an acronym for “Yet Another Compiler Compiler”. YACC generates
the code for the parser in the C programming language. YACC was developed at AT& T for
the Unix operating system. YACC has also been rewritten for other languages, including
Java, Ada.
The function parser calls the lexical analyzer to pick up the tokens from the input
stream. These tokens are organized according to the input structure rules .The input structure
rule is called as grammar. When one of the rule is recognized, then user code supplied for
this rule ( user code is action) is invoked. Actions have the ability to return values and
makes use of the values of other actions.
2.1 Steps in writing YACC Program:

1st Step: Using gedit editor create a file with extension y. For example: gedit prg1.y
nd
2 Step: YACC –d prg1.y
rd
3 Step: lex prg1.l
th
4 Step: cc y.tab.c lex.yy.c -ll
5th Step: /a.out
When we run YACC, it generates a parser in file y.tab.c and also creates an include
file y.tab.h. To obtain tokens, YACC calls yylex. Function yylex has a return type of int, and
returns the token. Values associated with the token are returned by lex in variable yylval.
xi
2.2 Structure of YACC source program:
Basic Specification:
Every YACC specification file consists of three sections. The declarations, Rules
(of grammars), programs. The sections are separated by double percent “%%” marks. The
% is generally used in YACC specification as an escape character.
The general format for the YACC file is very similar to that of the Lex file.
{definitions}
%%
{rules}
%%
{user subroutines}
%% is a delimiter to the mark the beginning of the Rule section.
Definition Section
%union It defines the Stack type for the Parser. It is a union of various datas/structures/
Objects
%token These are the terminals returned by the yylex function to the YACC. A token can
also have type associated with it for good type checking and syntax directed
translation. A type of a token can be specified as %token <stack
member>tokenName.
Ex: %token NAME NUMBER
%type The type of a non-terminal symbol in the Grammar rule can be specified with
this.The format is %type <stack member>non-terminal.
%noassoc Specifies that there is no associatively of a terminal symbol.
%left Specifies the left associatively of a Terminal Symbol
%right Specifies the right associatively of a Terminal Symbol.
%start Specifies the L.H.S non-terminal symbol of a production rule which should be
taken as the starting point of the grammar rules.
%prec Changes the precedence level associated with a particular rule to that of the
following token name or literal
xii
Rules Section
The rules section simply consists of a list of grammar rules. A grammar rule has the form:
A: BODY
A represents a nonterminal name, the colon and the semicolon are YACC punctuation and
BODY represents names and literals. The names used in the body of a grammar rule may
represent tokens or nonterminal symbols. The literal consists of a character enclosed in single
quotes.
Names representing tokens must be declared as follows in the declaration sections:
%token name1 name2…

Every name not defined in the declarations section is assumed to represent a
nonterminal symbol. Every non-terminal symbol must appear on the left side of at least one
rule. Of all the no terminal symbols, one, called the start symbol has a particular
importance. The parser is designed to recognize the start symbol. By default the start
symbol is taken to be the left hand side of the first grammar rule in the rules section.
With each grammar rule, the user may associate actions to be. These actions may return
values, and may obtain the values returned by the previous actions. Lexical analyzer can return
values for tokens, if desired. An action is an arbitrary C statement. Actions are enclosed in
curly braces.
xiii
INTRODUCTION TO UNIX
Basic UNIX commands
Folder/Directory Commands and Options

Action UNIX options & filespec
Check current Print Working Directory Pwd
Return to user's home folder Cd
Up one folder cd ..
Make directory mkdir proj1
Remove empty directory rmdir/usr/sam
Remove directory-recursively rm –r
File Listing Commands and Options

List directory tree- recursively ls –r
List last access dates of files, with hidden
files ls -l –a
List files by reverse date ls -t -r *.*
List files verbosely by size of file ls -l -s *.*
List files recursively including contents of
other directories ls -R *.*
List number of lines in folder wc -l *.xtumlsed -n '$='
List files with x anywhere in the name ls | grep x
File Manipulation Commands and Options

Create new(blank)file touch afilename
Copy old file to new file. -p preserve file
attributes(e.g. ownership and edit dates)-r
copy recursively through directory
structure -a archive, combines the flags-p –
R and-d cp old.filenew.file
Move old.file(-i interactively flag prompts
before overwriting files) mv –i old.file/tmp
Remove file(-intention) rm –i sam.txt
View a file vi file.txt
Concatenate files cat file1file2 to standard output.
Counts-lines,-words, and- characters in a
file wc -l
xiv
INTRODUCTION TO OPERATING SYSTEMS
Introduction
An Operating System is a program that manages the Computer hardware. It controls

and coordinates the use of the hardware among the various application programs for the
various users.
A Process is a program in execution. As a process executes, it changes state
 New: The process is being created

 Running: Instructions are being executed
 Waiting: The process is waiting for some event to occur
 Ready: The process is waiting to be assigned to a process
 Terminated : The process has finished execution
Apart from the program code, it includes the current activity represented by

 Program Counter,

 Contents of Processor registers,

Process Stack which contains temporary data like function parameters, return addresses
and local variables

 Data section which contains global variables

Heap for dynamic memory allocation
A Multi-programmed system can have many processes running simultaneously

with the CPU multiplexed among them. By switching the CPU between the processes, the
xv
OS can make the computer more productive. There is Process Scheduler which selects the
process among many processes that are ready, for program execution on the CPU.
Switching the CPU to another process requires performing a state save of the current process
and a state restore of new process, this is Context Switch.
4.1 Scheduling Algorithms
CPU Scheduler can select processes from ready queue based on various scheduling
algorithms. Different scheduling algorithms have different properties, and the choice of a
particular algorithm may favor one class of processes over another. The scheduling criteria
include

 CPU utilization:
  Throughput: The number of processes that are completed per unit time. 
  Waiting time: The sum of periods spent waiting in ready queue. 


Turnaround time: The interval between the time of submission of process to the time
 of completion.

Response time: The time from submission of a request until the first response is
produced.
The different scheduling algorithms are


 FCFS: First Come First Served Scheduling
  SJF: Shortest Job First Scheduling
  SRTF: Shortest Remaining Time First Scheduling
  Priority Scheduling
  Round Robin Scheduling
  Multilevel Queue Scheduling


Multilevel Feedback Queue Scheduling
4.2 Deadlocks
A process requests resources; and if the resource is not available at that time, the
process enters a waiting state. Sometimes, a waiting process is never able to change state,
because the resource is has requested is held by another process which is also waiting. This
situation is called Deadlock. Deadlock is characterized by four necessary conditions
  Mutual Exclusion
xvi
  Hold and WaitNo PreemptionCircular Wait
Deadlock can be handled in one of these ways,


 Deadlock Avoidance

Deadlock Detection and Recover
Shortest remainingtime scheduling algorithm:
Shortest remaining time, also known as shortest remaining time first (SRTF), is
aschedulingmethod that is apreemptiveversion ofshortest job nextscheduling. In this
scheduling algorithm, theprocesswith the smallest amount of time remaining until
completion is selected to execute. Since the currently executing process is the one with the
shortest amount of time remaining by definition, and since that time should only reduce as
execution progresses, processes will always run until they complete or a new process is
added that requires a smaller amount of time.
Shortest remaining time is advantageous because short processes are handled very
quickly. The system also requires very little overhead since it only makes a decision when a
process completes or a new process is added, and when a new process is added the algorithm
only needs to compare the currently executing process with the new process, ignoring all
other processes currently waiting to execute.
Like shortest job first, it has the potential forprocess starvation; long processes may
be held off indefinitely if short processes are continually added.
Round Robin (RR) scheduling algorithm:
Round-robin (RR) is one of the algorithms employed by process and

networkschedulers in computing. As the term is generally used, time slices (also known as
time quanta) are assigned to each process in equal portions and in circular order, handling
all processes without priority (also known as cyclic executive). Round-robin scheduling is
simple, easy to implement, and starvation-free. Round-robin scheduling can also be applied
to other scheduling problems, such as data packet scheduling in computer networks. It is an
operating system concept.
The name of the algorithm comes from the round-robin principle known from other
fields, where each person takes an equal share of something in turn.
xvii
Banker’s algorithm:
The Banker's algorithm, sometimes referred to as the detection algorithm, is a
resourceallocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests
for safety by simulating the allocation of predetermined maximum possible amounts of all
resources, and then makes an "s-state" check to test for possible deadlock conditions for all
other pending activities, before deciding whether allocation should be allowed to continue.
The algorithm was developed in the design process for the operating system and
originally described (in Dutch) in EWD108. When a new process enters a system, it must
declare the maximum number of instances of each resource type that it may ever claim;
clearly, that number may not exceed the total number of resources in the system. Also, when
a process gets all its requested resources it must return them in a finite amount of time.
Page replacement algorithms LRU and FIFO:
In a computer operating system that uses paging for virtual memory management,
pagereplacement algorithms decide which memory pages to page out, sometimes called
swap out, or writeto disk, when a page of memory needs to be allocated. Page replacement
happens when a requested page is not in memory (page fault) and a free page cannot be
used to satisfy the allocation, either because there are none, or because the number of free
pages is lower than some threshold.
When the page that was selected for replacement and paged out is referenced again
it has to be paged in (read in from disk), and this involves waiting for I/O completion. This
determines the quality of the page replacement algorithm: the less time waiting for page-
ins, the better the algorithm. A page replacement algorithm looks at the limited information
about accesses to the pages provided by hardware, and tries to guess which pages should be
replaced to minimize the total number of page misses, while balancing this with the costs
(primary storage and processor time) of the algorithm itself. The page replacing problem is
a typical online problem from the competitive analysis perspective in the sense that the
optimal deterministic algorithm is known.
xviii
INTRODUCTION TO COMPILER DESIGN
A program for a computer must be built by combining these very simple commands into a
program in what is called machine language. Since this is a tedious and error prone process most
programming is, instead, done using a high-level programming language. This language can be very
different from the machine language that the computer can execute, so some means of bridging the
gap is required. This is where the compiler comes in. A compiler translates (or compiles) a program
written in a high-level programming language that is suitable for human programmers into the
lowlevel machine language that is required by computers.
The phases of a compiler:

Lexical analysis: This is the initial part of reading and analysing the program text: The text is read
and divided into tokens, each of which corresponds to a symbol in the programming language, e.g., a
variable name, keyword or number.
Syntax analysis: This phase takes the list of tokens produced by the lexical analysis and arranges
these in a tree-structure (called the syntax tree) that reflects the structure of the program. This phase
is often called parsing.
Type checking: This phase analyses the syntax tree to determine if the program violates certain
consistency requirements, e.g., if a variable is used but not declared or if it is used in a context that
does not make sense given the type of the variable, such as trying to use a boolean value as a
function pointer.
Intermediate code generation: The program is translated to a simple machine independent
intermediate language.
Register allocation: The symbolic variable names used in the intermediate code are translated to
numbers, each of which corresponds to a register in the target machine code.
Machine code generation: The intermediate language is translated to assembly language (a textual
representation of machine code) for a specific machine architecture.
Assembly and linking: The assembly-language code is translated into binary representation and
addresses of variables, functions, etc., are determined.
Parsing:
A parser is a compiler or interpreter component that breaks data into smaller
elements for easy translation into another language. A parser takes input in the form of a
sequence of tokens or program instructions and usually builds a data structure in the form
of a parse tree or an abstract syntax tree.
xix
A parser's main purpose is to determine if input data may be derived from the start
symbol of the grammar.
Syntax analyzers follow production rules defined by means of context-free grammar.

The way the production rules are implemented (derivation) divides parsing into two types:
top-down parsing and bottom-up parsing.
Top-Down Parsing:
When the parser starts constructing the parse tree from the start symbol and then tries
to transform the start symbol to the input, it is called top-down parsing.
• Recursive descent parsing: It is a common form of top-down parsing. It is called

recursive as it usesrecursive procedures to process the input. Recursive descent parsing
suffers from backtracking.
• Backtracking: It means, if one derivation of a production fails, the syntax analyzer

restarts the processusing different rules of same production. This technique may
process the input string more than once to determine the right production.
Shift Reduce Parsing/Bottom up parsing:
Bottom-up parsing starts with the input symbols and tries to construct the parse tree
up to the start symbol. Bottom up parsing can be defined as an attempt to reduce the input
string „w‟ to the start symbol of a grammar by tracing out the rightmost derivations of „w‟
in reverse.
Shift-reduce Parsing (Bottom-up Parsing)
Shift-reduce parsing attempts to construct a parse tree for an input string beginning
at the leaves and working up towards the root. In other words, it is a process of “reducing”
xx
(opposite of deriving a symbol using a production rule) a string w to the start symbol of a
grammar. At every (reduction) step, a particular substring matching the RHS of a production
rule is replaced by the symbol on the LHS of the production.
A general form of shift-reduce parsing is LR (scanning from Left to right and using
Right-most derivation in reverse) parsing, which is used in a number of automatic parser
generators like Yacc, Bison, etc.
Intermediate code/ three address code:
Three-address code(often abbreviated to TAC or 3AC) is anintermediate codeused
byoptimizing compilersto aid in the implementation ofcode-improving transformations.
Each TAC instruction has at most three operands and is typically a combination of
assignment and a binary operator. For example, t1 = t2 + t3. The name derives from the use
of three operands in these statements even though instructions with fewer operands may
occur.
Since three-address code is used as an intermediate language within compilers, the
operands will most likely not be concrete memory addresses orprocessor registers, but rather
symbolic addresses that will be translated into actual addresses duringregister allocation. It
is also not uncommon that operand names are numbered sequentially since three-address
code is typically generated by the compiler.
Example: One solution to the quadratic equation using three address code is as
below. x = (-b + sqrt(b^2 - 4*a*c)) / (2*a) t1 = b * b t2 = 4 * a t3 = t2 * c t4 = t1 - t3
t5 = sqrt(t4) t6 = 0 - b t7 = t5 + t6 t9 = t7 / t8 x = t9 t8 = 2 * a
xxi
Procedure for Program Execution
 For Lex Program
Step 1: Create the lex file in unix envirnonment
vi filename.l
Step 2: Save and quit
Press Esc : wq if vi is used
Step 3: Compile the program using command
lex filename.l and
cc lex.yy.c -ll
Step 4:Execute the program using command:
./a.out
 For Yacc Program
Step 1: Create the lex file and yacc file both in unix envirnonment
vi filename.l
vi filename.y
Step 3: Compile the both program using command
lex filename.l
yacc –d filename.y
cc lex.yy.c y.tab.c –ll –ly
Step 4:Execute the program using command:
./a.out
 For C/C++ Program
Step 1: Create the C/C++ file in unix envirnonment
vi filename.c
vi filename.cpp
Step 3: Compile the both program using command
cc filename.c
g++ filename.cpp
Step 4: Execute the program using command:
./a.out
xxii
SS LAB(18CSL66)
Program: 1A
Write a LEX program to recognize valid arithmetic expression. Identifiers in the expression
could be only integers and operators could be + and *. Count the identifiers & operators present
and print them separately.
PREREQUISITES
1. Define Regular Expression.
2. List and explain RE with examples.
3. Phases of Compiler.
4. Structure of Lex.
SOURCE CODE
%{
#include<stdio.h>
#include<string.h>
int c1=0,c2=0,c3=0,brackets=0,flag=0,l=0,i,k=0;
char opnd[20][20],oprt[20][20];
%}
%%
"+"|"*" {c1++; c2++; strcpy(oprt[k],yytext); k++;}
[0-9]+ {c2++; c3++;strcpy(opnd[l],yytext); l++;}
[(] brackets++;
[)] {if(brackets>0)
{ brackets--;}
else
flag=1;}
[\n] return;
%%
main()
{
printf("enter the expression\n");
yylex();
printf("the number of operators=%d\n",c1);
printf("the operators are\n");
for(i=0;i<k;i++)
{
printf("%s\n",oprt[i]);
}
printf("the number of identifiers=%d\n",c3);
printf("the identifiers are\n");
for(i=0;i<l;i++)
{
printf("%s\n",opnd[i]);
}
printf("the input expression is ");
if(c2%2==0||brackets!=0||c2==0||flag==1||c1>=c3)
printf("invalid expression\n");
else
printf("valid expression\n");
}
Dept. of CSE, SJCIT 1 2020-2021

SS LAB(18CSL66)
OUTPUT/ RESULTS

SS LAB(18CSL66)
Program: 1B
Write YACC program to evaluate arithmetic expression involving operators: +, -, *, and /.
PREREQUISITES
1. Definition of Parser.
2. Define CFG.
3. Structure of YACC.
SOURCE CODE
LEX FILE:
%{
#include "y.tab.h"
extern int yylval;
%}
%%
[0-9]+ {yylval=atoi(yytext); return dig;}
[ \t] ;
\n return 0;
. return yytext[0];
%%
YACC FILE:
%{
#include<stdio.h>
%}
%token dig
%left '+','-'
%left '*','/'
%%
S:E {printf("value=%d\n",$1);exit(0);}
| error'\n' {printf("invalid expression\n");exit(0);}
;
E:E'+'E {$$=$1+$3;}
|E'-'E {$$=$1-$3;}
|E'*'E {$$=$1*$3;}
|E'/'E {if($3==0)
{
printf("\nerror division by zero\n");
exit(0);
}
else
{ $$=$1/$3;}
}
|'('E')' {$$=$2;}
|dig {$$=$1;}
;
%%
int main()
{

SS LAB(18CSL66)
yyparse();
return 0;
}
int yyerror()
{
printf("error");
return 1;
}
OUTPUT/ RESULTS

SS LAB(18CSL66)
Program: 2
Develop, Implement and Execute a program using YACC tool to recognize all strings
ending with b preceded by n a’s using the grammar a n b (note: input n value)
PREREQUISITES
1. Write Grammar for a n b
2. Write Grammar for a nbbbn
SOURCE CODE
LEX FILE:
%{
#include "y.tab.h"
%}
%%
a {return A;}
b {return B;}
\n {return 0;}
. {return yytext[0];}
%%
YACC FILE:
%{
#include <stdio.h>
int count=0,n;
%}
%token A
%token B
%%
S : T B {
if (count<n || count>n) {
yyerror();
}
}
Aa : A {count++;}
T : Aa| T Aa;
%%
int main()
{ printf("Enter the value of n \n");
scanf("%d",&n);
printf("Enter the string\n");
yyparse();
printf("Valid string");
}
int yyerror()
{
printf("Invalid string\n");
exit(0);
}

SS LAB(18CSL66)
OUTPUT/ RESULTS

SS LAB(18CSL66)
Program: 3
Design, develop and implement YACC/C program to construct Predictive / LL(1) Parsing Table
for the grammar rules: A →aBa , B →bB | ε. Use this table to parse the sentence: abba$
PREREQUISITES
1. Rules for FIRST and FOLLOW sets.
2. Algorithm for predictive parsing table.
SOURCE CODE
#include<stdio.h>
#include<string.h>
predictiveparser()
{
char fin[10][20],st[10][20],ft[20][20],fol[20][20];
int a=0,e,i,t,b,c,n,k,l=0,j,s,m,p;
printf("Enter the no. of Nonterminals\n");
scanf("%d",&n);
printf("Enter the productions in a grammar\n");
for(i=0;i<n;i++)
scanf("%s",st[i]);
for(i=0;i<n;i++)
fol[i][0]='\0';
for(s=0;s<n;s++)
{
for(i=0;i<n;i++)
{
j=3;
l=0;
a=0;
l1: if(!((st[i][j]>64)&&(st[i][j]<91)))
{
for(m=0;m<l;m++)
{
if(ft[i][m]==st[i][j])
goto s1;
}
ft[i][l]=st[i][j];
l=l+1;
s1: j=j+1;
}
else
{
if(s>0)
{
while(st[i][j]!=st[a][0])
{
a++;
}
b=0;
while(ft[a][b]!='\0')
{

SS LAB(18CSL66)
for(m=0;m<l;m++)
{
if(ft[i][m]==ft[a][b])
goto s2;
}
ft[i][l]=ft[a][b];
l=l+1;
s2: b=b+1;
}
}
}
while(st[i][j]!='\0')
{
if(st[i][j]=='|')
{
j=j+1;
goto l1;
}
j=j+1;
}
ft[i][l]='\0';
}
}
printf("\n FIRST SET :\n");
for(i=0;i<n;i++)
printf("FIRS[%c]= %s\t\n",st[i][0],ft[i]);
fol[0][0]='$';
for(i=0;i<n;i++)
{
k=0;
j=3;
if(i==0)
l=1;
else
l=0;
k1:while((st[i][0]!=st[k][j])&&(k<n))
{
if(st[k][j]=='\0')
{
k++;
j=2;
}
j++;
}
j=j+1;
if(st[i][0]==st[k][j-1])
{
if((st[k][j]!='|')&&(st[k][j]!='\0'))
{
a=0;
if(!((st[k][j]>64)&&(st[k][j]<91)))
{
for(m=0;m<l;m++)

SS LAB(18CSL66)
{
if(fol[i][m]==st[k][j])
goto q3;
}
q3: fol[i][l]=st[k][j];
l++;
}
else
{
while(st[k][j]!=st[a][0])
{
a++;
}
p=0;
while(ft[a][p]!='\0')
{
if(ft[a][p]!='@')
{
for(m=0;m<l;m++)
{
if(fol[i][m]==ft[a][p])
goto q2;
}
fol[i][l]=ft[a][p];
l=l+1;
}
else
e=1;
q2: p++;
}
if(e==1)
{
e=0;
goto a1;
}
}
}
else
{
a1: c=0; a=0;
while(st[k][0]!=st[a][0])
{
a++;
}
while((fol[a][c]!='\0')&&(st[a][0]!=st[i][0]))
{
for(m=0;m<l;m++)
{
if(fol[i][m]==fol[a][c])
goto q1;
}
fol[i][l]=fol[a][c];
l++;

SS LAB(18CSL66)
q1:c++;
}
}
goto k1;
}
fol[i][l]='\0';
}
printf("\n FOLLOW SET :\n");
for(i=0;i<n;i++)
printf("FOLLOW[%c] = %s \n",st[i][0],fol[i]);
printf("\n");
s=0;
for(i=0;i<n;i++)
{
j=3;
while(st[i][j]!='\0')
{
if((st[i][j-1]=='|')||(j==3))
{
for(p=0;p<=2;p++)
{
fin[s][p]=st[i][p];
}
t=j;
for(p=3;((st[i][j]!='|')&&(st[i][j]!='\0'));p++)
{
fin[s][p]=st[i][j];
j++;
}
fin[s][p]='\0';
if(st[i][t]=='@')
{
b=0; a=0;
while(st[a][0]!=st[i][0])
{
a++;
}
while(fol[a][b]!='\0')
{
printf("M[ %c , %c ] = %s
n",st[i][0],fol[a][b],fin[s]);
b++;
}
}
else if(!((st[i][t]>64)&&(st[i][t]<91)))
{
n",st[i][0],st[i][t],fin[s]);
}
else
{
b=0;
a=0;

SS LAB(18CSL66)
while(st[a][0]!=st[i][3])
a++;
while(ft[a][b]!='\0')
{
n",st[i][0],ft[a][b],fin[s]);
b++;
}
}
s++;
}
if(st[i][j]=='|')
j++;
}
}
}
parseinputstring()
{
char input[20],stack[20];
char m[2][3][3]={"aBa"," "," ","@","bB"," "};
int size[2][3]={3,20,0,1,2,0};
int i,j,k,n,str1,str2;
printf("\n Enter the input string: ");
scanf("%s",input);
strcat(input,"$");
n=strlen(input);
stack[0]='$';
stack[1]='A';
stack[2] ='\0';
i=1;
j=0;
printf("\nStack Input\n");
printf("--------------------------\n");
printf("%s %s\n", stack, input);
while((stack[i]!='$')&&(input[j]!='$'))
{
if(stack[i]==input[j] && ( stack[i] && input[j] != '$'))
{
i--;
j++;
for(k=0;k<=i;k++)
printf("%c",stack[k]);
printf(" ");
for(k=j;k<n;k++)
printf("%c",input[k]);
printf(" \n ");
}
switch(stack[i])
{
case 'A': str1=0;
break;
case 'B': str1=1;
break;

SS LAB(18CSL66)
}
switch(input[j])
{
case 'a': str2=0;
break;
case 'b': str2=1;
break;
case '$': str2=2;
break;
}
if(m[str1][str2][0]=='\0')
printf("\nERROR");
else if(m[str1][str2][0]=='@')
i--;
else
{
for(k=size[str1][str2]-1;k>=0;k--)
{
stack[i]=m[str1][str2][k];
i++;
}
i--;
}
for(k=0;k<=i;k++)
printf("%c",stack[k]);
printf(" ");
for(k=j;k<=n;k++)
printf("%c",input[k]);
printf(" \n ");
}
printf("SUCCESS\n");
}
void main()
{
printf("\n1. Construction of Predictive Parsing Table LL(1)
or the grammar\n");
printf(" A -> aBa \n B -> bB | @ \n\n\n");
predictiveparser();
printf("\n\n");
printf("The predictive parsing table is:\n");
printf("------------------------------------------------------
--\n");
printf("|\tNT\t\t| a\t\t| b\t| $\t|\n");
printf("------------------------------------------------------
--\n");
printf("|\tA\t\t| A->aBa\t|\t|\t|\n");
printf("------------------------------------------------------
--\n");
printf("|\tB\t\t| B->@\t\t|B->bB\t|\t|\n");
printf("------------------------------------------------------
--\n\n\n");
printf( "2. Parsing the given input string using the above
table\n\n");

SS LAB(18CSL66)
parseinputstring();
}
OUTPUT/RESULTS

SS LAB(18CSL66)
Program: 4
Design, develop and implement YACC/C program to demonstrate Shift Reduce Parsing
technique for the grammar rules: E →E+T | T, T →T*F | F, F →(E) | id and parse the sentence:
id + id * id.
PREREQUISITES
1. Explanation of Bottom up parser
2. Shift/Reduce conflicts and Reduce/Reduce conflicts
3. Precedence orders and associativity.
SOURCE CODE
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int len,top=-1,i,j;
char str[20],stk[20];
void errfcn();
void stkfcn();
void chk();
void smch();
void main()
{
puts("Note: Do Not give spaces in between the operator in the
input\n");
puts("The given GRAMMAR is \nE->E+T|T\nT->T*F|F\nF->(E)|id\n");
puts("enter the input srting");
gets(str);
len=strlen(str);
puts("stack\t\tinput\t\taction\n");
printf("$%s\t\t%s$\n",stk,str);
for(i=0;i<len;i++)
{
if(str[i]=='i' && str[i+1]=='d')
{
str[i]=str[i+1]=' ';
top=top+1;
printf("$%sid\t\t%s$\t\tSHIFT->id\n",stk,str);
stk[top]='F';
printf("$%s\t\t%s$\t\tREDUCE to F->id\n",stk,str);
stkfcn();
smch();
i=i+1;
}
else if(str[i]=='+' || str[i]=='*')
{
top=top+1;
stk[top]=str[i];
str[i]=' ';
if(stk[top]=='+')
printf("$%s\t\t%s$\t\tSHIFT->+\n",stk,str);
else

SS LAB(18CSL66)
printf("$%s\t\t%s$\t\tSHIFT->*\n",stk,str);
if((stk[0]=='+'|| stk[0]=='*')||((stk[top]=='+'||
stk[top]=='*')&&(stk[top-1]=='+'|| stk[top-1]=='*')))
errfcn();
}
else
errfcn();
}
if(stk[top]=='+'||stk[top]=='*')
errfcn();
chk();
if(top==0)
{
if(stk[top]=='F')
{
stk[top]='T';
printf("$%s\t\t%s$\t\tREDUCE to T->F\n",stk,str);
}
if(stk[top]=='T')
{
stk[top]='E';
printf("$%s\t\t%s$\t\tREDUCE to E->T\n",stk,str);
}
}
printf("$%s\t\t%s$\t\tSUCCESS\n",stk,str);
}
void stkfcn()
{
if((top==0)&&((str[i+2]=='+')||(str[i+2]==' ')))
{
stk[top]='T';
stk[top]='E';
return;
}
else if((top==0)&&(str[i+2]=='*'))
{
stk[top]='T';
return;
}
if(stk[top-1]=='+')
{
stk[top]='T';
chk();
}
else if(stk[top-1]=='*')
chk();
}

SS LAB(18CSL66)
void chk()
{
if(stk[top-1]=='*')
{
stk[top-1]=stk[top]=' ';
top=top-2;
printf("$%s\t\t%s$\t\tREDUCE to T->T*F\n",stk,str);
if((str[i+2]=='+')&&(top==0))
{
stk[top]='E';
}
}
else if((stk[top-1]=='+' && str[i+2]=='+')||(stk[top-1]=='+' &&
str[i+2]!='*'))
{
if(top-2==0)
{
stk[top-2]='E';
}
else
{
stk[0]='E';
for(j=3;j<=top;j++)
{
stk[j]=stk[j-2];
}
}
top=top-2;
printf("$%s\t\t%s$\t\tREDUCE to E->E+T\n",stk,str);
}
}
void smch()
{
if(stk[top-1]=='+' && str[i+2]=='+')
{
if(top-2==0)
{
stk[top-2]='E';
}
else
{
stk[0]='E';
for(j=3;j<=top;j++)
{
stk[j]=stk[j-2];
}
}
top=top-2;
}

SS LAB(18CSL66)
}
void errfcn()
{
printf("ERROR:invalid argument\n");
exit(0);
}
OUTPUT/RESULTS

SS LAB(18CSL66)
Program: 5
Design, develop and implement a C/Java program to generate the machine code using
Triples for the statement A = -B * (C +D) whose intermediate code in three-address form:
T1 = -B
T2 = C + D
T3 = T1 + T2
A = T3
PREREQUISITES
1. Different forms of ICG
2. DAG Representation with example.
SOURCE CODE
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
char op[2],arg1[5],arg2[5],result[5];
void main()
{
FILE *fp1,*fp2;
fp1=fopen("input.txt","r");
fp2=fopen("output.txt","w");
while(!feof(fp1))
{
fscanf(fp1,"%s%s%s%s",result,arg1,op,arg2);
if(strcmp(op,"+")==0)
{
fprintf(fp2,"\nMOV R0,%s",arg1);
fprintf(fp2,"\nADD R0,%s",arg2);
fprintf(fp2,"\nMOV %s,R0",result);
}
if(strcmp(op,"*")==0)
{
fprintf(fp2,"\nMUL R0,%s",arg2);
}
if(strcmp(op,"-")==0)
{
fprintf(fp2,"\nSUB R0,%s",arg2);
}
if(strcmp(op,"/")==0)
fprintf(fp2,"\nDIV R0,%s",arg2);
}
if(strcmp(op,"=")==0)
{

SS LAB(18CSL66)
}
}
fclose(fp1);
fclose(fp2);
}
OUTPUT/RESULTS

SS LAB(18CSL66)
Program:6A
Write a LEX program to eliminate comment lines in a C program and copy the resulting
program into a separate file.
PREREQUISITES
1. Built-in Function of Lex

2. Explain different form of writing RE for same input.
SOURCE CODE
%{
#include<stdio.h>
int slc=0,mlc=0;
%}
%x CMNTSL CMNTML
%%
"/*" {BEGIN CMNTML; mlc++;}
<CMNTML>. ;
<CMNTML>\n ;
<CMNTML>"*/" {BEGIN 0;}
"//" {BEGIN CMNTSL; slc++;}
<CMNTSL>. ;
<CMNTSL>\n {BEGIN 0;}
%%
main(int argc, char *argv[])
{
if(argc!=3)
{
printf("usage:%s <src file> <dst file>\n",argv[0]);
return;
}
yyin=fopen(argv[1],"r");
yyout=fopen(argv[2],"w");
yylex();
printf("Number of single comment lines=%d\n",slc);
printf("Number of multi comment lines=%d\n",mlc);
}

SS LAB(18CSL66)
OUTPUT/RESULTS

SS LAB(18CSL66)
Program: 6B
Write YACC program to recognize valid identifier, operators and keywords in the given text (C
program) file.
PREREUISITES
1. Built-in function of YACC.
2. Lexer- parser communication.
SOURCE CODE
LEX FILE:
%{
#include <stdio.h>
#include "y.tab.h"
extern int yylval;
%}
%%
[ \t] ;
[+|-|*|/|=|<|>] {printf("operator is %s\n",yytext);return OP;}
[0-9]+ {yylval=atoi(yytext); printf("numbers is %d\n",yylval); return
DIGIT;}
int|char|bool|float|void|for|do|while|if|else|return {printf("keyword is
%s\n",yytext);return KEY;}
[a-zA-Z0-9]+ {printf("identifier is %s\n",yytext);return ID;}
. ;
%%
YACC FILE:
{
#include<stdio.h>
#include<stdlib.h>
int id=0, dig=0, key=0, op=0;
extern FILE *yyin;
%}
%token DIGIT ID KEY OP
%%
input:
DIGIT input { dig++; }
| ID input { id++; }
| KEY input { key++; }
| OP input {op++;}
| DIGIT { dig++; }
| ID { id++; }
| KEY { key++; }
| OP { op++;}
;
%%
int main(int argc, char *argv[])
{
if(argc!=2)
{
printf("Usage: %s <source file>",argv[0]);
return;

SS LAB(18CSL66)
}
yyin=fopen(argv[1],"r");
yyparse();
printf("numbers = %d\nKeywords = %d\nIdentifiers = %d\noperators =
%d\n",dig, key,id, op);
}
void yyerror()
{
printf("EEK, parse error! Message: ");
return;
}
OUTPUT/RESULTS
INPUT:
OUTPUT:

SS LAB(18CSL66)
Program: 7
Design, develop and implement a C/C++/Java program to simulate the working of Shortest
remaining time and Round Robin (RR) scheduling algorithms. Experiment with different
quantum sizes for RR algorithm.
ALGORITHM / PROCEDURE
1. Write algorithm for SRT
2. Write algorithm for RR
SOURCE CODE
#include<stdio.h>
#include<stdlib.h>
int no;
void roundrobin(int,int,int[],int[]);
void srtf();
main()
{
int n,tq,choice;
int bt[10], st[10], i,j,k;
for(;;)
{
printf("Enter choice\n");
printf("1.Round Robin \n2.str \n3.Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Round robin scheduling algorithm\n");
printf("Enter the number of process\n");
scanf("%d",&n);
printf("Enter burst time for sequences\n");
for(i=0;i<n;i++)
{
scanf("%d",&bt[i]);
st[i]=bt[i];
}
printf("Enter time quantum\n");
scanf("%d",&tq);
roundrobin(n,tq,st,bt);
break;
case 2: printf("\n\n-------------------Shortest remaining
time------");
srtf();
break;
case 3: exit(0);
break;
}
}
}
void roundrobin(int n, int tq, int st[], int bt[])

{

SS LAB(18CSL66)
int time=0;
int tat[10],wt[10],i,count=0,swt=0,stat=0,temp1,sq=0,j,k;
float awt=0.0, atat=0.0;
while(1)
{
for(i=0,count=0;i<n;i++)
{
temp1=tq;
if(st[i]==0)
{
count++;
continue;
}
if (st[i]>tq)
st[i]=st[i]-tq;
else if(st[i]>=0)
{
temp1=st[i];
st[i]=0;
}
sq=sq+temp1;
tat[i]=sq;
}
if(n==count)
break;
}
for(i=0;i<n;i++)
{
wt[i]=tat[i]-bt[i];
swt=swt+wt[i];
stat=stat+tat[i];
}
awt=(float)swt/n;
atat=(float)stat/n;
printf("Process no burst time waiting time turnaround time\n");
for(i=0;i<n;i++)
printf("%d \t\t %d \t\t %d \t\t %d
\t\t\n",i+1,bt[i],wt[i],tat[i]);
printf("Average waiting time is%f\n avg turnaround time is
%f\n",awt,atat);
void srtf()
{
int
n,j=0,st[10],bt[10],rt[10],remain=0,smallest,time=0,i,endtime,swt=0,stat=0
;
printf("Enter the no. of process:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the arrivaltime for p[%d]:",i+1);

SS LAB(18CSL66)
scanf("%d",&st[i]);
printf("Enter the burst time for p[%d]:",i+1);
scanf("%d",&bt[i]);
rt[i]=bt[i];
}
rt[100]=999;
printf("Process\t|writing time\t|turnarround time\n");
for(time=0;remain!=n;time++)
{
smallest=100;
for(i=0;i<n;i++)
{
if(st[i]<=time && rt[i]<rt[smallest] && rt[i]>0)
{
smallest=i;
}
}
rt[smallest]--;
if(rt[smallest]==0)
{
remain++;
endtime=time+1;
j=smallest;
printf("p[%d]\t|\t%d\t|\t%d\n",smallest+1,endtime-bt[j]-
st[j],endtime-st[j]);
swt +=endtime-bt[j]-st[j];
stat +=endtime-st[j];
}
}
float awt=0.0,atat=0.0;
awt=(float)swt/n;
atat=(float)stat/n;
printf("Average waiting time:%f\n",awt);
printf("Average turnarround time:%f\n",atat);
}
OUTPUT/RESULT
Enter choice
1.Round Robin
2.str
3.Exit
1
Round robin scheduling algorithm
Enter the number of process
4
Enter burst time for sequences
4252
Enter time quantum

SS LAB(18CSL66)
15
process no burst time waiting time turnaround time
1 4 0 4
2 2 4 6
3 5 6 11
4 2 11 13
Average waiting time is5.250000
Average turnaround time is 8.500000
Enter choice
1.Round Robin
2.str
3.Exit
2
-------------------Shortest remaining time----------------------

Enter the no. of process:5
Enter the arrivaltime for p[1]:3
Enter the burst time for p[1]:5
process|writing time |turnarround time

p[2] | 0 | 4
p[1] | 1 | 6
p[4] | 2 | 4
p[3] | 6 | 10
p[5] | 10 | 14
Average waiting time:3.800000
Average turnarround time:7.600000
Enter choice
1.Round Robin
2.str
3.Exit

SS LAB(18CSL66)
Program: 8
Design, develop and implement a C/C++/Java program to implement Banker’s algorithm.
Assume suitable input required to demonstrate the results.
ALGORITHM/PROCEDURE
1. Algorithm for Banker’s
SOURCE CODE
#include<stdio.h>
struct process
{
int all[6],max[6],need[6],finished,request[6];
}p[10];
int avail[6],sseq[10],ss=0,check1=0,check2=0,n,pid,nor,nori,work[6];
int main()
{
int safeseq(void);
int ch,k,i=0,j=0,pid,ch1;
int violationcheck=0,waitcheck=0;
do
{
printf("\n1.Input\n2.New Request\n3.Safe State or
Not\n4.Print\n5.Exit\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the number of processes:");
scanf("%d",&n);
printf("\nEnter the number of resources:");
scanf("%d",&nor);
printf("\nEnter the available resources:");
for(j=0;j<n;j++)
{
for(k=0;k<nor;k++)
{
if(j==0)
{
printf("\nFor Resource Type %d:",k);
scanf("%d",&avail[k]);
}
p[j].max[k]=0;
p[j].all[k]=0;
p[j].need[k]=0;
p[j].finished=0;
p[j].request[k]=0;
}
}
for(i=0;i<n;i++)
{
printf("\nEnter Max and Allocated Resources for P %d
:",i);

SS LAB(18CSL66)
for(j=0;j<nor;j++)
{
printf("\nEnter the Max of Resources %d:",j);
scanf("%d",&p[i].max[j]);
printf("\nAllocation of Resources %d:",j);
scanf("%d",&p[i].all[j]);
if(p[i].all[j]>p[i].max[j])
{
printf("\nAllocation should be less than or equal
to Max\n");
j--;
}
else
p[i].need[j]=p[i].max[j]-p[i].all[j];
}
}
break;
case 2:
violationcheck=0;
waitcheck=0;
printf("\nRequesting Process ID:\n");
scanf("%d",&pid);
for(j=0;j<nor;j++)
{
printf("\nNumber of Request for Resource %d:",j);
scanf("%d",&p[pid].request[j]);
if(p[pid].request[j]>p[pid].need[j])
violationcheck=1;
if(p[pid].request[j]>avail[j])
waitcheck=1;
}
if(violationcheck==1)
printf("\nThe Process Exceeds its Max needs:
Terminated\n");
else if(waitcheck==1)
printf("\nLack of Resources: Process State - Wait\n");
else
{
for(j=0;j<nor;j++)
{
avail[j]=avail[j]-p[pid].request[j];
p[pid].all[j]=p[pid].all[j]+p[pid].request[j];
p[pid].need[j]=p[pid].need[j]-p[pid].request[j];
}
ch1=safeseq();
if(ch1==0)
{
for(j=0;j<nor;j++)
{
avail[j]=avail[j]+p[pid].request[j];
p[pid].all[j]=p[pid].all[j]-p[pid].request[j];
p[pid].need[j]=p[pid].need[j]+p[pid].request[j];

SS LAB(18CSL66)
}
}
else if(ch1==1)
printf("\nRequest committed.\n");
}
break;
case 3:
if(safeseq()==1)
printf("\nThe System is in Safe State\n");
else
printf("\nThe System is not in Safe State\n");
break;
case 4:
printf("\nNumber of Process:%d\n",n);
printf("\nNumber of Resources:%d\n",nor);
printf("\nPid\tMax\tAllocated\tNeed\n");
for(i=0;i<n;i++)
{
printf(" P%d :",i);
for(j=0;j<nor;j++)
printf(" %d ",p[i].max[j]);
printf("\t");
for(j=0;j<nor;j++)
printf(" %d ",p[i].all[j]);
printf("\t");
for(j=0;j<nor;j++)
printf(" %d ",p[i].need[j]);
printf("\n");
}
printf("\nAvailable:\n");
for(i=0;i<nor;i++)
printf(" %d ",avail[i]);
break;
case 5: break;
}
}while(ch!=5);
return 0;
}
int safeseq()
{
int tj,tk,i,j,k;
ss=0;
for(j=0;j<nor;j++)
work[j]=avail[j];
for(j=0;j<n;j++)
p[j].finished=0;
for(tk=0;tk<nor;tk++)
{
for(j=0;j<n;j++)
{
if(p[j].finished==0)

SS LAB(18CSL66)
{
check1=0;
for(k=0;k<nor;k++)
if(p[j].need[k]<=work[k])
check1++;
if(check1==nor)
{
for(k=0;k<nor;k++)
{
work[k]=work[k]+p[j].all[k];
p[j].finished=1;
}
sseq[ss]=j;
ss++;
}
}
}
}
check2=0;
for(i=0;i<n;i++)
if(p[i].finished==1)
check2++;
printf("\n");
if(check2>=n)
{
for(tj=0;tj<n;tj++)
printf("p%d",sseq[tj]);
return 1;
}
else
printf("\nThe System is not in Safe State\n");
return 0;
}
OUTPUT/RESULTS
$ ./a.out
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:1
Enter the number of processes:5
Enter the number of resources:3
Enter the available resources:

SS LAB(18CSL66)
For Resource Type 0:3

Enter Max and Allocated Resources for P 0 :

Enter the Max of Resources 0:7
Allocation of Resources 0:0












SS LAB(18CSL66)



1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:3
p1p3p4p0p2
The System is in Safe State
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:4

Number of Process:5
Number of Resources:3
Pid Max Allocated Need

P0 : 7 5 3 0 1 0 7 4 3
P1 : 3 2 2 2 0 0 1 2 2
P2 : 9 0 2 3 0 2 6 0 0
P3 : 2 2 2 2 1 1 0 1 1
P4 : 4 3 3 0 0 2 4 3 1
Available:
3 3 2
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:2

SS LAB(18CSL66)
Requesting Process ID:

1
Number of Request for Resource 0:1
p1p3p4p0p2
Request committed.
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:4

Number of Process:5

P0 : 7 5 3 0 1 0 7 4 3
P1 : 3 2 2 3 0 2 0 2 0
P2 : 9 0 2 3 0 2 6 0 0
P3 : 2 2 2 2 1 1 0 1 1
P4 : 4 3 3 0 0 2 4 3 1
Available:
2 3 0
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:3

p1p3p4p0p2
The System is in Safe State
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:2

SS LAB(18CSL66)

Lack of Resources: Process State - Wait
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:2

0

The System is not in Safe State
1.Input
2.New Request
3.Safe State or Not
4.Print
5.Exit
Enter your choice:4

Number of Process:5

P0 : 7 5 3 0 1 0 7 0 3
P1 : 3 2 2 3 0 2 0 2 0
P2 : 9 0 2 3 0 2 6 0 0
P3 : 2 2 2 2 1 1 0 1 1
P4 : 4 3 3 0 0 2 4 3 1
Available:
2 3 0
1.Input
2.New Request
SS LAB(18CSL66)
3.Safe State or Not

4.Print
5.Exit
Enter your choice:5

SS LAB(18CSL66)
Program: 9
Design, develop and implement a C/C++/Java program to implement page replacement
algorithms LRU and FIFO. Assume suitable input required to demonstrate the results.
ALGORITHM/PROCEDURE
1. Algorithm for LRU.
2. Algorithm for FIFO
SOURCE CODE
#include<stdio.h>
#include<stdlib.h>
void FIFO(char [ ],char [ ],int,int);
void lru(char [ ],char [ ],int,int);
void opt(char [ ],char [ ],int,int);
int main()
{
int ch,YN=1,i,l,f;
char F[10],s[25];
printf("\n\n\tEnter the no of empty frames: ");
scanf("%d",&f);
printf("\n\n\tEnter the length of the string: ");
scanf("%d",&l);
printf("\n\n\tEnter the string: ");
scanf("%s",s);
for(i=0;i<f;i++)
F[i]=-1;
do
{
printf("\n\n\t*********** MENU ***********");
printf("\n\n\t1:FIFO\n\n\t2:LRU \n\n\t4:EXIT");
printf("\n\n\tEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
for(i=0;i<f;i++)
{
F[i]=-1;
}
FIFO(s,F,l,f);
break;
case 2:
for(i=0;i<f;i++)
{
F[i]=-1;
}
lru(s,F,l,f);
break;
case 4:
exit(0);
}
printf("\n\n\tDo u want to continue IF YES PRESS 1\n\n\tIF NO
PRESS 0 : ");

SS LAB(18CSL66)
scanf("%d",&YN);
}
while(YN==1);return(0);
}
//FIFO
void FIFO(char s[],char F[],int l,int f)
{
int i,j=0,k,flag=0,cnt=0;
printf("\n\tPAGE\t FRAMES\t FAULTS");
for(i=0;i<l;i++)
{
for(k=0;k<f;k++)
{
I f(F[k]==s[i])
flag=1;
}
if(flag==0)
{
printf("\n\t%c\t",s[i]);
F[j]=s[i];
j++;
for(k=0;k<f;k++)
{
printf(" %c",F[k]);
}
printf("\tPage-fault%d",cnt);
cnt++;
}
else
{
flag=0;
for(k=0;k<f;k++)
{
printf(" %c",F[k]);
}
printf("\tNo page-fault");
}
if(j==f)
j=0;
}
}
//LRU
void lru(char s[],char F[],int l,int f)
{
int i,j=0,k,m,flag=0,cnt=0,top=0;
printf("\n\tPAGE\t FRAMES\t FAULTS");
for(i=0;i<l;i++)
{
for(k=0;k<f;k++)
{
if(F[k]==s[i])
{

SS LAB(18CSL66)
flag=1;
break;
}
}
if(j!=f && flag!=1)
{
F[top]=s[i];
j++;
if(j!=f)
top++;
}
else
{
if(flag!=1)
{
for(k=0;k<top;k++)
{
F[k]=F[k+1];
}
F[top]=s[i];
}
if(flag==1)
{
for(m=k;m<top;m++)
{
F[m]=F[m+1];
}
F[top]=s[i];
}
}
for(k=0;k<f;k++)
{
printf(" %c",F[k]);
}
if(flag==0)
{
printf("\tPage-fault%d",cnt);
cnt++;
}
else
printf("\tNo page fault");
flag=0;
}
}

SS LAB(18CSL66)
OUTPUT/RESULTS
Enter the no of empty frames: 3
Enter the length of the string: 20
Enter the string: 70120304230321201701
*********** MENU ***********
1:FIFO
2:LRU
4:EXIT
Enter your choice: 1
PAGE FRAMES FAULTS

7 7 Page-fault0
0 7 0 Page-fault1
1 7 0 1 Page-fault2
2 2 0 1 Page-fault3
0 2 0 1 No page-fault
3 2 3 1 Page-fault4
0 2 3 0 Page-fault5
4 4 3 0 Page-fault6
2 4 2 0 Page-fault7
3 4 2 3 Page-fault8
0 0 2 3 Page-fault9
1 0 1 3 Page-fault10
Do u want to continue IF YES PRESS 1
IF NO PRESS 0 : 1
*********** MENU ***********
1:FIFO
2:LRU
4:EXIT

SS LAB(18CSL66)
Enter your choice: 2
PAGE FRAMES FAULTS

7 7 Page-fault0
0 7 0 Page-fault1
1 7 0 1 Page-fault2
2 0 1 2 Page-fault3
0 1 2 0 No page fault
3 2 0 3 Page-fault4
4 3 0 4 Page-fault5
2 0 4 2 Page-fault6
3 4 2 3 Page-fault7
0 2 3 0 Page-fault8
1 3 2 1 Page-fault9
Do u want to continue IF YES PRESS 1
IF NO PRESS 0 :

SS LAB(18CSL66)
VIVA QUESTIONS
1. Define system software.

System software is computer software designed to operate the computer hardware and to provide a
platform for running application software. Eg: operating system, assembler, and loader.
2. What is an Assembler?
Assembler for an assembly language, a computer program to translate between lower-level
representations of computer programs.
3. Explain lex and yacc tools

Lex: - scanner that can identify those tokens
Yacc: - parser.yacc takes a concise description of a grammar and produces a C routine that can parse
that grammar.
4. Explain yyleng?
Yyleng-contains the length of the string our lexer recognizes.
5. What is a Parser?
A Parser for a Grammar is a program which takes in the Language string as it's input and produces
either a corresponding Parse tree or an Error.
6. What is the Syntax of a Language?

The Rules which tells whether a string is a valid Program or not are called the Syntax.
7. What is the Semantics of a Language?

The Rules which gives meaning to programs are called the Semantics of a Language.
8. What are tokens?

When a string representing a program is broken into sequence of substrings, such that each substring
represents a constant, identifier, operator, keyword etc of the language, these substrings are called the
tokens of the Language.
9. What is the Lexical Analysis?

The Function of a lexical Analyzer is to read the input stream representing the Source program, one
character at a time and to translate it into valid tokens.
10. How can we represent a token in a language?

The Tokens in a Language are represented by a set of Regular Expressions. A regular expression
specifies a set of strings to be matched. It contains text characters and operator characters. The
Advantage of using regular expression is that a recognizer can be automatically generated.
11. How are the tokens recognized?

The tokens which are represented by an Regular Expressions are recognized in an input string by
means of a state transition Diagram and Finite Automata.

SS LAB(18CSL66)
12. Are Lexical Analysis and Parsing two different Passes?

These two can form two different passes of a Parser. The Lexical analysis can store all the
recognized tokens in an intermediate file and give it to the Parser as an input. However it is more
convenient to have the lexical Analyzer as a co routine or a subroutine which the Parser calls
whenever it requires a token.
13. How do we write the Regular Expressions?
| OR (alternation)
() Group of
Subexpression
* 0 or more
Occurrences
? 0 or 1 Occurrence
+ 1 or more
Occurrences
{n,m} n-m Occurrences
14. What are the Advantages of using Context-Free grammars?

It is precise and easy to understand.
It is easier to determine syntactic ambiguities and conflicts in the grammar.
15. If Context-free grammars can represent every regular expression, why do one needs
R.E at all?
Regular Expression are Simpler than Context-free grammars.
It is easier to construct a recognizer for R.E than Context-Free grammar.
Breaking the Syntactic structure into Lexical & non-Lexical parts provide better front end for the
Parser.
R.E are most powerful in describing the lexical constructs like identifiers, keywords etc while
Context-free grammars in representing the nested or block structures of the Language.
16. What are the Parse Trees?

Parse trees are the Graphical representation of the grammar which filters out the choice for
replacement order of the Production rules.
17. What are Terminals and non-Terminals in a grammar?

Terminals:- All the basic symbols or tokens of which the language is composed of are called
Terminals. In a Parse Tree the Leafs represents the Terminal Symbol.
Non-Terminals:- These are syntactic variables in the grammar which represents a set of strings the
grammar is composed of. In a Parse tree all the inner nodes represents the Non-Terminal symbols.
18. What are Ambiguous Grammars?

A Grammar that produces more than one Parse Tree for the same sentences or the Production rules in
a grammar is said to be ambiguous.
19. What is bottom up Parsing?

SS LAB(18CSL66)
The Parsing method is which the Parse tree is constructed from the input language string beginning
from the leaves and going up to the root node.
Bottom-Up parsing is also called shift-reduce parsing due to its implementation. The YACC supports
shift-reduce parsing.
20. What is the need of Operator precedence?

The shift reduce Parsing has a basic limitation. Grammars which can represent a left-sentential parse
tree as well as right-sentential parse tree cannot be handled by shift reduce parsing. Such a grammar
ought to have two non-terminals in the production rule. So the Terminal sandwiched between these
two non-terminals must have some associability and precedence. This will help the parser to
understand which non-terminal would be expanded first.
21. What is exit status command?

Exit 0- return success, command executed successfully.
Exit 1 – return failure.
22. Define API’s

An application programming interface (API) is a source code based specification intended to be used
as an interface by software components to communicate with each other.

Ss Lab Manual

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Ss Lab Manual

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ss Lab Manual

Uploaded by

Copyright:

Available Formats

S J C INSTITUTE OF TECHNOLOGY

Department of Computer Science and Engineering

System Software Laboratory Manual

Department of Computer Science and Engineering

Imparting Center of Excellence in state-of-Art Infrastructure to make competent

PROGRAM EDUCATIONAL OBJECTIVES

Department of Computer Science and Engineering

PROGRAM SPECIFIC OUTCOMES (PSOs)

Department of Computer Science and Engineering

Course Learning Objectives

This course will help students to achieve the following objectives:

At the end of the course students should be able to:

1. Implement and demonstrate the scanning process using Lex tool.

Apply the knowledge of lexical analysis to define different tokens of a particular

2 Develop, Implement and Execute a program using YACC tool to

1.1Steps in writing LEX Program:

1.2 Structure of LEX source program:

1.3 Regular Expressions

Examples of regular expressions

Examples of token declarations

2.1 Steps in writing YACC Program:

%noassoc Specifies that there is no associatively of a terminal symbol.

%left Specifies the left associatively of a Terminal Symbol

%right Specifies the right associatively of a Terminal Symbol.

Names representing tokens must be declared as follows in the declaration sections:

%token name1 name2…

Folder/Directory Commands and Options

File Listing Commands and Options

File Manipulation Commands and Options

An Operating System is a program that manages the Computer hardware. It controls

A Process is a program in execution. As a process executes, it changes state

 New: The process is being created

A Multi-programmed system can have many processes running simultaneously

4.1 Scheduling Algorithms

  Waiting time: The sum of periods spent waiting in ready queue. 

The different scheduling algorithms are

  SJF: Shortest Job First Scheduling

  SRTF: Shortest Remaining Time First Scheduling

  Round Robin Scheduling

  Multilevel Queue Scheduling

Deadlock can be handled in one of these ways,

Round Robin (RR) scheduling algorithm:

Round-robin (RR) is one of the algorithms employed by process and

The phases of a compiler:

Syntax analyzers follow production rules defined by means of context-free grammar.

• Recursive descent parsing: It is a common form of top-down parsing. It is called

• Backtracking: It means, if one derivation of a production fails, the syntax analyzer

Dept. of CSE, SJCIT 1 2020-2021

Dept. of CSE, SJCIT 2 2020-2021

Dept. of CSE, SJCIT 3 2020-2021

Dept. of CSE, SJCIT 4 2020-2021

Dept. of CSE, SJCIT 5 2020-2021

Dept. of CSE, SJCIT 6 2020-2021

Dept. of CSE, SJCIT 7 2020-2021

Dept. of CSE, SJCIT 8 2020-2021

Dept. of CSE, SJCIT 9 2020-2021

Dept. of CSE, SJCIT 10 2020-2021

Dept. of CSE, SJCIT 11 2020-2021

Dept. of CSE, SJCIT 12 2020-2021

* MENU *