Spos by Dhamdhere PDF

ate an apple an apple apple

eer daueun-o The string is a sentence of Lg because the boy ate an apple - . Parse trees The sequence of derivations that produces a string from the distinguished symbol or the sequence of reductions that reduces the string to the distinguished symbol reveals the string’s syntactic structure. We use a parse tree to depict the syntactic structure of a string. A part of the parse tree is built at every derivation or reduction. Consider the production S NT; .... When a derivation is made according to this production, we build the following elemental parse tree: s JIN ONT If the next step in the derivation replaces NT; by some string , we build the following elemental parse tree to depict this derivation NT; JIN String B and combine this tree with the previous tree by replacing the node of NT; in the first tree by this tree. In essence, the parse tree has grown in the downward direction duc to a derivation. We can obtain a parse tree from a sequence of reductions by performi the converse actions, i.c., by building an elemental parse tree to indicate how a string of terminal and nonterminal symbols is replaced by a single nonterminal. Such a tree would grow in the upward direction. Example 6.6 illustrates parse trees.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.206 Systems Programming a string containing a single terminal symbol and a single nonterminal symbol— gives some practical advantages in scanning (we shall see this aspect in Chap- ter 7). However, the nature of the productions restricts the expressive power of these grammars, ¢.g., nesting of constructs or matching of parentheses cannot be specified using such productions. Hence the use of Type-3 productions is restricted to the specification of lexical units, e.g., identifiers, constants, labels, etc. The productions for and in Grammar (6.3) are in fact Type-3 in nature. It can be seen clearly when we rewrite the production for in a form that resembles Bt [tas nel|I|d where / and d stand for a letter and a digit, respectively. Type-3 grammars are also known as linear grammars or regular grammars. ‘These are further categorized into lefi-linear and right-linear grammars depending on whether the nonterminal symbol in the RHS alternative appears at the extreme left or extreme right. Operator grammars Definition 6.2 (Operator grammar (OG)) Productions of an operator grammar do not contain two or more consecutive nonterminal symbols in any RHS alternative. ‘Thus, nonterminal symbols occurring in an RHS string are separated by one or more terminal symbols. Each such terminal symbol is called an operator of the grammar. As discussed later in Chapter 7, strings specified by using an operator grammar can be parsed in a simple and efficient manner. Example 6.7 discusses an operator grammar. Example 6.7 (Operator grammar) Grammar (6.3) is un operator grammar because it sat- isfies Definition 6.2. The symbols *t’, ‘+’, ‘+", ‘Cand *)' are the operators of the grammar. 6.1.2 Ambiguity in Grammatic Specification A grammar is ambiguous if a string can be interpreted in two or more ways by using it. In natural languages, ambiguity may concern the meaning of a word, the syntax category of a word, or the syntactic structure of a construct. For example, a word can have multiple meanings or it can be both a noun and a verb (e.g., the word “base” ‘can mean a chemical base, a military base, or the construction of a foundation), and a sentence can have more than one syntactic structure (¢.g., “police was ordered to stop speeding on roads’). In a formal language grammar, ambiguity would arise if identical strings can occur on the RHS of two or more productions. For example, if a grammar has thea You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.210 Systems Programming transition, or simply a transition. Thus, the current state of a finite state automaton is determined by the string of source symbols it has processed so far. If a string is valid, this state is called a final state of the finite state automaton. A formal definition of a finite state automaton follows. Definition 6.3 (Finite state automaton (FSA)) A finite state automaton is a triple (S, E, T) where S isa finite set of states, one of which is the initial state sina, and one or more of which are the final states Eis the alphabet of source symbols T isa finite set of state transitions defining transitions out of states in on encountering symbols in 3. A deterministic finite state automaton (DFA) is a finite state automaton none of whose states has two or more transitions for the same source symbol. The DFA has the property that it reaches a unique state for every source string input to it. Each transition of the DFA can be represented by the triple (old state, source symbol, new state). The transitions in T can thus be represented by a set of such triples. Alternatively, the transitions of the DFA can be represented in the form of a state transition table (STT) which has one row for each state s; in $ and one column for each symbol symb in E. The entry STT(s;, symb) in the table indicates the id of the new state which the DFA would enter if the source symbol symb was input to it while it was in state s;. Thus, the entry STT(s;, symb) = sj and the triple (s;, symb, s)) contain equivalent information. The entry STT(s,, symb) would be blank if the DFA does not contain a transition out of state s; for symb. A deterministic finite state automaton can be represented pictorially by represent- ing each of its states by a circle and each of its state transitions by an arrow drawn from the old state to the new state and labelled by the source symbol that causes the transition. A final state of the DFA is represented by a double circle. Operation of a DFA is controlled by its current state, which we call s.. Its actions are limited to the following: Given a source symbol x at its input, it checks to see whether STT (s., x) is defined—that is, whether STT(s., x) = 5), for some 5). If so, it makes a transition to state sj; we say that it has recognized symbol x. If the entry STT(s¢, x) is blank, it indicates an error and stops. Example 6.11 (DFA for integer strings) Figure 6.3 shows a DFA to recognize integer strings according to the Type-3 rule ::=d \ d where d represents a Part (a) of the figure shows the state transition table for the DFA. Part (b) is a pictorial representation of the DFA. The initial and final states of the DFA are Start and Int respectively. Transitions during the recognition of string 839 would be as shown in the following table because each of 5, 3 and 9 is ad.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.214 Systems Programming ‘Table 6.2 Specification of a scanner Regular expression jemantic actions {+1 -\(@)* {Enter the string in the table of integer constants, say in entry n, Return the token [Int #n] } [+] -]((a)*.(d)" | (d)"(d)*) {Enter the string in the table_of real constants. Return the token [Real #m] } 1\d)* {Compare the string with reserved words. If amatch is found, return the token [Kw #k}; otherwise, enter the string in the symbol table, say, in entry i and return the token [ld fi] } 6.3 PARSING As discussed in Section 2.3.2.1, parsing determines the grammatical structure of a sentence. In Section 6.1, we discussed how parsing can be achieved either through the derivation of a string from a nonterminal symbol, or through the reduction of a string to a nonterminal symbol. It gives rise to two fundamental approaches to parsing called top-down parsing and bottom-up parsing, respectively. If a string is parsed successfully, the parser should build an intermediate code for it; otherwise, it should issue diagnostic messages reporting the cause and nature of error(s) in the string. The intermediate code is either a parse tree or an abstract syntax tree for the string; the latter is more common for reasons described below. Parse tree and abstract syntax trees A parse tree depicts the steps in the parsing of a source string according to a grammar, so it is useful for understanding the process of parsing. However, itis a poor intermediate representation for a source string because much of the information contained in it is not useful for subsequent processing in the compiler. An abstract syntax tree (AST) represents the structure of a source string in a more economical manner. The word ‘abstract’ implies that it is a representation designed by a compiler designer for her own purposes. Consequently, a source string may have different abstract syntax tress in different compilers. However, it has a unique parse tree. Example 6.14 illustrates the nature of the information in the parse tree and an abstract syntax tree for an expression. Example 6.14 (Parse tree and abstract syntax tree) Figure 6.6(a) shows a parse tree for the source string atbec according to Grammar (6.3). It shows how the identifier a is reduced to a primary, factor, term, and finally to an expression, This information is not useful for further processing of the string in the compiler. Figure 6,6(b) shows an abstract syntax tree for the same string. It simply shows that a is an operand of thea You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.218. Systems Programming 1. Source string marker (SSM): At any stage of parsing, the source string marker points to the first unmatched symbol in the source string. . Prediction making mechanism: This mechanism makes a prediction for the leftmost nonterminal symbol in the CSF. When called upon to make a prediction, it selects the RHS alternatives in a production of the nonterminal symbol in a left-to-right manner. It makes a prediction according to the next RHS alte mative in a production if a continuation check had failed during parsing according to the previous prediction; otherwise, it makes a prediction according to the first RHS alternative. This way, the parser will be ale to parse any valid string in Lg. Matching and backtracking mechanism: It implements the continuation check by using the SSM. If the check succeeds, the SSM would be incremented by the number of symbols that were matched. If the check fails, backtracking would be performed by resetting the CSF and the SSM to appropriate earlier values. A stack can be used to support backtracking. A stack entry would contain information about a derivation. It would contain three fields—a nonterminal symbol, an integer indicating which RHS alternative of the nonterminal symbol was under consideration, and the value of the SSM at the start of the derivation. Operation of the parser would be controlled by information in the TOS entry of this stack. Entries would be popped off the stack when derivations match completely or are rejected. BR » Continuation check and backtracking is performed in Step 3 of Algorithm 6.1. A complete algorithm for top-down parsing can be found in (Dhamdhere, 1997), Example 6.15 illustrates operation of a top-down parser. Example 6.15 (Top-down parsing) The string + + , which is the lexically analysed version of the source string atbsc, is to be parsed according to the grammar E T+E|T VaTI|V 65) . The first few steps in the parse are as follows: 1. SSM := 1; CSF :=$S; Make a prediction according to the production for S. Hence CSF := E. 2. Make a prediction according to the first RHS alternative of the production for E. Itis E > T+ E, Hence CSF becomes T + E. 3. Make a prediction according to the first RHS alternative of the production for T. tis T + V + T. Hence CSF becomes V + T +E.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.222 Systems Programming Example 6.16 (Predictive parsing) Table 6.4 summarizes the parsing of + according to Grammar (6.8). Note that Next symbol is the symbol pointed to by the SSM. ‘Table 6.4. Top-down parsing without backtracking St No. Current sentential form (CSF) _Next symbol __ Prediction LE ETE” 2 TE" T=vT" VTE" V T'E" + Te E” + BY> +E +E ESTE" +TE" T>VT" +VT'E" id V=> . Sid > + TE" * TW>eT 10, +*TE" TVvT" MW. +*VT'E" V 12. +*«T'E" - Tse BB. +*E" - Eve M0 4+ = = ‘To start with, CSF = E and the next symbol is *’. The first three steps are obvious. because productions for the three leftmost nonterminals have only one RHS alternative cach. In the 4" step, the next symbol is “+" and the leftmost NT is T”. The parser has to decide whether to make the prediction T”=> » T or T’=> e. Since the next symbol is not +, it makes the prediction T”=> € 6.3.1.1 Practical Top-Down Parsing A recursive descent parser A recursive descent parser employs a variant of top-down parsing without backtracking. It is so named because it uses a set of mutually-recursive procedures to perform parsing. Salient advantages of recursive descent parsing are its simplicity and gener- ality. It can be implemented in any language that supports recursive procedures. ‘To implement recursive descent parsing, a left-factored grammar is modified to make repeated occurrences of strings more explicit. For example, Grammar (6.8) would be rewritten as follows T{+T}Y Viey}" (6.9) where the notation {..}* indicates zero or more occurrences of the enclosed specification, The parser is written such that it has one procedure for each nonterminala You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.226 Systems Programming 1) where nt; is the leftmost nonterminal in the string and t) is the next source symbol. Note that these steps are equivalent to the steps in Example 6.16. ‘The procedure for constructing the parser table is described in the literature cited at the end of the chapter. 6.3.2 Bottom-Up Parsing A bottom-up parser constructs a parse tree for a source string by applying a sequence of reductions to it. The source string is valid if it can be reduced to S, the distinguished symbol of G. If not, an error is detected and reported during the process of reduction, Bottom-up parsing proceeds in a left-to-right manner as follows: The parser applies reductions to the string located to the left of the source string marker (SSM). When it cannot apply any reductions, it advances the SSM by one character and tries to apply reductions to the new string that is located to the left of the SSM, and so on. Thus, 2 typical situation during bottom-up parsing can be depicted as follows: SSM shen nonterminal and terminal only terminal symbols symbols To reach this situation, the parser would have performed some reductions and advanced the SSM over some symbols in the source string. Hence the string to the left of the SSM is composed of nonterminal and terminal symbols. The string to the right of the SSM is yet to be processed by the parser. Hence it consists of terminal symbols only. We try out a naive approach to bottom-up parsing to understand the key issues involved in it. Let there be 1 symbols in the string to the left of the SSM. We try to reduce the last few symbols in this string to some nonterminal symbol, say A, by using one of the RHS alternatives in a production for A. Let this RHS alternative have r symbols in it. This reduction can be depicted as follows: nsymbols SSM Before reduction : i: r symbols n—rsymbols SSM ts, | L After reduction : We advance the SSM if reduction is not possible for any nonterminal and any value of r current operator. Because the only instance of the operator precedence relation = is ‘(’ = *)’, the handle is the substring ‘(..)’ if the previous operator is *)". In all other cases, the handle merely consists of the previous operator and its operands. From these observations it is clear that apart from the current operator, only the previous operator needs to be considered at any point. Therefore, the parser employs a stack to store operators. It would push the current operator on the stack during a shift action and it would pop off the previous operator during a reduce action. To note the relation between operators and operands, each stack entry also accommodates information about the right operand of the operator stored in the entry. Information about the left operand of an operator, if any, would exist in the previous stack entry. We refer to the stack entry below the TOS entry as (TOS-1) entry, or TOSM entry, for short. Since operator precedence parsing ignores the nonterminal symbols in a string, it is not easy to build a parse tree for a source string. However, the parser can build an abstract syntax tree. The nodes in the tree would represent operators and operands of the expression and edges would represent relationships between them. Algorithm 6.4 (Operator precedence parsing) Data structures Stack: Each stack entry is a record with two fields, operator and operand pointer. Node : Anode is a record with three fields, symbol, left_pointer, and right_pointer. complete: Boolean; Funetions newnode (operator, loperand_pointer, r-operand_pointer) creates a node with appropriate pointer fields and returns a pointer to the Input An expression string enclosed between ‘}’ and ‘4’, 1. TOS := SB ~ 1; complete := false; Push “} on the stack; Set the SSM to point at the second source symbol. 2. If the current source symbol is an operand then { Build a node for the operand and store its pointer in TOS entry } x= newnode (source symbol, null, null); TOS.operand_pointer := x; Advance the SSM by one character;a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.238_ Systems Programming produced by a scanner would consist of a set of tables of lexical units and a sequence of tokens for the lexical units occurring in a source statement, The scanner generated by LEX would be invoked by a parser whenever the parser needs the next token. Accordingly, each semantic action would perform some table building actions and retum a single token. Example 6.25 (Generation of a scanner using LEX) A specification input to LEX consists of four parts. Figure 6.15 shows three parts of a specification. The first part of the specification, which is enclosed by the strings %{ and '}, is used to define symbols that are used in specifying the strings of L. It defines the symbol letter to stand for any upper or lower case letter, and digit to stand for any digit. The second part is enclosed by the strings %% and ‘4%. It contains the translation rules, i.e., string specifications and semantic actions. The third part contains auxiliary routines which ‘can be used in the semantic actions specified in the translation rules. a letter (a-2a-z] digit [0-9] he ah begin {return (BEGIN) ; } end {return(END) ; } " {return (ASGOP) ; } {letter} ({letter}I{digit})* {yylval=enterid(); return(ID) {aigit}+ {yylval=enter-num() ; return (NUM) ; } wh enter_id() { /* enters the id in the symbol table and returns entry number */ } enter-nun() { /* enters the number in the constants table and returns entry number +*/} Figure 6.15 A sample LEX specification As discussed in Section 6.2, a token has the fields lexical class and number in class. LEX allows only the class code of a token to be returned by a semantic action. Hence each operator and keyword is made into a class by itself. The first three translation rules in the specification of Figure 6.15 specify the strings begin, end, and the assignment operator := . Their semantic actions merely return the class codes for these strings. The fourth rule specifies an identifier. Its semantic actions would invoke the id, which would enter the identifier in the symbol table, unless it al- in the table, and return its entry number. The pair (1D, entry #) would form the token for the identifier string. To suit the LEX convention, entry # is put in the global variable yyval, and the class code ID is returned as the value of the calla You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.242 Systems Programming The notation called regular expression provides a concise method of specifying lexical units. A deterministic finite state automaton (DFA) is an abstract machine that is in one of its many states at any time and makes a transition to a specific new state when it is given a specific terminal symbol. If a lexical unit is specified as a regular expression, a DFA could be designed such that it would reach one of its final states on recognizing a lexical unit. Such a DFA can be used as a scanner. A DFA, and hence a scanner, can be automatically generated from a regular expression, LEX is a language processor development tool that generates scanners in this manner. A production in the grammar can be used for two purposes—to derive a string from a nonterminal symbol, and to reduce a string to a nonterminal symbol. Accord- ingly, there are two fundamental approaches to the parsing of a string. Top-down parsing tries to generate a matching string from the distinguished symbol of the grammar, whereas bottom-up parsing focuses on finding whether the string can be reduced to the distinguished symbol. A parse tree of a string represents the sequence of derivations or reductions performed during its parsing; it represents the syntactic structure of the string. A grammar is ambiguous if more than one parse tree can be constructed for a string. Top-down parsing is performed by making derivations according to productions of a grammar until a string that matches an input string can be generated. It is implemented through the steps of prediction making, matching and backtracking. Backtracking makes it inefficient and also compromises its diagnostic capability. A recursive descent parser is a top-down parser that avoids backtracking and its conse- quences. Bottom-up parsing is performed by applying reductions to an input string until it can be reduced to the distinguished symbol of the grammar. The notion of precedence can be used to decide when and how a reduction should be applied. An operator grammar and the notion of operator precedence can be used for efficient parsing of expressions. YACC is a language processor development tool that generates bottom-up parsers from a grammar, TEST YOUR CONCEPTS 1, Classify each of the following statements as true or false: (a) Ifa program uses a variable named alpha, alpha is a terminal symbol. (b) Each valid sentence of a language can be derived from its distinguished symbol. (©) Itis possible to find a sequence of reductions for a string from its abstract syntax tree. ({d) A DFA can have more than one transition out of a state for a source symbol. (©) The notion of precedence can be used to avoid ambiguity in a grammar. (0) A regular expression can be used to specify nested structures. (g) Grammars containing left recursion are amenable to top-down parsing. (h) Backtracking may have to be performed during bottom-up parsing. (i) An operator precedence grammar has fewer precedence relations than an equivalent simple precedence grammar.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.244 Systems Programming (ii) *( + )/ 10. Compare and contrast recursive descent parsing with LL(1) parsing. What grammar forms are acceptable to each of these? 11, Construct an operator precedence matrix for a grammar for expressions containing arithmetic, relational and boolean operators. 12. Given the following operator grammar s bA4 A VaB\e B VaC c VbA v (a) Construct an operator precedence matrix for the operators of the grammar. (b) Give a bottom-up parse for a string containing nine symbols. 13, ‘The keywords if, then and else are operators in the grammar of the if statement given in Problem 5(c). Find whether the operator precedence relations in this grammar are unique. BIBLIOGRAPHY Aho, Sethi and Ullman (1986) discuss automatic construction of scanners. Lewis, Rosenkrantz and Stearns (1976), Dhamdhere (2002) and Aho, Lam, Sethi and Ullman (2007) discuss parsing techniques in detail. 1, Aho, A. V., M. Lam, R. Sethi, and J. D. Uliman (2007): Compiters ~ Principles, Techniques and Tools, second edition, Addison-Wesley, Reading. 2. Barrett, W. A. and J. D. Couch (1977): Compiler Construction, Science Research Associates, Pennsylvania. 3. Dhamdhere, D. M. (2002): Compiler Construction ~ Principles & Practice, second edition, Macmillan India, New Delhi. 4. Fischer, C.N. and R. J. LeBlanc (1988): Crafting a Compiler, Benjamin/Cummings, Menlo Park, California. 5. Gries, D. (1971): Compiler Construction for Digital Computers, Wiley, New York. 6. Lewis, P. M., D. J. Rosenkrantz, and R. E. Stearns (1976): Compiler Design Theory, Addison-Wesley, Reading. 7. Tremblay, J. P. and P. G. Sorenson (1984): The Theory and Practice of Compiler Writing, McGraw-HilCHAPTER 7 Compilers In Chapter 2, we have seen that a compiler bridges the semantic gap between a programming language domain and an execution domain and generates a target program. The target program may be a machine language program or an object module discussed earlier in Chapter 5. The compiler performs two kinds of tasks while bridging the semantic gap: providing diagnostics for violations of programming language semantics in a source program, and generating code to implement meaning of a source program in the execution domain. Diagnostics are provided during scanning, parsing, and semantic analysis of a program. In Chapter 6, we have discussed scanning and parsing, and the LEX and YACC tools that can be used for generating scanners and parsers. The attributes of nonterminal symbols provided in YACC can be used for performing semantic actions that provide diagnostics and generate code. We discuss details of code generation in this chapter. To understand the key issues that need to be addressed during code generation, we first discuss features of programming languages that contribute to the semantic gap between a programming Jangeage domain and an execution domain, These features are: ‘© Data types © Data structures * Scope rules © Control structure We then discuss the techniques that are used to bridge the semantic gap effec- tively. These techniques are grouped into techniques for memory allocation to data structures, for handling scope rules, for generating code for expressions and control structures, and for optimizing the code generated for a program.246. Systems Programming 7.1 CAUSES OF A LARGE SEMANTIC GAP As discussed in Chapter 2, the semantic gap refers to the difference between semantics of two domains. A compiler is concerned with the programming language domain of its source language and the execution domain of its target machine, which is either a host computer or a virtual machine running under some operating system. Hence the semantic gap is caused by those features of the programming language that do not have corresponding features in the target machine. In this section, we discuss four such features and mention how a compiler may bridge the semantic gap caused by them, Note that the output of a compiler is a target program, which may be a machine language program for the target machine mentioned above, or an object module discussed earlier in Chapter 5. Data types Definition 7.1 (Data type) A data type is the specification of (i) values that entities of the type may have, and (ii) operations that may be performed on entities of the type. We refer to these values and operations as legal values and legal operations of a type. Legal operations of a type typically include an assignment operation and a set ‘of data manipulation operations. A programming language provides a few standard data types whose definitions are a part of the language specification, e.g., most lan- ‘guages support the data type boolean, which has the legal values #rve and false and the legal operations and, or, not and assignment. A programming language may also allow a user to define her own data types. Such data types are called user-defined data types. The compiler must check whether variables of a type are assigned legal values and whether variables and values of the type are manipulated through legal operations, and issue diagnostic messages when these requirements are not met. ‘A programming language may specify rules for type conversion, whereby a legal value of one data type can be converted into a legal value of another data type. It would typically permit conversion between numerical types such as integer and real, but may forbid conversion between other types. When an assignment operation or an expression in a program contains values of different numerical types, the compiler should apply the type conversion rules to decide which of the values should be converted to equivalent values in other types. Once these decisions are made, it should use an appropriate instruction of the target machine to implement each of the ‘operations. When an execution domain does not contain values or operations that correspond to those of a data type, the compiler must decide how to represent the value of a type and what instructions or sequences of instructions to use for performing the operations of a type. Examples 7.1 and 7.2 illustrate how a compiler handles data types. In Exam- ple 7.1, the execution environment has features that directly support the values and operations of a type, whereas Example 7.2 illustrates handling of a type where such features are absent.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.252. Systems Programming elements of info. Thus the PL/I program of Example 7.7 may execute slower than the Pascal program of Example 7.6 (see Section 7.5.3.4 for more details). However, the PL/I program provides greater flexibility because the procedure can handle any two-dimensional array irrespective of its dimension bounds. In fact, in different calls it can handle arrays having different dimension bounds. Hence we can draw the following inference: An early binding provides greater execution efficiency whereas a late binding provides greater flexibility in the writing of a program. Static and dynamic bindings Definition 7.3 (Static binding) A static binding is a binding performed before the execution of a program begins. Definition 7.4 (Dynamic binding) A dynamic binding is a binding performed after the execution of a program has begun. Use of static binding leads to more efficient execution of a program than use of dynamic binding. We shall discuss static and dynamic binding of memory in Section 7.5.1 and dynamic binding of variables to types in Chapter 8. 7.3. DATA STRUCTURES USED IN COMPILERS ‘Two kinds of data structures are used during compilation and execution of a program. A search data structure is used to maintain information concerning attributes of entities in the program. Search efficiency is the key criterion in its design. An allocation data structure is used to decide which area of memory should be allocated to an entity. Speed of allocation or deallocation and efficiency of memory utilization are the important criteria in the design of allocation data structures. In Section 2.4 we discussed how symbol tables are designed to provide search efficiency. In this section we discuss two allocation data structures called stack and heap. ‘A compiler uses both search and allocation data structures while compiling a source program. It uses a search data structure to constitute a table of information, such as the symbol table and the constants’ table. If the program being compiled contains nested blocks or nested procedures and functions, it would use an allocation data structure while allocating these tables. During execution, the target code of the program may use either search or allocation data structures in accordance with its logic. The target code would also invoke routines in the run time environment of the programming language. As we shall see in Section 7.5, some of these routines may use allocation data structures while allocating memory to the program’s data, 73.1 Stack ‘The last-in-first-out nature of the stack is useful for handling nested use of entities. The stack data structure and the extended stack model was described earlier in Sec- tion 4.6.6, and its use for expansion of nested macro calls was discussed. As we shalla You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.256 Systems Programming Scope of a variable Entities declared in a block must have unique names. These entities can be accessed only within that block. However, a program may contain a nesting of blocks and entity names may not be unique in the program. Hence the specification of a language contains rules for determining the scope of a variable, which consists of those parts of a program wherein the variable can be accessed. Let a data declaration in block b that uses the name name; create a variable vari. The scope rules of a block-structured language specify that 1. var, can be accessed in any statement situated in block b. 2. var; can be accessed in any statement situated a block b! which is enclosed in b unless b/ contains a declaration using the same name (i.c., using the name name;). A variable declared in block b is called a local variable of block b. A variable of an enclosing block that is accessible within block 6 is called a nonlocal variable of block b. We use the following notation to differentiate between variables created using the same name in different blocks: namepiock.rane : Variable created by a data declaration using the name name in block block.name ‘Thus alphaa, alphag are variables created using the name alpha in blocks A and B. x,y,z : integer; @ : real; Block | lock | Bs? + reali c jysz Block A i,j : integer; Block D Figure 7.4 block structured program Example 7.11 (Local and nonlocal variables of blocks) Consider the block-structured program in Figure 7.4. The variables that are accessible within the various blocks are as follows:a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.260_Systems Programming ‘Code(A) Code(A) | [ Code(a) | [ Codec) | Data(A) Code(B) Code(B) | Code(B) | | Code) | | Codec) Data(B) Data(A) | (A) Code} MII, | atace) | Data(C) i al | J ai i WA @ ) © @ Figure 7.6 (a) Static memory allocation, (b}-(d) Dynamic memory allocation scheme illustrated in Example 7.13. Because entry and exit from procedures fol- low the last-in-first-out rule, automatic dynamic allocation is implemented by using a stack. When a procedure is entered during the execution of a program, a record is created in the stack to contain its variables and a pointer is set to point at this record. Individual variables of the procedure are accessed by using displacements from this pointer. The record is popped off the stack when the procedure is exited. Details of this scheme are discussed later in Section 7.5.3. In program controlled dynamic allocation, a program can allocate or deallocate memory at any time during its execution. Program controlled dynamic allocation is implemented by using the heap data structure, which was discussed in Section 7.3.2. Dynamic allocation provides two significant advantages. Recursion is easy to implement because a recursive call on a function or subroutine leads to allocation of a separate memory area for its new activation, We discuss recursion later in Sec- tion 7.5.3.3. Data structures whose sizes become known only dynamically can also be handled naturally. For example, if an array is declared as a [m,n], where m and n are variables, size of the memory area to be allocated can be determined from the values of mand n, However, in both automatic dynamic allocation and program controlled dynamic allocation, address of the memory area allocated to a variable cannot, be known at compilation time. Hence a variable is accessed through a pointer. This arrangement may make a program using dynamic memory allocation execute slower than a program that uses static memory allocation. 7.8.2 Dynamic Memory Allocation and Access This section discusses only automatic dynamic memory allocation. Itis implemented by adapting the extended stack model discussed earlier in Section 4.6.6.1. Each record in the stack is used to accommodate variables of one activation of a block, hence we call it an activation record (AR). An activation record has the form shown in Figure 7.7. It contains two reserved pointers. As discussed later in this section,a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.264 Systems Programming of a block structured language, when b-use is in execution, b.defn must be active. Hence AR» em Would exist in the stack, and the nonlocal variable nl_var should to be accessed as start address of AR» dem + dnt_vor where dyisar is the displacement of nivar in AR. defy. The compiler needs to set up an arrangement by which the start address of AR), dem can be determined at any time during execution of the generated code. We discuss this arrangement in the following. We use the following terminology for a block and its enclosing blocks: A textual ancestor or static ancestor of block b-use is a block that encloses block b-use. The block immediately enclosing b.use is called its level I ancestor. A level m ancestor is a block that immediately encloses the level (m—~ 1) ancestor. The level difference between b-use and its level m ancestor is m. s.resty ase tepresents the static nesting level of b.use, that is, nesting level of block b.use in the program. ‘Access to nonlocal variables is implemented by using the second reserved pointer in the activation record, which has the address 1(ARB). This pointer is called the static pointer (see Figure 7.7). Step 5 of the actions performed at block entry (see Table 7.1) sets the static pointer in the activation record of a block to point at the activation record of the block’s static ancestor. If a statement in the block accesses a nonlocal variable n/_var declared in a level m ancestor of the block, the compiler would know the value of m from the searches made in the symbol table during name resolution for nl_var (see Example 7.12). Hence it would generate the following code to access ni.var: 1. r:= ARB; where r is some CPU register. 2. Repeat Step 3 m times, 3. r= L(r); i.e., load the static pointer of the activation record to which register r is pointing into CPU register r. 4. Access nl_var by using the address + dat var- a1) Thus the code traces the list formed by static pointers of activation records until the activation record of the level m ancestor is reached. It involves m indirections through static pointers. Example 7.15 illustrates access to nonlocal variables in the the program of Example 7.14. Example 7.15 (Access to nonlocal variables) Figure 7.9 shows memory allocation for the program of Example 7.14. When block B was entered, the static pointer in ARs would have been set to point at the start of AR,. When block C is entered, Step 5 of the actions performed at block entry (see Table 7.1) sets the static pointer in AR¢ to point at the start of ARs. The code generated to access variable x in the statement x := 2; is nowa You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.Compilers 271 MOVER AREG, T ‘COMP AREG, =‘5? BC GT, ERRORRTN Error if i>5 ‘COMP AREG, =(1" BC LT, ERRORRTN Error if i10 ‘COMP AREG, =‘17 BC LT, ERRORATN Error if j RR(node for operator [2)), so it makes a recursive call with node (5) as the parameter. At node [Jalso it decides to visit the right child before the left child. These decisions lead the postfix string cd-ab+/xy+*# +. Thus, the evaluation order is [6], (4), [5]. (2),a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.Compilers 307 Eval; ‘true’ only if b; contains an evaluation of e that is not followed by assignments to any operands of ¢ Modify, : ‘true’ only if b; contains assignment(s) to some operand(s) of e. Eval; and Modify; depend entirely on the computations situated in bj, so they are called local properties of block 6;. Avail.in; and Avail_out; are ‘global’ properties because they depend on properties at predecessors of bj. Following (7.8), the global properties Avail in; and Avail out, are computed by using the following equations Avail.iny =. Tat by in pred (ny) Avail_out 79) Avail-out; = Eval;-+ Avail.in . Modify; (7.10) where ~ is the boolean negation operation and Iqi 4, ix ped () i8 the boolean “and” operation over all predecessors of bj. Equation (7.9) implies condition 2 of (7.8). It ensures that Avail in; would be true only if Avail_out is true for all predecessors of ,. Equation (7.10) implies condition 1 of (7.8). Equations (7.9) and (7.10) are called data flow equations. Every basic block in Gp has a pair of equations analogous to (7.9)-(7.10). Thus, we need to solve a system of simultaneous equations to obtain the values of Avail.in and Avail_out for all basic blocks in Gp. Data flow analysis is the process of solving these equations. Iterative data flow analysis is a simple method of data flow analysis, which assigns some initial values to Avail_in and Avail_out of all basic blocks in Gp and iteratively recomputes them according to Equations (7.9)-(7.10) until they converge onto consistent values. The initial values are Availin; = false if b; is the entry node no true otherwise Avail.out, = true After solving the system of equations (7.9)-(7.10) for all blocks, global common subexpression elimination is performed as follows: An evaluation of expression e is eliminated from a block b; if 1, Avail_in, = true, and 2. The evaluation of e in b; is not preceded by an assignment to any of its operands. Example 7.40 illustrates application of this method. Example 7.40 (Global common subexpression elimination) Available expression analysis, for the control flow graph of Figure 7.36 gives the following results: ab: Avail_in = true for blocks 2,5,6,7,8,9 ‘Avail out = true for blocks 1,2,5,6,7,8,9, 10 xty: Avail in = true for blocks 6,7,8,9 Avail_out = true for blocks 5,6,7,8,9a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.314 Systems Programming 12, Watson, D, (1989): High Level Languages and their Compilers, Addison-Wesley, Reading.CHAPTER 8 Interpreters In Chapter 2 we defined an interpreter as a language processor that bridges the execution gap of a program written in a programming language without generating a target program. This characteristic makes interpreters attractive for use in a program development environment because it avoids the overhead of compilation between successive trial runs of a program. An interpreter can itself be coded in a programming language, which makes it portable. ‘An interpreter performs interpretation of a source program by using the interpretation cycle repeatedly. In each execution of this cycle, it analyzes the next statement of the source program to find its meaning and then performs actions that implement the meaning. This arrangement incurs substantial overhead during interpretation, which makes interpretation slow. An impure interpreter is a hybrid scheme used to speed up interpretation of programs. In this scheme, some elements of compilation are integrated with the interpreter—the source program is processed to build an intermediate code which can be interpreted faster than the source language form of the program. In this chapter we discuss how interpreters perform actions indicated in a source program without generating a target program and how impure interpreters achieve faster interpretation. ‘The Java language environment incorporates many of the considerations discussed in Chapter 1. It uses a virtual machine to provide portability of programs. It provides both an interpreter and a just-in-time compiler to make its working adaptive and provides the capability to download and execute programs over the Internet. We discuss the Java virtual machine, the Java bytecode which is the machine language of the virtual machine, and working of the Java bytecode verifier that provides security even when unknown Java programs are downloaded and executed.316 Systems Programming 8.1 BENEFITS OF INTERPRETATION Benefits of interpreters arise from the fact that the interpreter does not generate a target program. It is simpler to develop an interpreter for a programming language than to develop a compiler for it because interpretation does not involve code generation (see Section 8.2). This simplicity makes interpretation more attractive when programs or commands are not executed repeatedly. Hence interpretation is a popu- lar choice for commands to an operating system or an editor, The user interfaces of many software packages prefer interpretation for similar reasons. Use of interpretation avoids the overhead of compilation of a program. However, during interpretation every statement is subjected to the interpretation cycle, which is expensive in terms of CPU time. Thus, a trade-off exists between compilation of a program and its interpretation, We use the following notation to illustrate this trade-off: f, ) Debug output is written in the file

can contain: trace : Trace of labelled statements executed subtrace : Trace of subprograms called init (): Trace of assignments made to each variable in subchk (): Subscript range check: Report error if subscript in any reference to an array in is out of bounds 2. at Indicated actions are executed when statement bearing is encountered during execution. The possible actions are: trace on : Trace is enabled trace off : Trace is disabled display : Values of variables in the list are written in the debug file Figure 9.4 ‘Trace and dump facilities in Fortran 2. Examining or changing values at a breakpoint 3. Stepping through a program's execution in a statement-by-statement manner. A breakpoint is a place in a program where its execution should be suspended to enable a debug conversation. It can be specified statically by identifying a source statement as in the at command of Figure 9.4, in which case the debug conversation is initiated when the program’s execution reaches the statement. Alternatively, it can be specified through a condition, in which case the debug conversation is initiated whenever the condition is satisfied during the program’s execution. Use of dynamic specification incurs more overhead during the program's execution because the condition would have to be evaluated repeatedly. However, it is the most effective method of capturing certain kinds of errors. For example, if the user finds that a variable xyz has somehow been assigned the “wrong” value 100, it can ask a debug conversation to be initiated when the condition xyz = 100 is satisfied. If she wishes to examine variables’ values in the 50” iteration of a loop, she can specify a condition ‘on the control variable of the loop. ‘Ata breakpoint, the user can examine values of interest, and even change values of variables to facilitate further debugging or to check out a proposed bug fix. To study how the program could have gone wrong, she can set a breakpoint that would occur before the program has assigned the wrong value and then execute the program in a statement-by-statement manner to observe its behaviour. Example 9.6 (Dynamic debugging) Figure 9.5 illustrates use of dynamic debugging facilities supported by many Basic interpreters. The programmer can set breakpoints ata You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.Software Tools 339 the second developer's copy, it would contain changes in function delete info but none in function add_info. Thus changes made by the first developer would be lost. The consistency issue caused by simultaneous modifications to a file is resolved by merging a modified file with the file stored in the file system, rather than by overwriting the file. In Example 9.10 changes made by the first developer would be merged with the original file and changes made by the second developer would be merged with the file resulting from the first merge operation. ‘This way, changes made by the first developer would survive. Inconsistencies can still arise if the developers hhad made changes in the same statements. The system can warn the second developer of this danger when she executes her commit operation. The Source code control system (SCCS) was the first version control system that saw extended use under Unix. Concurrent versions system (CVS) allowed many developers to edit the same file simultaneously; however, it did not use atomic updates. The version control system Subversion (SVN) is widely used in the open source community. It uses atomic updates. 9.2.6 Program Documentation Aids ‘Most programming projects suffer from lack of up-to-date documentation, Auto- matic documentation tools are motivated by the desire to overcome this deficiency. ‘These tools work on the source program to produce different forms of documentation, .g., flow charts, IO specifications showing files and their records, cross reference information, etc. 9.2.7 Design of Software Tools Program preprocessing and instrumentation Program preprocessing techniques are used to support static analysis of programs. Tools generating cross reference listings and lists of unreferenced symbols, test data generators, and documentation aids use this technique. Program instrumentation implies insertion of new statements in a program. The instrumented program is trans- lated using a standard translator. During execution, the inserted statements perform a set of desired functions, Profile and debug monitors typically use this technique. Ina profile monitor, an inserted statement updates a counter indicating the number of times a statement is executed, whereas in a debug monitor an inserted statement checks whether a breakpoint condition is satisfied and opens a debug conversation. Example 9.11 illustrates how program instrumentation is performed. Example 9.11 (Program instrumentation) A debug monitor instruments a program to insert statements of the form call debug. mon (consti); before every statement in the program, where consti is an integer constant indicating the serial number of the statement in the program. During execution of the instru-a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.Software Tools 345 94.1 Testing Assertions ‘A debug assertion is a relation between the values of program variables. It can be associated with a program statement. The debug monitor verifies the assertion when execution reaches that statement. Execution of the program continues if the assertion is fulfilled; otherwise, a debug conversation is opened so that the user can perform actions for locating the cause of the program malfunction. Use of debug assertions eliminates the need to produce voluminous information for debugging purposes. 9.5 PROGRAMMING ENVIRONMENTS: A programming environment is a sofiware system that provides integrated facilities for program creation, editing, execution, testing and debugging. Its use avoids use of distinct software tools during different steps in program development, thereby providing convenience and enhancing programmer productivity. A software environment consists of the following components: 1. A syntax directed editor (which is a structure editor) 2. A language processor—a compiler, interpreter, or both 3. A debug monitor 4, A dialog monitor. All components are accessed through the dialog monitor. The syntax directed editor incorporates a front end for the programming language. As a user keys in his program, the editor performs syntax analysis and converts it into an intermediate representation, typically an abstract syntax tree. The compiler (oF interpreter) and the debug monitor share the intermediate representation. If a compiler is used, it is ac~ tivated after the editor has converted a statement to intermediate representation. The compiler works incrementally to generate code for the statement. This way, execution or interpretation of the program can start immediately after the last statement has been input. The programmer can interrupt execution of the program at any time to either enter the debug mode or return to the editor, modify the program, and resume or restart its execution. The main simplification for the user is the easy accessibility of all functions through the dialog monitor. The system may also provide other program develop- ‘ment and testing functions. For example, it may permit a programmer to execute partially completed program. The programmer can be alerted if an undeclared variable or an incomplete statement is encountered during execution. ‘The programmer can insert necessary declarations or statements and resume execution. This arrangement permits major interfaces in the program to be tested prior to the development of a module. Some programming environments also support reversible execution, whereby a program’s execution can be ‘stepped back’ by one or more statements.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.Software Tools 351 description, the syntax and semantics of commands are specified in a YACC like manner, Thus, the interface is activated when a user types in a command. The event based approach uses a visual model of the interface. A screen with icons is displayed to the user. Selection of an icon by clicking the mouse on it causes an event. The action specified against the event is now performed. ‘The grammar and event description approaches lack the notion of a sequence of actions. The finite state machine approach can efficiently incorporate this notion. ‘The basic principle in this approach is to associate a finite state machine with each window or each icon. Actions are specified on the basis of conditions involving the states of these machines. This approach has the additional power of coordinating the concurrent activities in different windows. In the following we describe two UIMSs using the event description approach. Menulay Menulay is an early UIMS using the screen layout as the basis for the dialog model. The UI designer starts by designing the user screen to consist of a set of icons. A semantic action is specified for each icon. This action is performed when the icon is selected. The interface consists of a set of screens. The system generates a set of icon tables giving the name and description of an icon, and a list of (event, func- tion_id) pairs indicating which application function should be called when an event is selected. Hypercard This UIMS from Apple incorporates object orientation in the event oriented approach. A card has an associated screen layout containing buttons and fields. A button can be selected by clicking the mouse on it. A field contains editable text. Each card has a specific background, which itself behaves like a card. Many cards can share the same background. A hypercard program is thus a hierarchy of cards called a stack. UI behaviour is specified by associating an action, in the form of a HyperTalk script, with each button, field and card. The action for an event is determined by using the hierarchy of cards as an inheritance hierarchy. Hypercard uses an interpretive schematic to implement a UI. 9.7 SUMMARY Users and computational activities need support of various housekeeping functions for maintenance and interfacing of programs. ‘These functions are performed by system programs called software tools. A software tool interfaces a program with the entity from which it draws its input and with the entity that uses its output. In this chapter we discussed various software tools used in program development, and user interfaces. A user can employ a variety of software tools in program development. These352_Systems Programming include familiar tools such as editors and some specialized software tools. A programming environment provides integrated facilities for program creation, editing, execution, testing and debugging. Its use avoids having to use distinct software tools during different steps in program development, thereby providing convenience and enhancing programmer productivity. A test data generator analyzes a program and generates test data that would exercise various execution paths in it, thereby elim- inating the drudgery of testing and making testing more comprehensive. A debug monitor helps in localization of errors by allowing a programmer to halt execution of a program at interesting points and examine values of variables to detect bugs and diagnose their causes. Its use improves the productivity in program debugging. A. profile monitor helps in performance tuning of a program by collecting information concerning the program's behaviour during execution. A source code management system helps to ensure consistency of a program during debugging and modification. A version control system helps in maintenance of a program that has several versions. We discussed the design of editors, debug monitors, and programming environments. A user interface simplifies the interaction of a user with an application by providing means for conducting command dialogs. We discussed principles of command dialog design and structure of user interfaces. ‘TEST YOUR CONCEPTS 1. Classify each of the following statements as true or false: (a) An infeasible path is simply a path that may not be traversed during an execution of a program. (b) To check whether values are used correctly in a loop, one should set a breakpoint ata statement that is executed after exiting the loop. (©) A source code management system is used to decide whether a modification is correct. (d) A debug monitor uses program instrumentation, (e) To handle queries’of an ad hoc kind, one should develop a program generator rather than an interpreter. EXERCISE 9 1. Comment on the statement “Dynamic debugging is easier to implement in interpreters than in compilers”. 2. Comment on whether you would prefer a generative schematic or an interpretive schematic for following purposes: (a) Implementing display commands issued during dynamic debugging (b) Producing a report from a file (c) Writing a general purpose screen handling system (d) Handling data base queries. Give reasons for your answers,PART II OPERATING SYSTEMS Chapter 10: Overview of Operating Systems Chapter 11: Program Management Chapter 12. : Memory Management Chapter 13: File Systems Chapter 14: Security and ProtectionCopyrighted materiala You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.cuapTer 13 File Systems ‘Computer users store programs and data in files so that they can be used conve- niently and preserved across computing sessions. A user expects the file system to provide many facilities—convenient and fast access to files, reliable storage of files, and means to share files with co-workers, The operating system must fulfill these expectations and also ensure efficient use of /O devices. Operating systems organize file management into two components. A file system provides facilities for creating and efficiently manipulating files, for ensuring reliability of files when faults such as power outages or I/O device malfunctions occur, and for specifying how files are to be shared among users. The input output control system (OCS) provides efficient access to data stored on /O devices, and efficient performance of I/O devices. The file system provides different file types, each with its own characteristics, and a directory structure for convenient grouping of related files, It allocates disk space when a file is created or extended. It ensures reliability through two means. Recovery techniques are used to restore files to a consistent state when failures occur. Fault tolerance techniques are used to ensure that the file system can continue its operation even when failures occur. The IOCS implements V/O operations using the DMA, and uses disk scheduling to improve the rate at which a disk can perform /O operations. It uses the techniques of buffering, blocking and caching of data to speed up /O operations in a process. In this chapter we discuss file systems and IOCS in that order.466. Systems Programming 13.1 OVERVIEW OF FILE PROCESSING We use the term file processing to describe the general sequence of operations of opening a file, reading data from the file or writing data into it, and closing the file. Management of file processing activities is structured in two components: @ File system ¢ Input output control system (OCS). A file system provides several file types (see Section 13.2) and operations that can be performed on files of each file type. Each file type provides its own abstract view of data in a file—we call it a logical view of data. The IOCS organizes a file's data on an /O device in accordance with its file type. It is the physical view of the file's data. The mapping between the logical view of the file’s data and its physical view is performed by the IOCS. The IOCS also provides an arrangement which speeds up a file processing activity—it holds some data from a file in memory areas organized as buffers, a file cache or a disk cache. When a process performs a read operation to get some data from a file, the IOCS takes the data from a buffer or a cache if itis present there. This way, the process does not have to wait until the data is read off the VO device that holds the file. Analogously, when a process performs a vrite operation on a file, the IOCS copies the data to be written in a buffer or in a cache. The actual 1/0 operations to read data from an /O device into a buffer or a cache, or to write it from there into an /O device, are performed by the IOCS in the background. 13.1.1 File System and the IOCS A file system views a file as a collection of data that is owned by a user, can be shared by a set of authorized users, and has to be reliably stored over an extended period of time. A file system gives users freedom in naming their files so that a user can give a desired name to a file without worrying whether it conflicts with names of other users’ files; and it provides privacy by protecting against interference by other users. The IOCS, on the other hand, views a file as a repository of data that need to be accessed speedily and are stored on an VO device that needs to be used efficiently. The file system and the IOCS form a hierarchy. The file system provides an interface through which a process can perform open, read/write and close operations on files, Its modules handle protection and sharing of files and pass on read/write requests for file data to the IOCS. The IOCS modules ensure efficient operation of VO devices and efficient file processing in each process. Data and metadata A file system houses two kinds of data—data contained within files, and data used to access files, We call the data within files file data, or simply data. The data used to access files is called control data, or metadata, ¢.g., data in the directory entry of a file. As discussed later in this chapter, metadata also play a role in implementing file operations.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.a You have either reached 2 page thts unevalale fer vowing or reached your ievina tit for his book.SYSTEMS PROGRAMMING _ AU eee eR om eee me ec mee Re CL Programming. It offers in-depth treatment for the fundamental concepts in Ue CM eee Oe CUO CMG ec med SC RU ee Ute ee ee oa a Ears tage Pec Ce cre ceenneeut recy Se eR Me CY ot ee TY et oa ae ale) ce a Moe ae eeu eee Rec ES ec ae SM Me ec eae aa et et en aot Ree eeca aed 1SBN-13 ISBN-10: 0-07 8 Giaw tat Desc : | | | | ll

Uploaded by

Uploaded by

You might also like