Important Descriptive Question part2

<<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.