Program Generation

Figure 1.6 depicts the program generation activity. The program generator is a software system, which accepts the specification of program to be generated, and generates a program in the target PL. in effect, the program generator introduces a new domain between the application and PL domains (shown in Fig 1.7). We call this the program generator domain. The specification gap is now the gap between the application domain and the program generator domain. This gap is smaller than the gap between the application domain and the target PL domain.

Program Program Program
Specification Generator in target PL

 

Reduction in the specification gap increases the reliability of the generated program. Since the generator domain is close to the application domain, it is easy for the designer or programmer to write the specification of the program to be generated.Specification
gap

Application Program Traget PL Execution
domain generator domain domain
domain

 

The harder task of bridging the gap to the PL domain is performed by the generator. This arrangement also reduces the testing effort. Proving the correctness of the program generator amounts to providing the correctness of the transformation of Fig. 1.6. This would be performed while implementing the generator. To test an application generated by using the generator, it is necessary to only verify the correctness of specification input to the program generator. This is a much simpler task than verifying the correctness of the generated program. This task can be further simplified by providing a good diagnostic (i.e. error indication) capability in the program generator, which would detect inconsistencies in the specification.

Data Structures for Language Processing
The space-time tradeoff in data structures i.e. the tradeoff between memory requirements and the search efficiency of a data structure, is a fundamental principle of systems programming. A language processor makes frequent use of the search operation over its data structures. This makes the design of data structures a crucial issue in language processing activities. Here, we will discuss the data structure requirements of language processors and suggest efficient data structures to meet these requirements.
The data structures used in language processing can be classified on the basis of the following idea –

1. Nature of a data structure – whether a linear or non-linear data structure.
2. Purpose of a data structure – whether a search data structure or an allocation data structure.
3. Lifetime of a data structure – whether used during language processing or during target program execution.

   A linear data structure consists of a linear arrangement of elements in the memory. The physical proximity of its elements is used to facilitate efficient search. However, a linear data structure requires a contiguous area of memory for its elements. This poses problems in situations where the size of a data structure is difficult to predict. In such a situation, a designer is forced to overestimate the memory requirements of a linear data structure to ensure that it does not outgrow the allocated memory. This leads to wastage of memory. The elements of a non-linear data structure are accessed using pointers. Hence the elements need not occupy contiguous areas of memory, which avoids the memory allocation problem seen in the context of linear data structures. However, the non-linear arrangement of elements leads to lower search efficiency.Search data structures are used during language processing to maintain attribute information concerning different entities in the source program. These data structures are characterized by the fact that the entry for an entity is created only once but may be searched for a large number of times. Search efficiency is therefore very important. Allocation data structures are characterized by the fact that the address of the memory area allocated to an entity is known to the user(s) of that entity. Thus no search operations are conducted on them. Speed of allocation or deallocation and efficiency of memory utilization are the important criteria for the allocation data structures.

   Linked Lists and Tree Structured Organizations
   Linked lists and tree-structured organizations are non-linear in nature, that is, elements of the search data structures are not located in adjoining memory areas. To facilitate search, each entry contains one or more pointers to other entries.
   Symbol Other info Pointer ………Pointer

   These organizations have the advantage that a fixed memory area need not be committed to the search structure. The system simply allocates a header element to start with. This elements to the first entry in the linked list or to the root of the tree. Other entries are allocated as and when needed.

   Linked Lists

   Each entry in the linked list organization contains a single pointer field. The list has to be searched sequentially for obvious reasons. Hence its search performance is identical with that of sequential search tables, i.e. ps= l/2 and pu = l.

   Binary Trees

   Each node in the tree is a symbol entry with two pointer fields – the left-pointer and the right-pointer. The following relation holds at every node of the tree: If s is the symbol in the entry, the left pointer points to a subtree containing all symbols < s while the right pointer points to a subtree containing all symbol > s. This relation is used by the search procedure in a manner analogous to Algorithm 2.2. Algorithm 2.4 contains the search procedure. We use the notation x, y to represent field y of node x and the notation (p)*.y to represent field y of the node pointed to by pointer p.Algorithm 2.4 (Binary Tree Search)

   1. current_node_pointer := address of root of the binary tree;
   2. If s= (current_node_pointer)*.symbol, then exit with success;
   3. If s < (current_node_pointer)*.symbol then

   current_node_pointer := (current_node_pointer)*.left_pointer ;
   else current_node_pointer := (current_node_pointer)*.right_pointer ;

   1. If current_node_pointer := nil then

   exit with failure.

   else goto Step 2.

   The best search performance is obtained when the tree is balanced. This performance is identical with that of the binary search table. In the worst case, the tree degenerates to a linked list and the search performance is identical with sequential search.

   Elements of Assembly Language Programming

   An assembly language is a machine dependent, low level programming language, which is specific to a certain computer system (or a family of computer systems). Compared to the machine language of a computer system, it provides three basic features, which simplify programming:
4. Mnemonic operation codes: Use of mnemonic operation codes (also called mnemonic opcodes) for machine instruction eliminates the need to memorize numeric operation codes. It also enables the assembler to provide helpful diagnostics, for example indication of misspelt operation codes.
5. Symbolic operands: Symbolic names can be associated with data or instructions. These symbolic names can be used as operands in assembly statements. The assembler performs memory bindings to these names; the programmer need not know any details of the memory bindings performed by the assembler. This leads to a very important practical advantage during program modification.
6. Data declarations: Data can be declared in a variety of notations, including the decimal notation. This avoids manual conversion of constants into their internal machine representation, for example, conversion of –5 into (11111010)2 or 10.5 into (41A80000)16.

   Statement Format

   An assembly language statement has the following format:
   [Label] <Opcode> <operand spec>[, <operand spec> ..]
   where, the notation [..] indicates that the enclosed specification is optional. If a label is specified in a statement, it is associated as a symbolic name with the memory word(s) generated for the statement. <operand spec> has the following syntax: