Sikkim Manipal university MCA Third Sem june-2011 Solved Assignment

July-2011

Master of Computer Application (MCA)

     Sikkim Manipal University Distance Education 

NAME: Vivek Kumar Rai

Assignment of Third semester July-2011

Fully Solved

ROLL No:-

website:- http://vivekraicdac.blogspot.in/

email-id vivek.k.ray@gmail.com

vivekray@cdac.in

ph:- 8880583241

February 2011

Master of Computer Application (MCA) – Semester 3

MC0071 – Software Engineering Assignment Set – 1

1.Explain the following concepts with respect to Software Reliability.

A) Software Reliability Metrics:

B) Programming for Reliability:

Answer:

A) Software Reliability Metrics:

Software Reliability is the application of statistical techniques to data collected during system development and operation to specify, predict, estimate, and assess the reliability of software-based systems. "Software Reliability Engineering (SRE) is a standard, proven best practice that makes testing more reliable, faster, and cheaper. It can be applied to any system using software and to frequently-used members of software component libraries."

B) Programming for Reliability:

In recent years, static analysis has become a viable technique for finding bugs in large software systems. Modern static analyzers have been used to find hundreds of bugs in the Linux kernel and many large commercial applications without the false alarm rate seen in previous generation tools such as lint. Static analyzers find bugs in source code without the need for execution or test cases. They parse the source code and then perform dataflow analysis to find potential error cases on all possible paths through each function. No technique is a silver bullet, and static analysis is no exception. Static analysis is usually only practical for certain categories of errors and cannot replace functional testing. However, compared with traditional QA and testing techniques, static analysis provides a way to achieve much higher coverage of corner cases in the code. Compared with manual code review, static analysis is impartial, thorough, and cheap to perform regularly.

2. Suggest six reasons why software reliability is important. Using an example, explain the difficulties of describing what software reliability means.

Answer:

Reliable software must include extra, often redundant, code to perform the necessary checking for exceptional conditions. This reduces program execution speed and increases the amount of store required by the program. Reliability should always take precedence over efficiency for the following reasons:

a) Computers are now cheap and fast: There is little need to maximize equipment usage. Paradoxically, however, faster equipment leads to increasing expectations on the part of the user so efficiency considerations cannot be completely ignored.

b) Unreliable software is liable to be discarded by users: If a company attains a reputation for unreliability because of single unreliable product, it is likely to affect future sales of all of that company’s products.

c) System failure costs may be enormous: For some applications, such a reactor control system or an aircraft navigation system, the cost of system failure is orders of magnitude greateAnswer:r than the cost of the control system.

500. Unreliable systems are difficult to improve: It is usually possible to tune an inefficient system because most execution time is spent in small program sections. An unreliable system is more difficult to improve as unreliability tends to be distributed throughout the system.

e) Inefficiency is predictable: Programs take a long time to execute and users can adjust their work to take this into account. Unreliability, by contrast, usually surprises the user. Software that is unreliable can have hidden errors which can violate system and user data without warning and whose consequences are not immediately obvious. For example, a fault in a CAD program used to design aircraft might not be discovered until several plane crashers occurs.

f) Unreliable systems may cause information loss: Information is very expensive to collect and maintains; it may sometimes be worth more than the computer system on which it is processed. A great deal of effort and money is spent duplicating valuable data to guard against data corruption caused by unreliable software.

Answer: The software process used to develop that product influences the reliability of the software product. A repeatable process, which is oriented towards defect avoidance, is likely to develop a reliable system. However, there is not a simple relationship between product and process reliability.

Users often complain that systems are unreliable. This may be due to poor software engineering. However, a common cause of perceived unreliability is incomplete specifications. The system performs as specified but the specifications do not set out how the software should behave in exceptional situations. As professionals, software engineers must do their best to produce reliable systems, which take meaningful and useful actions in such situations.

The Reliability of a software system is a measure of how well users think it provides the services that they require. Reliability is usually defined as the probability of failure-free operation for a specified time in a specified environment for a specific purpose. Say it is claimed that software installed on an aircraft will be 99.99% reliable during an average flight of five hours. This means that a software failure of some kind will probably occur in one flight out of 10000.

A formal definition of reliability may not equate to user’s experience of the software. The difficulty in relating such a figure to user’s experience arises because it does not take the nature of the failure into account. A user does not consider all services to be of equal importance. A system might be thought of as unreliable if it ever failed to provide some critical service. For example, say a system was used to control braking on an aircraft but failed to work under a single set of very rare conditions. If an aircraft crashed because of these failure conditions, pilots of similar aircraft would regard the software as unreliable.

There is a general requirement for more reliable systems in all application domains. Customers expect their software to operate without failure to be available when it is required. Improved programming techniques, better programming languages and better quality management have led to very significant improvements in reliability for most software. However, for some systems, such as those which control unattended machinery, these ‘normal’ techniques may not be enough to achieve the level of reliability required, In these cases special programming techniques may be necessary to achieve the required reliability. Some of these techniques are discussed in this chapter.

The concept on Software reuse has been included in the following section. Because improved reliability is one of the benefits of reuse. Software components are not just used in one system but are tried and tested in a variety of different environments. Design and implementation forms are discovered and eliminated so the reusable components contain few errors.

Software reliability: Software reliability is a function of the number of failures experienced by a particular user of that software. A software failure occurs when the software is executing. It is a situation in which the software does not deliver the service expected by the user. Software failures are not the same as software faults although these terms are often used interchangeably.

Formal specifications and proof do not guarantee that the software will be reliable in practical use. The reasons for this are:

a) The specifications may not reflect the real requirements of system users : Many failures experienced by users were a consequence of specification errors and omissions, which could not be detected by formal system specification. It may even be the case that the opaqueness of formal notations makes it more difficult for users to establish whether or not a system meets their real requirements.

