<<BACK
Q10: What is
parsing? Explain any three parsing techniques.?
Ans: Parsing
is the process of analyzing a text made of a sequence of tokens to determine its
grammatical structure with respect to a given formal grammar. Parsing is also known
as syntactic analysis and parser is used for analyzing a text. The task of parser
is essentially to determine if and how the input can be derived from the start symbol
of the grammar.
Following are
three parsing techniques:
Top-down
parsing - Top-down parsing can be viewed as an attempt to find left-most derivations of
an input-stream by searching for parse trees using a top-down expansion of
the given formal grammar rules. Tokens are consumed from left to right.Inclusive
choice is used to accommodate ambiguity by expanding all alternative righthand-sides of
grammar rules.
Bottom-up
parsing - A parser can start with the input and attempt to rewrite it to the start symbol.
Intuitively, the parser attempts to locate the most basic elements, then the elements
containing these, and so on. LR parsers are examples of bottom-up parsers.
Another term used for this type of parser is Shift-Reduce parsing.
Recursive
descent parsing- It is a top down parsing without backtracking. This parsing technique uses
a set of recursive procedures to perform parsing. Salient advantages of recursive
descent parsing are its simplicity and generality. It can be implemented in any language
supporting recursive procedures.
Q11: Explain
any three policies for process scheduling that uses resource consumption information.
What is response ratio?
Ans: Three policies
for process scheduling are described below in brief:
1.
First-come First-served (FCFS) (FIFO)
– Jobs are
scheduled in order of arrival
–
Non-preemptive
• Problem:
– Average
waiting time can be large if small jobs wait behind long ones
– May lead to
poor overlap of I/O and CPU and convoy effects
2.
Shortest Job First (SJF)
– Choose the
job with the shortest next CPU burst
– Provably
optimal for minimizing average waiting time
• Problem:
– Impossible
to know the length of the next CPU burst
3.
Round Robin(RR)
– Often used
for timesharing
– Ready queue
is treated as a circular queue (FIFO)
– Each process
is given a time slice called a quantum
– It is run
for the quantum or until it blocks
– RR allocates
the CPU uniformly (fairly) across all participants. If average queue length
is n, each
participant gets 1/n
– As the time
quantum grows, RR becomes FCFS
– Smaller
quanta are generally desirable, because they improve response time
• Problem:
– Context
switch overhead of frequent context switch
Q12: Macros Vs Subroutines
Ans: (i) Macros are
preprocessor directives i.e. it is processed before the source program is
passed to the compiler.
Subroutines
are blocks of codes with a specific task, to be performed and are directly
passed to compiler.
(ii) In a Macros call the preprocessor replaces the macro template with its macro expansion, in
a literal way.
(iii) Macros increases the program size.
Q.13: Write short notes on: (i) YACC (ii) Debug monitors
Ans: (i)YACC
stands for “Yet another Compiler-Compiler” : Computer program
input generally has
some structure; in fact, every computer program that does input can be thought of as
defining an “input language” which it accepts. An input language may be as complex as
a programming language, or as simple as a sequence of numbers. Unfortunately,
usual input facilities are limited, difficult to use, and often are lax about
checking their
inputs for validity.
YACC provides
a general tool for describing the input to a computer program. The YACC user
specifies the structures of his input, together with code to be invoked as each such
structure is recognized. YACC turns such a specification into a subroutine that handles
the input process; frequently, it is convenient and appropriate to have most of the flow of
control in the user's application handled by this subroutine. The output from YACC is
LALR parser for the input programming laughing
(ii)Debug
monitors provide debugging support for a program. A
debug monitor executes the
program being debugged under its own control thereby providing execution
efficiency during debugging. There are debug monitors that are language independent
and can handle programs written in many languages. For example-DEC-
Debug
monitor provide the following facilities for dynamic debugging:
1. Setting
breakpoints in the program
2. Initiating
a debug conversation when control reaches a breakpoint.
3. Displaying
values of variables
4. Assigning
new values to variables.
5. Testing
user defined assertions and predicates involving program variables.
Q14: Define
deadlock? Explain the necessary conditions for deadlock to occur.
Ans: Deadlock
is a situation, in which processes never finish executing and
system resources are
tied up, preventing other jobs from starting. A process requests resources; if
the resources are not available at that time, the process enters a wait state. Waiting
processes may never again change state, because the resources they have requested
are held by other waiting processes, thereby causing deadlock.Necessary
conditions for deadlock to occur are:
i. Mutual
exclusion: At least one resource must be held in a
nonsharable mode; that is, only
one process at a time can use the resource. If another process requests that resource,
the requesting process must be delayed until the resource has been released.
ii. Hold
and wait: A process must be holding at least one
resource and waiting to acquire
additional resources that are currently being held by other processes.
iii. No
pre-emption: Resources cannot be pre-empted; that is, a
resource can be released only
voluntarily by the process holding it, after the process holding it has completed its
task.
iv. Circular
wait: A set{P0, P1,……, Pn) of waiting processes
must exist such that P0 is
waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2,
……., Pn-1 is waiting for a resource that is held by Pn and Pn is waiting for a resource
that is held by P0. All four
conditions must hold simultaneously for a deadlock to occur and conditions are not
completely independent. For example, the circular-wait implies the hold-and wait condition.