b) The proof may contain errors Program proofs are large and complex so, like large and complex programs, they usually contain errors.

c) The Proof may assume a usage pattern, which is incorredepends on the endpoint coordinates only and can be precomputed, and the ideal y for successive integer values of x can be computed starting from y0 and repeatedly adding the slope.ct. If the system is not used as anticipated, the proof may be invalid.

If it is possible to measure if a system is 100% reliable as this would require an amount of time equal to the lifetime of the system. However, as reliability requirements increase, system costs usually rise exponentially. This is mostly due to the need of redundant hardware and a vast increase in testing costs to check that the required reliability has been achieved. As discussed some specifications, which call for, ultra-reliable systems are unrealistic. The number of tests required to validate these specifications cannot be carried out in a reasonable time.

3. What are the essential skills and traits necessary for effective project managers in successfully handling projects?

Answer:

A successful project manager knows how to bring together the definition and control elements and operate them efficiently. That means you will need to apply the leadership skills you already apply in running a department and practice the organizational abilities you need to constantly look to the future. In other words, if you are a qualified department manager, you already possess the skills and attributes for succeeding as a project manager. The criteria by which you will be selected will be similar. Chances are, the project you are assigned will have a direct relationship to the skills you need just to do your job.

For example:

Organizational and leadership experience:- An executive seeking a qualified project manager usually seeks someone who has already demonstrated the ability to organize work and to lead others. He or she assumes that you will succeed in a complicated long-term project primarily because you have already demonstrated the required skills and experience.

Contact with needed resources:- For projects that involve a lot of coordination between departments, divisions, or subsidiaries, top management will look for a project manager who already communicates outside of a single department. If you have the contacts required for a project, it will naturally be assumed that you are suited to run a project across departmental lines.

Ability to coordinate a diverse resource pool:- By itself, contact outside of your department may not be enough. You must also be able to work with a variety of people and departments, even when their backgrounds and disciplines are dissimilar. For example, as a capable project manager, you must be able to delegate and monitor work not only in areas familiar to your own department but in areas that are alien to your background.

Communication and procedural skills:- An effective project manager will be able to convey and receive information to and from a number of team members, even when particular points of view are different from his own. For example, a strictly administrative manager should understand the priorities of a sales department, or a customer service manager may need to understand what motivates a production crew.

Ability to delegate and monitor work:- Project managers need to delegate the work that will be performed by each team member, and to monitor that work to stay on schedule and within budget. A contractor who builds a house has to understand the processes involved for work done by each subcontractor, even if the work is highly specialized. The same is true for every project manager. It is not enough merely to assign someone else a task, complete with a schedule and a budget. Delegation and monitoring are effective only if you are also able to supervise and assess progress.

Dependability:- Your dependability can be tested only in one way: by being given responsibility and the chance to come through. Once you gain the reputation as a manager who can and do respond as expected, you are ready to take on a project. These project management qualifications read like a list of evaluation points for every department manager. If you think of the process of running your department as a project of its own, then you already understand what it is like to organize a project²the difference, of course, being that the project takes place in a finite time period, whereas your departmental tasks are ongoing. Thus, every successful manager should be ready to tackle a project, provided it is related to his or her skills, resources, and experience.

4. Which are the four phases of development according to Rational Unified Process?

Answer:  The software lifecycle is broken into cycles, each cycle working on a new generation of the product. T he Rational Unified Process divides one development cycle in four consecutive phases.

I.) Inception phase:  During the inception phase, you establish the business case for the system and delimit the project scope. Toaccomplish this you must identify all external entities with which the system will interact (actors) anddefine the nature of this interaction at a high-level. This involves identifying all use cases and describing a few significant ones. The business case includes success criteria, risk assessment, and estimate of the resources needed, and a phase plan showing dates of major milestones.

II.) Elaboration phase: The purpose of the elaboration phase is to analyze the problem domain, establish a sound architectural foundation,develop the project plan, and eliminate the highest risk elements of the project. To accomplish these objectives, you must have the “mile wide and inch deep” view of the system. Architectural decisions have to be made with an understanding of the whole system: its scope, major functionality and nonfunctional requirements such as performance requirements.

III.) Construction phase: During the construction phase, all remaining components and application features are developed and integrated into the product, and all features are thoroughly tested. The construction phase is, in one sense, a manufacturing process where emphasis is placed on managing resources and controlling operations to optimize costs, schedules, and quality. In this sense, the management mindset undergoes a transition from the development of intellectual property during inception and elaboration, to the development of deployable products during construction and transition.

Transition phase: The purpose of the transition phase is to transition the software product to the user community. Once the product has been given to the end user, issues usually arise that require you to develop new releases, correct some problems, or finish the features that were postponed.

February 2011

Master of Computer Application (MCA) – Semester 3

MC0072 –Computer Graphics

Assignment Set – 1

2. What is DDA line drawing algorithm explain it with the suitable example discuss the merit and demerit of the algorithm.

Answer: DDA Line Algorithm

1.Read the line end points (x₁,y₁ ) and (x₂,y₂) such that they are not equal.

[if equal then plot that point and exit]

2.∆x = and ∆y =

3.If then

Length=

else

Length=

end if

4.= (x₂-x₁)/length

= (y₂-y₁)/length

This makes either or equal to 1 because the length is either

| x₂-x₁| or |y₂-y₁|, the incremental value for either x or y is 1.

5. 5.x = x1+0.5 * sign()

y = y1+0.5*sign()

[Here the sign function makes the algorithm worl in all quadrant. It returns –1, 0,1 depending on whether its argument is <0, =0, >0 respectively. The factor 0.5 makes it possible to round the values in the integer function rather than truncating them]

6.i=1 [begins the loop, in this loop points are plotted]

7. while(ilength)

{

Plot (Integer(x), Integer(y))

x= x+∆x

y= y+∆y

i=i+1

}

8. stop

Let us see few examples to illustrate this algorithm.

Example:- Consider the line from (0,0) to (4,6). Use the simple DDA algorithm to rasterize this line.

Evaluating steps 1 to 5 in the DDA algorithm we have

x₁₌₀, x_{2= 4}, y₁₌₀, y₂₌₆

length = =6

∆x = =

∆y=

Initial values for

x= 0+0.5*sign ()=0.5

y= 0+ 0.5 * sign(1)=0.5

Tabulating the results of each iteration in the step 6 we get,

fig1

The results are plotted as shown in the Fig 1 It shows that the rasterized line lies to both sides of the actual line, i.e. the algorithm is orientation dependent.

Fig 2: Result for s simple DDA

Eample: Consider the line from (0,0) to (-6,-6). Use the simple DDA algorithm to rasterize this line.

x1=0, x2= -6,y1=0, y2=-6

length = =6

==-1

Initial values for

x= 0+0.5*sign (-1) = -0.5

y= 0+ 0.5 * sign(-1) = -0.5

Tabulating the results of each iteration in the step 6 we get,

Fig. 3

The results are plotted as shown in the Fig 3 It shows that the rasterized line lies on the actual line and it is 45⁰ line.

Advantages of DDA Algorithm

1. It is the simplest algorithm and it does not require special skills for implementation.

2. It is a faster method for calculating pixel positions than the direct use of equation y=mx + b. It eliminates the multiplication in the equation by making use of raster characteristics, so that appropriate increments are applied in the x or y direction to find the pixel positions along the line path.

Disadvantages of DDA Algorithm

1. Floating point arithmetic in DDA algorithm is still time-consuming.

2.The algorithm is orientation dependent. Hence end point accuracy is poor

3. Write a short note on:

A) Reflection

B) Sheer

C) Rotation about an arbitrary axis

Answer:

Reflection:- A reflection is a transformation that produces a mirror image of an object relative to an axis of reflection. We can choose an axis of reflection in the xy plane or perpendicular to the xy plane. The table below gives examples of some common reflection.

Fig. 1 Reflection about y axis

fig2

Shear: A transformation that slants the shape of an objects is called the shear transformation. Two common shearing transformations are used. One shifts x coordinate values and other shifts y coordinate values. However, in both the cases only one coordinate (x or y) changes its coordinates and other preserves its values.

1 X shear : The x shear preserves they coordinates, but changes the x values which causes vertical lines to tilt right or left as shown in the fig. 6.7. The transformation matrix for x shear is given as

Fig 3

…. (4)

2 Y Shear: The y shear preserves the x coordinates, but changes the y values which causes horizontal lines to transform into lines which slope up or down, as shown in the Fig. 6.8.

Fig. 5

The transformation matrix for y shear is given as

…. (6)

Rotation about Arbitrary Axis : A rotation matrix for any axis that does not coincide with a coordinate axis can be set up as a composite transformation involving combinations of translation and the coordinate-axes rotations.

In a special case where an object is to be rotated about an axis that is parallel to one of the coordinate axes we can obtain the resultant coordinates with the following transformation sequence.

1. Translate the object so that the rotation axis coincides with the parallel coordinate axis

2. Perform the specified rotation about that axis.

3. Translate the object so that the rotation axis is moved back to its original position

When an object is to be rotated about an axis that is not parallel to one of the coordinate axes, we have to perform some additional transformations. The sequence of these transformations is given below.

1. Translate the object so that rotation axis specified by unit vector u passes through the coordinate origin. (See fig. 5)

2. Rotate the object so that the axis of rotation coincides with one of the coordinate axes. Usually the z axis is preferred. To coincide the axis of rotation to z axis we have to first perform rotation of unit vector u about x axis to bring it into xz plane and then perform rotation about y axis to coincide it with z axis.(See Figs. 6)
   3. Perform the desired rotation about the z axis

4. Apply the inverse rotation about y axis and then about x axis to bring the rotation axis back to its original orientation.

5. Apply the inverse translation to move the rotation axis back to its original position.

As shown in the Fig. 6.23 (a) the rotation axis is defined with two coordinate points P₁ and P₂ and unit vector u is defined along the rotation of axis as

Where V is the axis vector defined by two points P₁ and P₂ as

V = P₂ – P₁ = (x₂ – x₁, y₂ – y₁, z₂ – z₁)

The components a, b and c of unit vector us are the direction cosines for the rotation axis and they can be defined as

Fig. 7

As mentioned earlier, the first step in the transformation sequence is to translate the object to pass the rotation axis through the coordinate origin. This can be accomplished by moving point P₁ to the origin. The translation is as given below.

Now we have to perform the rotation of unit vector u about x axis. The rotation of u around the x axis into the xz plane is accomplished by rotation can be determined from the dot product of into the z axis and the cosine of the rotation angle through angle and the unit vector u_z(0, 0, 1) along the z axis.

where and u_z(0, 0, 1) = K

=

Where d is the magnitude of :

Similarly, we can determine the sine of from the cross product of .

…(6.33)

and the Cartesian form for the cross product given as

…(6.34)

Equating the right sides of equations 6.33 and 6.34 we get

since

This can also be verified graphically as shown in Fig. 6.24

Fig. 8

By substituting values of cos   the rotation matrix Rand sin_x can be given as

Next we have to perform the rotation of unit vector about y axis. This can be achieved by rotating as follows. and sin  onto the z axis. Using similar equations we can determine cos through angle

We have angle of rotation = =

Consider cross product of and u_z

Cartesian form of cross product gives us

Equating above equations,

But we have,

and

in the rotation matrix R and sin By substituting value of cos _y can be given as

Let

Resultant rotation matrix R_xy = R_x . R_y

From equation 9 we have

Using above equation we get inverse of R_xy as Inverse of translation matrix can be given as

With transformation matrices T and R_xy we can align the rotation axis with the positive z axis. Now the specified rotation with angle  can be achieved by rotation transformation as given below.

To complete the required rotation about the given axis, we have to transform the rotation axis back to its original position. This can be achieved by applying the inverse transformations T^-1 and The overall transformation matrix for rotation about an arbitrary axis then can be expressed as the concatenation of five individual transformations.

4) Describe the following:
A) Basic Concepts in Line Drawing

C) Bresenham’s Line Drawing Algorithm

B) Digital Differential Analyzer Algorithm

Answer:

Basic Concepts in Line Drawing :- Basic Concepts in Line Drawing : Before discussing specific line drawing algorithms it is useful to note the general requirements for such algorithms. These requirements specify the desired characteristics of line.

· The line should appear as a straight line and it should start and end accurately.

· The line should be displayed with constant brightness along its length independent of its length and orientation.

· The line should be drawn rapidly.

Let us see the different lines drawn in Fig.1

a) Vertical and horizontal lines b) 45⁰ line

c) Lines with other orientation

As shown in Fig.1 (a), horizontal and vertical lines are straight and have same width. The 45⁰ line is straight but its width is not constant. On the other hand, the line with any other orientation is neither straight nor has same width. Such cases are due to the finite resolution of display and we have to accept approximate pixels in such situations, shown in Fig.1 (c).

The brightness of the line is dependent on the orientation of the line. We can observe that the effective spacing between pixels for the 45⁰ line is greater than for the vertical and horizontal lines. This will make the vertical and horizontal lines appear brighter than the 45⁰ line. Complex calculations are required to provide equal brightness along lines of varying length and orientation. Therefore, to draw line rapidly some compromises are made such as

· Calculate only an approximate line length.

· Reduce the calculations using simple integer arithmetic

· Implement the result in hardware or firmware.

Bresenham’s Line Dra Digital Differential Analyzer Algorithm wing Algorithm :- The Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. A minor extension to the original algorithm also deals with drawing circles. While algorithms such as Wu's algorithm are also frequently used in modern computer graphics because they can support antialiasing, the speed and simplicity of Bresenham's line algorithm mean that it is still important. The algorithm is used in hardware such as plotters and in the graphics chips of modern graphics cards. It can also be found in many software graphics libraries. Because the algorithm is very simple, it is often implemented in either the firmware or the hardware of modern graphics cards.

Bresenham's algorithm chooses the integer y corresponding to the pixel center that is closest to the ideal (fractional) y for the same x; on successive columns y can remain the same or increase by 1. The general equation of the line through the endpoints is given by

Since we know the column, x, the pixel's row, y, is given by rounding this quantity to the nearest integer:

The slope (y₁ − y₀) / (x₁ − x₀)

depends on the endpoint coordinates only and can be precomputed, and the ideal y for 

successive integer values of x can be computed starting from y₀ and repeatedly adding the 

slope.

Digital Differential Analyzer Algorithm:- In computer graphics, a hardware or software implementation of a digital differential analyzer (DDA) is used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. In its simplest implementation the DDA algorithm interpolates values in interval [(x_start, y_start), (x_end, y_end)] by computing for each x_i the equations x_i = x_i−1+1/m, y_i = y_i−1 + m, where Δx = x_end − x_start and Δy = y_end − y_start and m = Δy/Δx The DDA method can be implemented using floating-point or integer arithmetic. The native floating-point implementation requires one addition and one rounding operation per interpolated value (e.g. coordinate x, y, depth, color component etc.) and output result. This process is only efficient when an FPU with fast add and rounding operation is available. The fixed-point integer operation requires two additions per output cycle, and in case of fractional part overflow, one additional increment and subtraction. The probability of fractional part overflows is proportional to the ratio m of the interpolated start/end values. DDAs are well suited for hardware implementation and can be pipelined for maximized throughput. where m represents the slope the line and c is the y intercept . this slope can be expressed in DDA as

      yend-ystart
  m= -----------   
      xend-xstart

February 2011

Master of Computer Application (MCA) – Semester 3

MC0073 – System Programming

Assignment Set – 1

1. Explain the following
   A) Lexical Analysis
   B) Syntax Analysis
   Answer:
   Lexical Analysis: In computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner. A lexer often exists as a single function which is called by a parser or another function

   Lexical grammar: The specification of a programming language will often include a set of rules which defines the lexer. These rules usually consist of regular expressions and they define the set of possible character sequences that are used to form individual tokens or lexemes. In programming languages delimiting blocks with tokens (e.g., "{" and "}") as opposed to off-side rule languages delimiting blocks with indentation, white space is also defined by a regular expression and influences the recognition of other tokens but does not itself contribute tokens. White space is said to be non-significant in such languages.

   Token: A token is a string of characters, categorized according to the rules as a symbol (e.g., IDENTIFIER, NUMBER, COMMA). The process of forming tokens from an input stream of characters is called tokenization and the lexer categorizes them according to a symbol type. A token can look like anything that is useful for processing an input text stream or text file.

A lexical analyzer generally does nothing with combinations of tokens, a task left for a parser. For example, a typical lexical analyzer recognizes parentheses as tokens, but does nothing to ensure that each '(' is matched with a ')'.

Consider this expression in the C programming language:

sum=3+2;

Tokenized in the following table:

Lexeme	Token type
sum	Identifier
=	Assignment operator
3	Number
+	Addition operator
2	Number
;	End of statement

Tokens are frequently defined by regular expressions, which are understood by a lexical analyzer generator such as lex. The lexical analyzer (either generated automatically by a tool like lex, or hand-crafted) reads in a stream of characters, identifies the lexemes in the stream, and categorizes them into tokens. This is called "tokenizing." If the lexer finds an invalid token, it will report an error.

Following tokenizing is parsing. From there, the interpreted data may be loaded into data structures for general use, interpretation, or compiling.

Scanner: The first stage, the scanner, is usually based on a finite-state machine (FSM). It has encoded within it information on the possible sequences of characters that can be contained within any of the tokens it handles (individual instances of these character sequences are known as lexemes). For instance, an integer token may contain any sequence of numerical digit characters. In many cases, the first non-whitespace character can be used to deduce the kind of token that follows and subsequent input characters are then processed one at a time until reaching a character that is not in the set of characters acceptable for that token (this is known as the maximal munch rule, or longest match rule). In some languages[which?] the lexeme creation rules are more complicated and may involve backtracking over previously read characters.

Tokenizer : Tokenization is the process of demarcating and possibly classifying sections of a string of input characters. The resulting tokens are then passed on to some other form of processing. The process can be considered a sub-task of parsing input.

Take, for example

The quick brown fox jumps over the lazy dog

The string isn't implicitly segmented on spaces, as an English speaker would do. The raw input, the 43 characters, must be explicitly split into the 9 tokens with a given space delimiter (i.e. matching the string " " or regular expression /\s{1}/).

The tokens could be represented in XML,

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
</sentence>

Syntax Analysis : Unlike other aspects of the compiler, the syntax analysis parts are not very separable, since they are mixed up with calls to all other parts, such as semantic analysis.

However the method used is that commonly known as recursive descent. This will not be treated in great detail here - consult any book on compiler theory for details.

The method depends on writing a separate parsing procedure for each kind of syntactic structure, such as if statement, assignment statement, expression and so on, and each of these is only responsible for analysing its own kind of structure. If any structure contains another structure then the parsing procedure can call the procedure for this contained structure. As an example, consider the procedure ifstatement. Eliminating all but the syntax analysis parts leaves

procedure ifstatement;
begin
    expression;
    if sy = thensy then insymbol
    else error(52);
    statement;
    if sy = elsesy then
    begin
        insymbol; statement
    end
end;

This relies on the existence of similar procedures for expression and statement. When ifstatement is called, the initial if symbol has already been recognised, so the first action of ifstatement is to call the procedure expression to parse the condition. A then symbol should follow, so this is tested for and skipped if present, and an error announced if absent. Procedure statement is called after this to parse the statement that should follow. The else part is optional, so if an else symbol is present it is skipped and statement called; otherwise nothing more is done.Another simple example is whilestatement

procedure whilestatement;
begin
    expression;
    if sy = dosy then insymbol else error(54);
    statement
end;
Of course constructs may contain their own constructs, for instance an if statement may contain another if statement: and this is why the method is called recursive, since in this case ifstatement will call statement, which will again call ifstatement for the enclosed if statement, which will itself again call statement.

Error Recovery: Recursive descent works very well as long as the program being compiled is syntactically correct. However, as soon as there is a syntax error it risks getting completely out of step with the source program. For instance, if the then symbol should be misspelled

if a > max tehn max:=a

then error 52 will be reported, and statement will be called with tehn as its first symbol. In trying to parse this as an assignment statement, tehn will be flagged as an undeclared identifier, and the becomes symbol will be reported as missing after it, and so on with a hopeless cascade of error messages, all because of one error.

So, in an attempt to reduce these cascading messages, a method of error recovery has been used. The method involves passing over to parsing procedures a set of symbols representing what might be called synchronising points. When a syntax error occurs, symbols may be skipped until one of the synchronising points is found, allowing the parser to get back into phase. An example of such synchronisation is at in procedure statement, where if the statement being compiled is not followed by an acceptable symbol, error 6 is reported and procedure skip is called to skip input symbols to a synchronising point.

So, returning to procedure ifstatement and now adding the error recovery parts:

procedure ifstatement;
begin
    expression(fsys + [thensy]);
    if sy = thensy then insymbol
    else error(52);
    statement(fsys + [elsesy]);
    if sy = elsesy then
     begin insymbol;
         statement(fsys)
    end
end;

Fsys is nonlocal to ifstatement, passed over to statement , and containing the synchronising symbols for this statement. When expression is called, thensy is added to this set as an extra possible synchronising point. Similarly, when statement is called at elsesy is added to the set, since an else may follow it.

Fsys is set up initially in the call to the first compiling procedure programme for the main program. Its initial value is all those symbols that can uniquely start a declaration (blockbegsys) or a statement . Casesy is excluded since it may also appear as part of a record declaration, and so does not make a very good choice of synchronisation point. It is added back into the set at the call of body once the declarations have safely been compiled. The procedure for a while statement, with added error recovery parts, is

procedure whilestatement;
begin
    expression(fsys + [dosy]);
    if sy = dosy then insymbol else error(54);
    statement(fsys)
end;

This method of error-recovery is formalised in Hartmann (1975) and Pemberton (1979).

2. What is RISC and how it is different from the CISC?

Answer:

RISC:The Reduced Instruction Set Computer, or RISC, is a microprocessor CPU design philosophy that favors a simpler set of instructions that all take about the same amount of time to execute. The most common RISC microprocessors are AVR, PIC, ARM, DEC Alpha, PA-RISC, SPARC, MIPS, and IBM’s PowerPC.

· RISC characteristics

- Small number of machine instructions : less than 150

- Small number of addressing modes : less than 4

- Small number of instruction formats : less than 4

- Instructions of the same length : 32 bits (or 64 bits)

- Single cycle execution

- Load / Store architecture

- Large number of GRPs (General Purpose Registers): more than 32

- Hardwired control

- Support for HLL (High Level Language).

RISC and x86 : However, despite many successes,RISC has made few inroads into the desktop PC and commodity server markets, where Intel’s x86 platform remains the dominant processor architecture (Intel is facing increased competition from AMD, but even AMD’s processors implement the x86 platform, or a 64-bit superset known as x86-64). There are three main reasons for this. One, the very large base of proprietary PC applications are written for x86, whereas no RISC platform has a similar installed base, and this meant PC users were locked into the x86. The second is that, although RISC was indeed able to scale up in performance quite quickly and cheaply, Intel took advantage of its large market by spending vast amounts of money on processor development. Intel could spend many times as much as any RISC manufacturer on improving low level design and manufacturing. The same could not be said about smaller firms like Cyrix and NexGen, but they realized that they could apply pipelined design philosophies and practices to the x86-architecture – either directly as in the 6×86 and MII series, or indirectly (via extra decoding stages) as in Nx586 and AMD K5. Later, more powerful processors such as Intel P6 and AMD K6 had similar RISC-like units that executed a stream of micro-operations generated from decoding stages that split most x86 instructions into several pieces. Today, these principles have been further refined and are used by modern x86 processors such as Intel Core 2 and AMD K8. The first available chip deploying such techniques was the NexGen Nx586, released in 1994 (while the AMD K5 was severely delayed and released in 1995). As of 2007, the x86 designs (whether Intel’s or AMD’s) are as fast as (if not faster than) the fastest true RISC single-chip solutions available.

CISC: A Complex Instruction Set Computer (CISC) supplies a large number of complex instructions at the assembly language level. Assembly language is a low-level computer programming language in which each statement corresponds to a single machine instruction. CISC instructions facilitate the extensive manipulation of low-level computational elements and events such as memory, binary arithmetic, and addressing. The goal of the CISC architectural philosophy is to make microprocessors easy and flexible to program and to provide for more efficient memory use.

The CISC philosophy was unquestioned during the 1960s when the early computing machines such as the popular Digital Equipment Corporation PDP 11 family of minicomputers were being programmed in assembly language and memory was slow and expensive.

CISC machines merely used the then-available technologies to optimize computer performance. Their advantages included the following: (1) A new processor design could incorporate the instruction set of its predecessor as a subset of an ever-growing language–no need to reinvent the wheel, code-wise, with each design cycle. (2) Fewer instructions were needed to implement a particular computing task, which led to lower memory use for program storage and fewer time-consuming instruction fetches from memory. (3) Simpler compilers sufficed, as complex CISC instructions could be written that closely resembled the instructions of high-level languages. In effect, CISC made a computer’s assembly language more like a high-level language to begin with, leaving the compiler less to do.

Some disadvantages of the CISC design philosophy are as follows: (1) The first advantage listed above could be viewed as a disadvantage. That is, the incorporation of older instruction sets into new generations of processors tended to force growing complexity. (3) Many specialized CISC instructions were not used frequently enough to justify their existence. The existence of each instruction needed to be justified because each one requires the storage of more microcode at in the central processing unit (the final and lowest layer of code translation), which must be built in at some cost. (4) Because each CISC command must be translated by the processor into tens or even hundreds of lines of microcode, it tends to run slower than an equivalent series of simpler commands that do not require so much translation. All translation requires time. (4) Because a CISC machine builds complexity into the processor, where all its various commands must be translated into microcode for actual execution, the design of CISC hardware is more difficult and the CISC design cycle correspondingly long; this means delay in getting to market with a new chip.

The terms CISC and RISC (Reduced Instruction Set Computer) were coined at this time to reflect the widening split in computer-architectural philosophy.

RISC VS CISC :

CISC	RISC
Emphasis on hardware	Emphasis on software
Includes multi-clock complex instructions	Single-clock, reduced instruction only
Memory-to-memory: "LOAD" and "STORE" incorporated in instructions	Register to register: "LOAD" and "STORE" are independent instructions
Small code sizes, high cycles per second	Low cycles per second, large code sizes
Transistors used for storing complex instructions	Spends more transistors on memory registers

Fig. 1.0 (table for CISC VS RISC)

3. Explain the following with respect to the design specifications of an Assembler:
   A) Data Structures
   B) pass1 & pass2 Assembler flow chart

Answer:

Data Structure: The second step in our design procedure is to establish the databases that we have to work with.

Pass 1 Data Structures

1. Input source program

2. A Location Counter (LC), used to keep track of each instruction’s location.

3. A table, the Machine-operation Table (MOT), that indicates the symbolic mnemonic, for each instruction and its length (two, four, or six bytes)

4. A table, the Pseudo-Operation Table (POT) that indicates the symbolic mnemonic and action to be taken for each pseudo-op in pass 1.

5. A table, the Symbol Table (ST) that is used to store each label and its corresponding value.

6. A table, the literal table (LT) that is used to store each literal encountered and its corresponding assignment location.

7. A copy of the input to be used by pass 2.

Pass 2 Data Structures

1. Copy of source program input to pass1.

2. Location Counter (LC)

3. A table, the Machine-operation Table (MOT), that indicates for each instruction, symbolic mnemonic, length (two, four, or six bytes), binary machine opcode and format of instruction.

4. A table, the Pseudo-Operation Table (POT), that indicates the symbolic mnemonic and action to be taken for each pseudo-op in pass 2.

5. A table, the Symbol Table (ST), prepared by pass1, containing each label and corresponding value.

6. A Table, the base table (BT), that indicates which registers are currently specified as base registers by USING pseudo-ops and what the specified contents of these registers are.

7. A work space INST that is used to hold each instruction as its various parts are being assembled together.

8. A work space, PRINT LINE, used to produce a printed listing.

9. A work space, PUNCH CARD, used prior to actual outputting for converting the assembled instructions into the format needed by the loader.

10. An output deck of assembled instructions in the format needed by the loader.

Fig. 1. Data structures of the assembler

Format of Data Structures The third step in our design procedure is to specify the format and content of each of the data structures. Pass 2 requires a machine operation table (MOT) containing the name, length, binary code and format; pass 1 requires only name and length. Instead of using two different tables, we construct single (MOT). The Machine operation table (MOT) and pseudo-operation table are example of fixed tables. The contents of these tables are not filled in or altered during the assembly process. The following figure depicts the format of the machine-op table (MOT)

—————————————– 6 bytes per entry ———————————–

Mnemonic Opcode (4bytes) character	Binary Opcode (1byte) (hexadecimal)	Instruction length(2 bits) (binary)	Instructionformat (3bits) (binary)	Not used here (3 bits)
“Abbb”	5A	10	001
“Ahbb”	4A	10	001
“ALbb”	5E	10	001
“ALRB”	1E	01	000
…….	…….	…….	…….

Fig.: 2

3.The flowchart for Pass – 1:

The primary function performed by the analysis phase is the building of the symbol table. For this purpose it must determine the addresses with which the symbol names used in a program are associated. It is possible to determine some address directly, e.g. the address of the first instruction in the program, however others must be inferred.

To implement memory allocation a data structure called location counter (LC) is introduced. The location counter is always made to contain the address of the next memory word in the target program. It is initialized to the constant. Whenever the analysis phase sees a label in an assembly statement, it enters the label and the contents of LC in a new entry of the symbol table. It then finds the number of memory words required by the assembly statement and updates; the LC contents. This ensure: that LC points to the next memory word in the target program even when machine instructions have different lengths and DS/DC statements reserve different amounts of memory. To update the contents of LC, analysis phase needs to know lengths of different instructions. This information simply depends on the assembly language hence the mnemonics table can be extended to include this information in a new field called length. We refer to the processing involved in maintaining the location counter as LC processing.

Flow hart for Pass – 2

Fig.4Pass2 flowchart

4.Define the following,

1. Parsing
2. Scanning
3. Token

Answer:

Parsing:

Parsing transforms input text or string into a data structure, usually a tree, which is suitable for later processing and which captures the implied hierarchy of the input. Lexical analysis creates tokens from a sequence of input characters and it is these tokens that are processed by a parser to build a data structure such as parse tree or abstract syntax trees.

Conceptually, the parser accepts a sequence of tokens and produces a parse tree. In practice this might not occur.

1. The source program might have errors. Shamefully, we will do very little error handling.

2. Real compilers produce (abstract) syntax trees not parse trees (concrete syntax trees). We don’t do this for the pedagogical reasons given previously.

There are three classes for grammar-based parsers.

1. Universal

2. Top-down

3. Bottom-up

The universal parsers are not used in practice as they are inefficient; we will not discuss them.

As expected, top-down parsers start from the root of the tree and proceed downward; whereas, bottom-up parsers start from the leaves and proceed upward. The commonly used top-down and bottom parsers are not universal. That is, there are (context-free) grammars that cannot be used with them. The LL and LR parsers are important in practice. Hand written parsers are often LL. Specifically, the predictive parsers we looked at in chapter two are for LL grammars. The LR grammars form a larger class. Parsers for this class are usually constructed with the aid of automatic tools.

Scanning and token:

There are three phases of analysis with the output of one phase the input of the next. Each of these phases changes the representation of the program being compiled. The phases are called lexical analysis or scanning, which transforms the program from a string of characters to a string of tokens. Syntax Analysis or Parsing, transforms the program into some kind of syntax tree; and Semantic Analysis, decorates the tree with semantic information.

The character stream input is grouped into meaningful units called lexemes, which are then mapped into tokens, the latter constituting the output of the lexical analyzer.

For example, any one of the following C statements

x3 = y + 3;

x3 = y + 3 ;

x3 = y+ 3 ;

but not

x 3 = y + 3;

would be grouped into the lexemes x3, =, y, +, 3, and ;. A token is a

<token-name,attribute-value> pair. The hierarchical decomposition above sentence is given figure 1.0

Fig. 1.0

A token is a <token-name, attribute-value> pair.

For example

1. The lexeme x3 would be mapped to a token such as <id,1>. The name id is short for identifier. The value 1 is the index of the entry for x3 in the symbol table produced by the compiler. This table is used gather information about the identifiers and to pass this information to subsequent phases.

2. The lexeme = would be mapped to the token <=>. In reality it is probably mapped to a pair, whose second component is ignored. The point is that there are many different identifiers so we need the second component, but there is only one assignment symbol =.

3. The lexeme y is mapped to the token <id,2>

4. The lexeme + is mapped to the token <+>.

5. The number 3 is mapped to <number, something>, but what is the something. On the one hand there is only one 3 so we could just use the token <number,3>.

6. However, there can be a difference between how this should be printed (e.g., in an error message produced by subsequent phases) and how it should be stored (fixed vs. float vs. double). Perhaps the token should point to the symbol table where an entry for this kind of 3 is stored. Another possibility is to have a separate numbers table.

7. The lexeme ; is mapped to the token <;>.

Note, non-significant blanks are normally removed during scanning. In C, most blanks are non-significant. That does not mean the blanks are unnecessary. Consider

int x;

intx;

The blank between int and x is clearly necessary, but it does not become part of any token. Blanks inside strings are an exception, they are part of the token (or more likely the table entry pointed to by the second component of the token).

Note that we can define identifiers, numbers, and the various symbols and punctuation without using recursion (compare with parsing below).

Parsing involves a further grouping in which tokens are grouped into grammatical phrases, which are often represented in a parse tree.

5. Describe the process of Bootstrapping in the context of Linkers

Answer:

Boot straping: In computing, bootstrapping refers to a process where a simple system activates another more complicated system that serves the same purpose. It is a solution to the Chicken-and-egg problem of starting a certain system without the system already functioning. The term is most often applied to the process of starting up a computer, in which a mechanism is needed to execute the software program that is responsible for executing software programs (the operating system).

Bootstrap loading:The discussions of loading up to this point have all presumed that there’s already an operating system or at least a program loader resident in the computer to load the program of interest. The chain of programs being loaded by other programs has to start somewhere, so the obvious question is how is the first program loaded into the computer?

In modern computers, the first program the computer runs after a hardware reset invariably is stored in a ROM known as bootstrap ROM. as in "pulling one’s self up by the bootstraps." When the CPU is powered on or reset, it sets its registers to a known state. On x86 systems, for example, the reset sequence jumps to the address 16 bytes below the top of the system’s address space. The bootstrap ROM occupies the top 64K of the address space and ROM code then starts up the computer. On IBM-compatible x86 systems, the boot ROM code reads the first block of the floppy disk into memory, or if that fails the first block of the first hard disk, into memory location zero and jumps to location zero. The program in block zero in turn loads a slightly larger operating system boot program from a known place on the disk into memory, and jumps to that program which in turn loads in the operating system and starts it. (There can be even more steps, e.g., a boot manager that decides from which disk partition to read the operating system boot program, but the sequence of increasingly capable loaders remains.)

Why not just load the operating system directly? Because you can’t fit an operating system loader into 512 bytes. The first level loader typically is only able to load a single-segment program from a file with a fixed name in the top-level directory of the boot disk. The operating system loader contains more sophisticated code that can read and interpret a configuration file, uncompress a compressed operating system executable, address large amounts of memory (on an x86 the loader usually runs in real mode which means that it’s tricky to address more than 1MB of memory.) The full operating system can turn on the virtual memory system, loads the drivers it needs, and then proceed to run user-level programs.

Many Unix systems use a similar bootstrap process to get user-mode programs running. The kernel creates a process, then stuffs a tiny little program, only a few dozen bytes long, into that process. The tiny program executes a system call that runs /etc/init, the user mode initialization program that in turn runs configuration files and starts the daemons and login programs that a running system needs.

None of this matters much to the application level programmer, but it becomes more interesting if you want to write programs that run on the bare hardware of the machine, since then you need to arrange to intercept the bootstrap sequence somewhere and run your program rather than the usual operating system. Some systems make this quite easy (just stick the name of your program in AUTOEXEC.BAT and reboot Windows 95, for example), others make it nearly impossible. It also presents opportunities for customized systems. For example, a single-application system could be built over a Unix kernel by naming the application /etc/init.

Software Bootstraping & Compiler Bootstraping:Bootstrapping can also refer to the development of successively more complex, faster programming environments. The simplest environment will be, perhaps, a very basic text editor (e.g. ed) and an assembler program. Using these tools, one can write a more complex text editor, and a simple compiler for a higher-level language and so on, until one can have a graphical IDE and an extremely high-level programming language

Compiler Bootstraping:In compiler design, a bootstrap or bootstrapping compiler is a compiler that is written in the target language, or a subset of the language, that it compiles. Examples include gcc, GHC, OCaml, BASIC, PL/I and more recently the Mono C# compiler.

6. Describe the procedure for design of a Linker.

Answer:

Design of a linker: Relocation and linking requirements in segmented addressing

The relocation requirements of a program are influenced by the addressing structure of the computer system on which it is to execute. Use of the segmented addressing structure reduces the relocation requirements of program.

A Linker for MS-DOS:

Example 1: Consider the program of written in the assembly language of intel 8088. The ASSUME statement declares the segment registers CS and DS to the available for memory addressing. Hence all memory addressing is performed by using suitable displacements from their contents. Translation time address o A is 0196. In statement 16, a reference to A is assembled as a displacement of 196 from the contents of the CS register. This avoids the use of an absolute address, hence the instruction is not address sensitive. Now no relocation is needed if segment SAMPLE is to be loaded with address 2000 by a calling program (or by the OS). The effective operand address would be calculated as <CS>+0196, which is the correct address 2196. A similar situation exists with the reference to B in statement 17. The reference to B is assembled as a displacement of 0002 from the contents of the DS register. Since the DS register would be loaded with the execution time address of DATA_HERE, the reference to B would be automatically relocated to the correct address.

Though use of segment register reduces the relocation requirements, it does not completely eliminate the need for relocation. Consider statement 14 .

MOV AX, DATA_HERE Which loads the segment base of DATA_HERE into the AX register preparatory to its transfer into the DS register . Since the assembler knows DATA_HERE to be a segment, it makes provision to load the higher order 16 bits of the address of DATA_HERE into the AX register. However it does not know the link time address of DATA_HERE, hence it assembles the MOV instruction in the immediate operand format and puts zeroes in the operand field. It also makes an entry for this instruction in RELOCTAB so that the linker would put the appropriate address in the operand field. Inter-segment calls and jumps are handled in a similar way. Relocation is somewhat more involved in the case of intra-segment jumps assembled in the FAR format. For example, consider the following program : FAR_LAB EQU THIS FAR ; FAR_LAB is a FAR label JMP FAR_LAB ; A FAR jump Here the displacement and the segment base of FAR_LAB are to be put in the JMP instruction itself. The assembler puts the displacement of FAR_LAB in the first two operand bytes of the instruction , and makes a RELOCTAB entry for the third and fourth operand bytes which are to hold the segment base address. A segment like ADDR_A DW OFFSET A (which is an ‘address constant’) does not need any relocation since the assemble can itself put the required offset in the bytes. In summary, the only RELOCATAB entries that must exist for a program using segmented memory addressing are for the bytes that contain a segment base address. For linking, however both segment base address and offset of the external symbol must be computed by the linker. Hence there is no reduction in the linking requirements.

Some More comming ................................................................................