Compiler Design | Subject Wise

Statically typed languages

A language is statically typed if the type of a variable is known at compile time. For some languages this means that you as the programmer must specify what type each variable is (e.g Java, C, C++); other languages offer some form of type inference, the capability of the type system to deduce the type of a variable (e.g.: OCaml, Haskell, Scala, Kotlin)

The main advantage here is that all kinds of checking can be done by the compiler, and therefore a lot of trivial bugs are caught at a very early stage.

Examples: C, C++, Java, Rust, Go, Scala

Dynamically typed languages

A language is dynamically typed if the type is associated with run-time values, and not named variables/fields/etc. This means that you as a programmer can write a little quicker because you do not have to specify types every time (unless using a statically-typed language with type inference).

Examples: Perl, Ruby, Python, PHP, JavaScript

Most scripting languages have this feature as there is no compiler to do static type-checking anyway, but you may find yourself searching for a bug that is due to the interpreter misinterpreting the type of a variable. Luckily, scripts tend to be small so bugs have not so many places to hide.

Most dynamically typed languages do allow you to provide type information, but do not require it. One language that is currently being developed, Rascal, takes a hybrid approach allowing dynamic typing within functions but enforcing static typing for the function signature.

• Incremental Compiler is a compiler Compiles only those portion of source code that has been modified.
• Incremental Compiler compiles only those portion of source code that have been modified and without recompiling the whole program it can also compile the additional statements of a program.
• An incremental compiler is a kind of incremental computation applied to the field of compilation. Quite naturally, whereas ordinary compilers make so called clean build, that is, (re)build all program modules, incremental compiler recompiles only those portions of a program that have been modified.

Refer : https://en.wikipedia.org/wiki/Incremental_compiler

Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain generally means the assignment of some value to a variable.

A counterpart of a UD Chain is a Definition-Use Chain (DU Chain), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions.

Both UD and DU chains are created by using a form of static code analysis known as data flow analysis. Knowing the use-def and def-use chains for a program or subprogram is a prerequisite for many compiler optimizations, including constant propagation and common subexpression elimination.

Refer : https://en.wikipedia.org/wiki/Use-define_chain

According to Aho Ullman book : 
PeepHole Optimization is done by examining a sliding window of target instructions(called the peephole) and replacing instruction sequences within the peephole by a faster sequence or shorter.
It can be applied directly after Intermediate Code Generation to improve the intermediate representation.
The code in the peephole need not be contiguous , although some implementations do require this.

So, options(A), option(B) and option(C) are true. Only option(D) is false.

• A compiler is a computer program that transforms code written in a high-level programming language into the machine code. It is a program which translates the human-readable code to a language a computer processor understands (binary 1 and 0 bits)
• An interpreter is a computer program, which coverts each high-level program statement into the machine code. This includes source code, pre-compiled code, and scripts. Both compiler and interpreters do the same job which is converting higher level programming language to machine code. However, a compiler will convert the code into machine code (create an exe) before program run. Interpreters convert code into machine code when the program is run.
• Compiler transforms code written in a high-level programming language into the machine code, at once, before program runs, whereas an Interpreter coverts each high-level program statement, one by one, into the machine code, during program run.
• Compiled code runs faster while interpreted code runs slower.
• Compiler displays all errors after compilation, on the other hand, the Interpreter displays errors of each line one by one.
• Compiler is based on translation linking-loading model, whereas Interpreter is based on Interpretation Method.
• Compiler takes an entire program whereas the Interpreter takes a single line of code.

The output of a lexical analyzer is stream of tokens
-lexical analyzer is the first phase of a compiler
-lexical analyzer read input characters from the source program and produce output as sequence of tokens

Compilers translate the C language into machine code, which can be executed by the CPU. It's often easy to see which bytes of machine code correspond to which statements in your C code. Debuggers use this correspondence when showing how your C code runs.

So the meaning of "a declaration is not an executable statement" is that no machine code corresponds to a declaration. This also means that:

CPU doesn't spend any time to "run" the declaration (but the compiler does spend time to examine it) A visual debugger will "skip" the declaration when running your program step by step

If a compiler is to handle a small amount of data, then the symbol table can be implemented as an unordered list, which is easy to code, but it is only suitable for small tables only. A symbol table can be implemented in one of the following ways:

1. Linear (sorted or unsorted) list
2. Binary Search Tree
3. Hash table

Among all, symbol tables are mostly implemented as hash tables, where the source code symbol itself is treated as a key for the hash function and the return value is the information about the symbol.

The symbol table provides the following operations:
Insert ()
lookup()

Implementation of Symbol table

Following are commonly used data structure for implementing symbol table

List

• In this method, an array is used to store names and associated information.
• A pointer “available” is maintained at end of all stored records and new names are added in the order as they arrive
• To search for a name we start from beginning of list till available pointer and if not found we get an error “use of undeclared name”
• While inserting a new name we must ensure that it is not already present otherwise error occurs i.e. “Multiple defined name”
• Insertion is fast O(1), but lookup is slow for large tables – O(n) on average Advantage is that it takes minimum amount of space.

Linked List :

• This implementation is using linked list. A link field is added to each record.
• Searching of names is done in order pointed by link of link field.
• A pointer “First” is maintained to point to first record of symbol table.
• Insertion is fast O(1), but lookup is slow for large tables – O(n) on average

Hash Table :

• In hashing scheme two tables are maintained – a hash table and symbol table and is the most commonly used method to implement symbol tables..
• A hash table is an array with index range: 0 to tablesize – 1.These entries are pointer pointing to names of symbol table.
• To search for a name we use hash function that will result in any integer between 0 to tablesize – 1.
• Insertion and lookup can be made very fast – O(1).
• Advantage is quick search is possible and disadvantage is that hashing is complicated to implement.

Binary Search Tree :

• Another approach to implement symbol table is to use binary search tree i.e. we add two link fields i.e. left and right child.
• All names are created as child of root node that always follow the property of binary search tree.
• Insertion and lookup are O(log2 n) on average

Refer : http://www.cse.aucegypt.edu/~rafea/csce447/slides/table.pdf

There are generally two types of Parsers:

Top-Down Parsers:
In this Parsing technique we expand the start symbol to the whole program.
Recursive Descent and LL parsers are the Top-Down parsers.

Bottom-Up Parsers:
In this Parsing technique we reduce the whole program to start symbol.
Operator Precedence Parser, LR(0) Parser, SLR Parser, LALR Parser and CLR Parser are the Bottom-Up parsers.

Recursive descent
Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.

Top-Down Parsers:

• In this Parsing technique we expand the start symbol to the whole program.
• In top down parsing, we just start with the start symbol and compare the right side of the different productions against the first piece of input to see which of the productions should be used.
• A top down parser is called LL parser because it parses the input from Left to right, and constructs a Leftmost derivation of the sentence.
• Recursive Descent and LL parsers are the Top-Down parsers.
• A bottom up parser is LR parser with Left to Right parsing performing Right Most Derivation in reverse order (LR)

Peephole optimization is a form of optimization that is done on a segment of generated code.
So, Peephole optimization is form of Local optimization

Constant folding

Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

i = 320 * 200 * 32;

Most compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000).

Constant folding can make use of arithmetic identities. If x is numeric, the value of 0 * x is zero even if the compiler does not know the value of x (note that this is not valid for IEEE floats since x could be Infinity or NotANumber. Still, some languages that favor performance such as GLSL allow this for constants, which can occasionally cause bugs).

Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def" may be replaced with "abcdef".

Simple Example:

In the code fragment The below expression (3 + 5) can be evaluated at compile time and replaced with the constant 8.

int f (void)
{
return 3 + 5;
}
Below is the code fragment after constant folding.
int f (void)
{
return 8;
}

I. All function calls are resolved at compile time in C language -False
II. All function calls are resolved at compile time in C++ language -False

In both C and C++ Language If any function contains branch instruction and branch address are not  know at compile time . Branch instructions address are know at only run time

1st pass: scan label definitions and assign addresses
2nd pass: actual translation (object code)

Pass 1 : define symbols (assign addresses)

• Assign addresses to all statements in the program
• Save the values assigned to all labels for use in Pass 2
• Process some assembler directives
• Table creation , Adding literals to literal table
• Allocate space for literals
• Compute total length of a program

Pass 2 : assemble instructions and generate object program

• Assemble instructions
• Generate data values defined by BYTE, WORD, etc.
• Process the assembler directives not done in Pass 1
• Write the object program and the assembly listing

Finally, assembler must write the generated object code to some output device
- Called object program
- Will be later loaded into memory for execution

In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing.

Other Examples of strength reduction include:

• Replacing a multiplication within a loop with an addition
• Replacing an exponentiation within a loop with a multiplication

Let take an Example:
Exponentiation is replaced by multiplication and multiplication is in return replaced by addition.
The below code is having multiplication operator:

a = 10;
for (j=0; j < X; j++)
{
 Z[j] = a * j;
}

This code can be replaced by the following code by replacing the multiplication with addition.

a = 10;
k = 0;
for (j=0; j < X; j++)
{
 Z[j] = k;
 k = k + a;
}

In peephole optimization a small portion of code need not be contiguous  and it is replaced by another which is expected to be better performing.
This is often applied repeatedly. So, all given options are true in this question.

Refer this link : http://www.cse.iitm.ac.in/~krishna/cs3300/pm-lecture3.pdf

C is the useless variable as there is no production rule which replaces C with a terminal. Thus, it does not derive any non terminal.

Bottom-up parser generates the right-most derivation in reverse order. It constructs the parse tree from the input string to the root and tries to construct the right-most derivation of the specified string backward.

The nodes are :

1. Start
2. 1
3. 2 to 7
4. End

Edges will be 4.
An edge from Start to 1.
An edge from 1 to 2-7.
A self-loop on 2-7
An edge from 2-7 to end.
Hence, Option(B) 44 is the correct answer.

Terminal table is a permanent database that has an entry for each terminal symbol.such as arithmetic operators, keywords, punctuation characters such as ';' , ','etc Fields: Name of the symbol.
option(B) is the correct answer

Total number of token = 8

1. printf
2. (
3. "A%B="
4. ,
5. &
6. i
7. )
8. ;

In option (B), Multiplication operation is replaced with Shift Operator . It reduce the operator strength because shift operator is less expensive than multiplication operation.
Here, most suitable option is 2) Replace P × 16 by P ≪ 4

In loop jamming, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other. It reduces the time taken to compile the many number of loops.

Example:

Initial Code:

for(int i=0; i<5; i++)
  a = i + 5;
for(int i=0; i<5; i++)
  b = i + 10;

Using Loop jamming above code converted into below Optimized code :

for(int i=0; i<5; i++)
{
  a = i + 5;
  b = i + 10;
}

In loop jamming, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other. It reduces the time taken to compile the many number of loops.

Example:

Initial Code:

for(int i=0; i<5; i++)
  a = i + 5;
for(int i=0; i<5; i++)
  b = i + 10;

Using Loop jamming above code converted into below Optimized code :

for(int i=0; i<5; i++)
{
  a = i + 5;
  b = i + 10;
}

External subroutines are routines that are created and maintained separately from the program that will be calling them.

Refer : http://faculty.cs.niu.edu/~byrnes/csci360/notes/360ext.htm

• YACC stands for Yet Another Compiler Compiler.
• YACC is an LALR(1) ( LookAhead, Left-to-right, Rightmost derivation producer with 1 lookahead token) parser generator
• YAAC builds up LALR(1)  parsing table.

Micro program is the set of instructions indicating the primitive operations in a system
Micro program is a set of microinstructions that defines the individual operations that a computer carries out in response to a machine-language instruction

Let the grammar is:
A → BC
B → aa
C → bb
now let the string w = aabb then
A  → BC(reduction 3)
     → aaC (reduction 2)
     → aabb (reduction 1)
n = 4 and number of productions are 3 so n - 1

Note :
There is a mistake in question it is not supposed to have A -> a, even though that is not a unit production. Given key is n-1.

• Lexical Analysis is the first phase of the compiler also known as a scanner. It converts the High level input program into a sequence of Tokens.
• A lexical token is a sequence of characters that can be treated as a unit in the grammar of the programming languages.

Example of tokens:

• Type token (id, number, real, . . . )
• Punctuation tokens (IF, void, return, . . . )
• Alphabetic tokens (keywords)

Keywords; Examples-for, while, if etc.
Identifier; Examples-Variable name, function name, etc.
Operators; Examples '+', '++', '-' etc.
Separators; Examples ',' ';' etc.

linking loader : A loader which combines the functions of a relocating loader with the ability to combine a number of program segments that have been independently compiled into an executable program.

1. Statement I - True Bottom up and top down parser are linear time parsers which take O(n) time to parse the string. i.e, only one scan of input is required
   -LL(1) and LR parsers takes O(n)
   -CFG is O(n³)
   -LL and LR parsers are linear time parsers.
   Refer : https://www.csee.umbc.edu/courses/331/fall11/notes/04/04cparsing.ppt.pdf
2. Statement II - False It cannot be implemented with static storage allocation. It needs dynamic memory allocation.
3. Statement III - True Every s-attributed SDT is L-attributed SDT (vice-versa need not be true)
   S-attributed SDT follows bottom up approach. Hence L-attributed SDT which are also S-attributed can be solved by bottom up parsing
   Refer : http://www.cs.sunysb.edu/~cse304/Fall09/Lectures/attributes-handout.pdf
4. Statement IV - True  Code improving transformation can be performed at both source language and intermediate code level.

A single pass assembler scans the program only once and creates the equivalent binary program

For predictive-parsing, grammar should be:

• Free from ambiguity
• Free from left recursion
• Free from left factoring

Since given grammar can have infinite parse trees for string ‘ε’, so grammar is ambiguous, and also S → SS has left recursion. so it can not have predictive parser.

option(C) is also satisfying but option(D) is a better answer hear. Because we have standard procedure for removing left-recursion but ambiguity is not easy to remove.

Pseudo Instructions are special commands to the assembler about the positioning of the program, the address the program should presumed to be assembled at, the name of the module, data declarations, the title and printing options for the program, defining and calling macros, macro looping and test, and end of source code. Unless a machine instruction is issued, these do not generate executable code.

Refer : https://en.wikibooks.org/wiki/360_Assembly/Pseudo_Instructions

The given grammar is ambiguous as there are two possible leftmost derivations for string “c”.

First Leftmost Derivation
S → A
A → c

Second Leftmost Derivation
S → B
B → c

An Ambiguous grammar can neither be LL(1) nor LR(1)

Constant folding
Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

i = 320 * 200 * 32;

Most compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000).

Constant folding can make use of arithmetic identities. If x is numeric, the value of 0 * x is zero even if the compiler does not know the value of x (note that this is not valid for IEEE floats since x could be Infinity or NotANumber. Still, some languages that favor performance such as GLSL allow this for constants, which can occasionally cause bugs).

Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def" may be replaced with "abcdef".

Simple Example:

In the code fragment The below expression (3 + 5) can be evaluated at compile time and replaced with the constant 8.

int f (void)
{
return 3 + 5;
}
Below is the code fragment after constant folding.
int f (void)
{
return 8;
}

Loop Optimization
Loop Optimization is the process of increasing execution speed and reducing the overheads associated with loops
Decreasing the number of instructions in an inner loop improves the running time of a program even if the amount of code outside that loop is increased.

Loop Optimization Techniques -

1. Frequency Reduction (Code Motion)
2. Loop Unrolling:
3. Loop Jamming

 

The structure and format of data are defined using syntax. Semantics defines how a particular pattern to be interpreted, and what action is to be taken based on that interpretation. In programming languages, syntax of the instructions plays a vital role in designing of the program.

Basic Blocks

Basic block is a set of statements that always executes in a sequence one after the other.

The characteristics of basic blocks are :

• They do not contain any kind of jump statements in them.
• There is no possibility of branching or getting halt in the middle.
• All the statements execute in the same order they appear.
• They do not lose lose the flow control of the program.

Flow Graphs

• A flow graph is a directed graph with flow control information added to the basic blocks.
• The basic blocks serve as nodes of the flow graph.
• There is a directed edge from block B1 to block B2 if B2 appears immediately after B1 in the code

Top-down parser generates the left-most derivation. It constructs the parse tree from left to right and constructs the left-most derivation of the specified sentence.

Syntax Directed Definition

• An SDD is a CFG with attributes and rules.
  – Attributes are associated with grammar symbols.
  – Rules are associated with productions.
• An SDD specifies the semantics of productions.
  – It does not enforce a specific way of achieving the semantics

Syntax Directed Translation

• An SDT is done by attaching rules or program fragments to productions.
• The order induced by the syntax analysis produces a translation of the input program

Role of SDT

•  To associate actions with productions
•  To associate attributes with non-terminals
•  To create implicit or explicit syntax tree
•  To perform semantic analysis

The output of a lexical analyzer is stream of tokens
-lexical analyzer is the first phase of a compiler
-lexical analyzer read input characters from the source program and produce output as sequence of tokens

Operator which is at lower level in the grammar is termed to have higher precedence.

• * and + have least priority because  are present at the top most level .
• * and + have equal precedence because they are same level .
• '-' have higher precedence than '+' and '*' because is present at the bottom most level

Let us take an example 6*7-8 when we draw parse tree according to grammar

      E
   /  |  \
  E   *   F
  |     / | \
  F    F  -  F
  |    |     |
id(6) id(7) id(8)

As we can see that first ‘- ‘ will be evaluated then ‘ * ‘ is evaluated
Thus, ‘ – ‘ has higher precedence then *.

So correct answer is option(B)

Number of Tokens are 10 for printf("i=%d, &i=%x", i, &i);

1. printf
2. (
3. "i=%d, &i=%x"
4. ,
5. i
6. ,
7. &
8. i
9. )
10. ;

WhiteSpaces will be removed by the lexical analyzer from the source code.

Number of Tokens are 9 for printf("i=%d, &i=%x", i&i);

1. printf
2. (
3. "i=%d, &i=%x"
4. ,
5. i
6. &
7. i
8. )
9. ;

Operator precedence parser can be constructed from a grammar called Operator grammar. These grammars have the property that no production on right side is ɛ or has two adjacent non-terminals.
So, A → BC and A → ε are not allowed.
Thus, Correct option is (D).

LL parse and Recursive Descent Parse is a Top Down Parsers.

• YACC stands for Yet Another Compiler Compiler.
• YACC is an LALR(1) ( LookAhead, Left-to-right, Rightmost derivation producer with 1 lookahead token) parser generator
• YAAC builds up LALR(1)  parsing table.

(A). Canonical LR is the most powerful parser as compared to other LR parsers. Order is
LR(0) < SLR(1) < LALR(1) < CLR(1)

(B) . The grammar generated by LP(Linear Precedence) are CFG but not implying All CFG are LP.

(C) . Every SLR grammar is unambiguous but not every unambiguous grammar is SLR

(D) . LR(k) has a k-look ahead which can always see ahead the input in order to avoid backtracking and LR(k) is the most general non back tracking shift reduce parsing method

Recursive Descent Parsing

• Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right.
• It uses procedures for every terminal and non-terminal entity.
• This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking.
• A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.
• This parsing technique is regarded recursive as it uses context-free grammar which is recursive in nature.

LL parser is a Top Down Parsers.

Machine independent optimizations

• Enable other transformations
  -Procedure inlining, cloning, loop unrolling
• Eliminate redundancy
  -Redundant expression elimination
• Eliminate useless and unreachable code
  -Dead code elimination
• Specialization and strength reduction
  -Constant propagation, peephole optimization
• Move operations to less-frequently executed places
  -Loop invariant code motion
• Other Machine Independent optimization are
  -Loop optimization
  -Redundancy elimination
  -Folding
  -Strength reduction
  -Deadlock elimination

Machine dependent (scheduling) transformations

•  Take advantage of special hardware features
  - Instruction selection, prefetching
•  Manage or hide latency, introduce parallelism
  - Instruction scheduling, prefetching
•  Manage bounded machine resources
  - Register allocation
• Other Machine Dependent optimization are
  -Register allocation
  -Use of addressing modes
  -Peephole optimization

The containment rules are the following:

• Every LR(0) grammar is also SLR(1), but not all SLR(1) grammars are LR(0).
• Every SLR(1) grammar is also LALR(1), but not all LALR(1) grammars are SLR(1).
• Every LALR(1) grammar is also LR(1), but not all LR(1) grammars are LALR(1).
• Every LL(1) grammar is also LR(1), but not all LR(1) grammars are LL(1).
• Every LL(0) grammar is also LR(0), SLR(1), LALR(1), LR(1), and LL(1)

typo mistake***option(A) : Reduces the space of the code****

Code Optimization
Code Optimization phase removes the unnecessary code line and arranges the sequence of statements to speed up the execution of the program without wasting resources. The main goal of Code Optimization phase is to improve on the intermediate code to generate a code that runs faster and occupies less space.

The main functions of Code Optimization phase are:

• Code Optimization helps you to establish a trade-off between execution and compilation speed
• It Improves the running time of the target program
• Generates streamlined code still in intermediate representation
• Removing unreachable code and getting rid of unused variables
• Removing statements which are not altered from the loop

Let us consider the following example code

a = intofloat(10)
b = c * a
d = e + b
f = d

Then Code Optimizer will take above code and transformed it into below code

b = c * 10.0
f = e+b

So, Both option (A) and option(B)  are correct answers.

• Syntax analysis or parsing is the second phase of a compiler.
• Syntax Analysis is also called as parsing.
• Syntax analysis takes the token produced by lexical analysis as input and generates a parse tree (or syntax tree).
• In this phase, token arrangements are checked against the source code grammar, i.e. the parser checks if the expression made by the tokens is syntactically correct.

The linker resolves symbol references by associating each ref with exactly one symbol definition from the symbol tables of its input relocatable obj files. Symbol resolution is easy for references to local variables that are defined in the same module as the ref.

Resolving ref to global symbols is trickier. When the compiler encounters a symbol (either a var or func name) that is not defined in the current module, it assumes that it is defined in some other module, generally a linker symbol table entry, and leaves it for the linker to handle. If the linker is unable to find a def for the referenced symbol in any of its input modules, it prints an error msg and terminates.

A language translator is a program which is used to translate an input program written in one programming language into another programming language. Language processor is also called a language translator.

A program written in any high-level programming language is called the Source code or program. To convert the source code into machine code is called the object code or program. A Translator translates the source program into the object program that the computer can understand and execute.

In programming Language processors are three types:

1. Assembler
2. Interpreter
3. Compiler

Assembler is a translator which is used to translate the assembly language code into machine language code.

Interpreter converts the source program written in high level language into machine languages.
An interpreter converts each statement of the program line by line into machine code.

Compiler : The purpose of compiler is same as interpreter but unlike interpreters which translate the source program line by line, compiler are the translators, which translate the entire program into machine codes.

Synthesized attributes follows bottom up parsing evaluation.

Example :
X -> Y | Z  i attribute is there in X,Y and Z
X.i = f( Y.i , Z.i ) means parent is taking attribute from there children

Bottom Up Parsers
LR( 0 ) , SLR( 1 ) , LR( 1 ) , LALR( 1 ) and Operator Precedence

Top Down Parsers
Non Recursive descent ( LL( 1 ) ) and Recursive descent

LR Parsers which are generated from LR grammar are also coming under bottom up parsing fashion Therefore option(C) is correct.

Theorem : A context free grammar G=(V​ _T​ , V_{​ N}​ , S,P) is LL(1) if and if only if for every nonterminal A and every strings of symbols ⍺,β such that ⍺≠β and
A → ⍺,β we have
1. First(⍺) ∩ First (β) =Θ.
2. If ⍺ *⇒ ε then First(β) ∩ Follow(A)= Θ.

Condition 2 is not required If grammar is epsilon free

Refer : https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/Syntax.html/node14.html

Functions of Semantic Analysis:

• Type Checking 
  Ensures that data types are used in a way consistent with their definition.
• Label Checking
  A program should contain labels references.
• Flow Control Check 
  Keeps a check that control structures are used in a proper manner.(example: no break statement outside a loop)
• Scope resolution
• Array-bound checking

Semantics errors that the semantic analyzer is expected to recognize:

• Type mismatch
• Undeclared variable
• Reserved identifier misuse.
• Multiple declaration of variable in a scope.
• Accessing an out of scope variable.
• Actual and formal parameter mismatch.

• Lexical Analysis is the first phase of the compiler also known as a scanner. It converts the High level input program into a sequence of Tokens.
• A lexical token is a sequence of characters that can be treated as a unit in the grammar of the programming languages.

Example of tokens:

• Type token (id, number, real, . . . )
• Punctuation tokens (IF, void, return, . . . )
• Alphabetic tokens (keywords)

Keywords; Examples-for, while, if etc.
Identifier; Examples-Variable name, function name, etc.
Operators; Examples '+', '++', '-' etc.
Separators; Examples ',' ';' etc.

• Parser is a part of compiler and responsible for syntax recognition.
• Scanner is a part of compiler that used by lexical analyzer it takes input as stream of characters and produce output as a stream of words along with their associated syntactic categories
• In Semantic analysis consistency and definition of syntax is checked.
• An optimizer is used improve the IR program and an IR-to-IR transformer that tries to improve the IR program in same way(intermediate representation)

Scalability is the capacity of distributed system to adopt the increased load in Distributed System

False-Lexical Analysis is specified by context-free grammars and implemented by pushdown automata
Lexical Analysis is specified by regular grammar and implemented by finite automata
False-Syntax Analysis is specified by regular expressions and implemented by finite-state machine
Syntax Analysis uses context free grammar which uses push down automata

Strength Reduction : Replace expensive operations with less expensive but equivalent operations.
For Example : Multiplication is more expensive operation than addition.
Shift operation is less expensive operation than Multiplication/Division.

In option (B), Multiplication operation is replaced with Shift Operator . It reduce the operator strength because shift operator is less expensive than multiplication operation.
Here, most suitable option is 2) Replace P × 32 by P ≪ 5

linker is a computer program that takes one or more object files generated by a compiler and combines them into one executable program, library file or another object file


Principles tasks of the linker are:

• Resolve external references among separately compiled program units.
• Relocate code and data relative to the beginning of the program.

-Assembler translate assembly language to machine code.
-Loader enforces access-control restrictions on system libraries

In loop jamming, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other. It reduces the time taken to compile the many number of loops.

Example:

Initial Code:

for(int i=0; i<5; i++)
  a = i + 5;
for(int i=0; i<5; i++)
  b = i + 10;

Using Loop jamming above code converted into below Optimized code :

for(int i=0; i<5; i++)
{
  a = i + 5;
  b = i + 10;
}

Dynamic linking is used to reduce space consumption on disk and memory and it also reduce the cost of software update.
I. Reduction in overall program execution time - True
II. Reduction in overall space consumption in memory - False
III. Reduction in overall space consumption on disk- False
IV. Reduction in the cost of software updates- False

Option(A) : True
The grammar S → a Sb |bSa|SS|∈, where S is the only non-terminal symbol and ∈ is the null string, is ambiguous grammar because we are able to derive two different parse trees for string "aabb" therefore the given grammar is ambiguous.
Consider the string ="aabb"
Parse Tree 1 :
Parse Tree 2:


Option(A) : False
LALR is more powerful then SLR.

Option(D) : True
An LL(1) parser is a top-down parser.

Option(D) : True
YACC tool is an LALR(1) parser generator.

Loop unrolling

• Loop unrolling is a loop transformation technique that helps to optimize the execution time of a program.
• Loop unrolling basically remove or reduce iterations.
• Loop unrolling increases the program’s speed by eliminating loop control instruction and loop test instructions.

Let us consider an example :
Program 1 without loop unrolling:

#include
int main(void)
{
 for (int i=0; i<5; i++)
  printf("Hello\n"); //print hello 5 times
 return 0;
}

Output :

1. Hello
2. Hello
3. Hello
4. Hello
5. Hello

This program uses loop unrolling.

#include
int main(void)
{
 // unrolled the for loop in program 1
 printf("Hello\n");
 printf("Hello\n");
 printf("Hello\n");
 printf("Hello\n");
 printf("Hello\n");
 return 0;
}

Output :

1. Hello
2. Hello
3. Hello
4. Hello
5. Hello

• The translator which performs macro calls expansion is called Macro pre-processor .
• A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so.
• Macro processors have been used for language expansion (defining new language constructs that can be expressed in terms of existing language components), for systematic text replacements that require decision making, and for text reformatting (e.g. conditional extraction of material from an HTML file).
• A Dynamic linker is the part of an operating system that loads and links the shared libraries.
• C preprocessor is a micro processor that is used by compiler to transform your code before compilation. It is called micro pre-processor because it allows us to add macros.

option(A) : True
LALR parser is Bottom Up parse

option(B) : False
We don't have any RL(1) parsing. We have LR(1) parsing algorithm. Incase of LR(1) parsing L stands for left-to-right scanning of the input string and R signifies that we will get a Rightmost Derivation.

option(C) : True
LR parser is Bottom Up parser.

option(D) : True
In LL(1), the 1 indicates that there is a one – symbol look – ahead.

option A,B,C are included.

• Code optimization is responsibility of System Programmers
• Optimization can be performed by automatic optimizers, or programmers.
• An optimizer is either a specialized software tool or a built-in unit of a compiler (the so-called optimizing compiler).
• Modern processors can also optimize the execution order of code instructions.

option A,B,C are included.

• In two pass assembler the symbol table is used to store memory locations
• The symbol table contains information to locate and relocate symbolic definitions and references. The assembler creates the symbol table section for the object file. It makes an entry in the symbol table for each symbol that is defined or referenced in the input file and is needed during linking.
• The symbol table is then used by the link editor during relocation. The symbol table's section header contains the symbol table index for the first non-local symbol.
• Instead of using an absolute memory address it uses a symbolic address.

Top-Down Parsers:

• In this Parsing technique we expand the start symbol to the whole program.
• In top down parsing, we just start with the start symbol and compare the right side of the different productions against the first piece of input to see which of the productions should be used.
• A top down parser is called LL parser because it parses the input from Left to right, and constructs a Leftmost derivation of the sentence.
• Recursive Descent and LL parsers are the Top-Down parsers.
• A bottom up parser is LR parser with Left to Right parsing performing Right Most Derivation in reverse order (LR)

• A general-purpose macro processor or general purpose preprocessor is a macro processor that is not tied to or integrated with a particular language or piece of software.
• A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so.
• Macro processors are often embedded in other programs, such as assemblers and compilers. Sometimes they are standalone programs that can be used to process any kind of text.
• Macro processors have been used for language expansion (defining new language constructs that can be expressed in terms of existing language components), for systematic text replacements that require decision making, and for text reformatting (e.g. conditional extraction of material from an HTML file).

option A,B,C are included.

option(A) : Correct

• lexical analyzer is the first phase of a compiler
• lexical analyzer read input characters from the source program and produce output as sequence of tokens

option(B) : Correct

• Syntax analysis or parsing is the second phase of a compiler.
• Syntax Analysis is also called as parsing.
• Syntax analysis takes the token produced by lexical analysis as input and generates a parse tree (or syntax tree).
• In this phase, token arrangements are checked against the source code grammar, i.e. the parser checks if the expression made by the tokens is syntactically correct.

option(C) : Wrong

• Semantic means meaning of language. syntax analysis phase only cares about the correct syntax of the program.
• Programs are logically valid or not, this part is done by semantic analysis phase.

Difference between static and dynamic binding 

• Static binding happens at compile-time while dynamic binding happens at runtime.
• Binding of private, static and final methods always happen at compile time since these methods cannot be overridden.
• In Static binding All information needed to call a function is known at compile time.
• In dynamic binding All information need to call a function come to know at run time.
• When the method overriding is actually happening and the reference of parent type is assigned to the object of child class type then such binding is resolved during runtime.
• The binding of overloaded methods is static and the binding of overridden methods is dynamic.

Symbol table can be used for
(A) Checking type compatibility
(B) Suppressing duplication of error message
(C) Storage allocation

• A compiler for a high-level language that runs on one machine and produces code for a different machine is called cross compiler.
• A one-pass compiler is a compiler that passes through the source code of each compilation unit only once. traverses the program only once.
• A multi-pass compiler or two pass compiler is a type of compiler that processes the source code or abstract syntax tree of a program several times.
• A one-pass compilers is faster than multi-pass compilers.

In LR (K) , "K" indicate number of lookahead and can be any finite value.

Peephole optimization is a form of optimization that is done on a segment of generated code.
So, Peephole optimization is form of Local optimization
**Local optimization is correct answer**

Terminal table is a permanent database that has an entry for each terminal symbol.such as arithmetic operators, keywords, punctuation characters such as ';' , ','etc Fields: Name of the symbol.
option(B) is the correct answer

Tasks done in parsing are :

• Check the validity of a source string
• Determine the syntactic structure of a source string
• Syntax analysis takes the token produced by lexical analysis as input and generates a parse tree (or syntax tree).
• In this phase, token arrangements are checked against the source code grammar, i.e. the parser checks if the expression made by the tokens is syntactically correct.

• YACC stands for Yet Another Compiler Compiler.
• YACC is an LALR(1) ( LookAhead, Left-to-right, Rightmost derivation producer with 1 lookahead token) parser generator
• YAAC builds up LALR(1)  parsing table.

• The action of parsing the source program into the proper syntactic classes is known as lexical analysis
• lexical analyzer is the first phase of a compiler
• The output of a lexical analyzer is stream of tokens
• lexical analyzer read input characters from the source program and produce output as sequence of tokens

Difference between static and dynamic binding 

• Static binding happens at compile-time while dynamic binding happens at runtime.
• Binding of private, static and final methods always happen at compile time since these methods cannot be overridden.
• In Static binding All information needed to call a function is known at compile time.
• In dynamic binding All information need to call a function come to know at run time.
• When the method overriding is actually happening and the reference of parent type is assigned to the object of child class type then such binding is resolved during runtime.
• The binding of overloaded methods is static and the binding of overridden methods is dynamic.

Shift-Reduce parsers perform the following

• Shift step that advances in the input stream by one symbol and
• Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.

• True : Canonical LR parser is LR (1) parser with single look ahead terminal
• True : All LR(K) parsers with K > 1 can be transformed into LR(1) parsers.

In a two-pass assembler, symbol table is generated in first pass but it need two pass to scan whole source file. While one pass assembler scan whole file in one go.

Following tasks performed in first pass

• It allocates space for the literals.
• It computes the total length of the program.
• It builds the symbol table for the symbols and their values.

• A debugger is a computer program used by programmers to test and debug a target program
• Debugger allows to set breakpoints, execute a segment of program and display contents of register. One of the Debugger name is GDB used under Unix.

Refer 1 : https://www.cs.utah.edu/~germain/PPS/Topics/debugging_programs.html
Refer 2 : https://www.cs.cmu.edu/~gilpin/tutorial/

Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.

Following are the steps to convert an arbitrary CFG to LL(1) grammar:

1. Remove ambiguity (by taking care of precedence and associatively)
2. Remove Left Recursion (This will come when you remove ambiguity)
3. Make grammar deterministic by Left factoring (In case occur) To convert CFG to LL(1), which is top down parser.

If the grammar is ambiguous, is left recursive and has left factoring, then, it is not a LL(1). For LL(1) all the 3 should be removed.

For predictive-parsing, grammar should be:

• Free from ambiguity
• Free from left recursion
• Free from left factoring

Since given grammar can have infinite parse trees for string ‘ε’, so grammar is ambiguous, and also S → SS has left recursion. so it can not have predictive parser.

option(C) is also satisfying but option(D) is a better answer hear. Because we have standard procedure for removing left-recursion but ambiguity is not easy to remove.

The given grammar is ambiguous as there are two possible leftmost derivations for string “c”.

First Leftmost Derivation
S → A
A → c

Second Leftmost Derivation
S → B
B → c

An Ambiguous grammar can neither be LL(1) nor LR(1)

A grammar is said to be ambiguous if there exists more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string

Here both Grammar G1 and G2 are ambiguous as For G1 we can generate more than one parse tree for the same string “ababa” and for G2 we can also generate more than one parse the for the string ” ab ” so both G1 and G2 is also ambiguous grammars.

Bottom-up parser generates the right-most derivation in reverse order. It constructs the parse tree from the input string to the root and tries to construct the right-most derivation of the specified string backward.

**Correct answer is option(B): Code optimization using cheaper machine instructions.**

• In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations.
• Classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing.

Strength reduction examples

• Instead of Multiplication by 2 we can use left shift by 2
• Instead of division by 2 we can use right shift by 2

Operator which is at lower level in the grammar is termed to have higher precedence.

• * and + have least priority because  are present at the top most level .
• * and + have equal precedence because they are same level .
• '-' have higher precedence than '+' and '*' because is present at the bottom most level

Let us take an example 6*7-8 when we draw parse tree according to grammar

      E
   /  |  \
  E   *   F
  |     / | \
  F    F  -  F
  |    |     |
id(6) id(7) id(8)

As we can see that first ‘- ‘ will be evaluated then ‘ * ‘ is evaluated
Thus, ‘ – ‘ has higher precedence then *.

So correct answer is option(B)

Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.

Following are the steps to convert an arbitrary CFG to LL(1) grammar:

1. Remove ambiguity (by taking care of precedence and associatively)
2. Remove Left Recursion (This will come when you remove ambiguity)
3. Make grammar deterministic by Left factoring (In case occur) To convert CFG to LL(1), which is top down parser.

If the grammar is ambiguous, is left recursive and has left factoring, then, it is not a LL(1). For LL(1) all the 3 should be removed.

Canonical LR is most powerful parsing method
LR > LALR > SLR

S1 is correct and S2 is correct.

• SLR parser uses the follow information to construct the SLR parse table.
• LR and LALR uses the look-ahead symbol to generate the parse table
• LR is powerful than SLR and LALR. Therefore, LR will be able to recognize large class of CFG than the SLR and LALLR

In Top-down parser takes input from Left to right constructing leftmost derivation of the sentence.

• Top-down parser   - Leftmost derivation
• Bottom-Up parser - Reverse of rightmost derivation

Interpreter converts the source program written in high level language into machine languages. An interpreter converts each statement of the program line by line into machine code.

Platform independence means that the same program works on any platform(operating system like windows, linux, unix) without needing any modification.

• A grammar is said to be ambiguous if there exists more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string
• Here both Grammar G1 and G2 are ambiguous as For G1 we can generate more than one parse tree for the same string “aab” and for G2 we can also generate more than one parse the for the string ” abab ”,"baba" etc. So both G1 and G2 is also ambiguous grammars.

**Correct answer : option(D) = aSb**

S→Sα1 ∣ Sα2 ∣ β1 ∣ β2
Given grammar can generate : {β1,β2,β1α1,β1α2,β2α1,β2α2,β2α1α2.........., ...., ,,,etc}
We can generate only {β1,β2} in option(A).
In option(B) there is no terminating point string containing {α1,α2}
option(C) also not correct because it can generate only {β1,β2}
option(D) can generate all the string generate by the given grammar.

Method 2 : 
S→Sα1 ∣ Sα2 ∣ β1 ∣ β2,
Apply left recursion  then we get
S → β1 ∣ β2 ∣ β1A ∣ β2A, A → α1A ∣ α2A ∣ λ
Therefore, Option(D) S→β1 ∣ β2 ∣ β1A ∣ β2A, A → α1A ∣ α2A ∣ λ

Discuss this question in Discussion forum : https://academyera.com/ugc-net-cs-2013-june-paper-2-parsers-2

Writing a macro is another way of ensuring modular programming in assembly language.

• A macro is a sequence of instructions, assigned by a name and could be used anywhere in the program.
• In NASM, macros are defined with %macro and %endmacro directives.
• The macro begins with the %macro directive and ends with the %endmacro directive.

Macro definition syntax :

%macro macro_name number_of_params
<macro body>
%endmacro

Where, number_of_params specifies the number parameters, macro_name specifies the name of the macro.

The macro is invoked by using the macro name along with the necessary parameters. When you need to use some sequence of instructions many times in a program, you can put those instructions in a macro and use it instead of writing the instructions all the time.

• Grammar of the programming is checked at syntax phase of compiler
• Type checking is done during semantic analysis phase and syntax analysis is used to generate parse trees.
  Example : int a = "world" . Hence false
• logical errors will checked in semantic analysis

A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so. Macro processors are often embedded in other programs, such as assemblers and compilers. Sometimes they are standalone programs that can be used to process any kind of text.

Parse tree follows below points always:

• All leaf nodes have to be terminals.
• All interior nodes have to be non-terminals.
• In-order traversal gives original input string.
• Parse tree is always following in-order traversal. It visits left, root and right

(A+B)∗C

Given question is wrong they given wrong order as Two operator between operands . But according to there intention we are assuming ** is single(*) and there is no |* these are useless symbols

• 3 – 2 * 4 $ | * 2** 3
• (3 – 2) * 4 $ | * 2** 3
• ((3 – 2) * 4) $ | * (2** 3)
• (((3 – 2) * 4) $ | * (2** 3))
• (((3 - 2) *) 4 $ | * (2**3))
• (((1) *) 4 $ | * (2**3))
• (((4 $ | * (2**3))
• (((4 $ | * (6))
• (((4⁶))
• 4096

• Lexical analysis or Scanner is the first phase of a compiler,
• It takes the modified source code from language preprocessors that are written in the form of sentences.
• A scanner or lexical analyzer reads the program from left to right, organize them into tokens and pass those tokens to the next level.

• A compiler for a high-level language that runs on one machine and produces code for a different machine is called cross compiler.
• A one-pass compiler is a compiler that passes through the source code of each compilation unit only once. traverses the program only once.
• A multi-pass compiler or two pass compiler is a type of compiler that processes the source code or abstract syntax tree of a program several times.
• A one-pass compilers is faster than multi-pass compilers.

• Absolute loader is a kind of loader in which relocated object files are created, loader accepts these files and places them at a specified location in the memory.
• This type of loader is called absolute loader because no relocating information is needed, rather it is obtained from the programmer or assembler.

Both (A) and (B)

S    → xxW(print “1”)
W → Sz(print “3”)
S   → xxW(print “1”)
W → Sz(print “3”)
S   →  y(print “2”)
Answer is option(C) 23131

Method : 2

Answer is option(C) 23131

Synthesized attributes follows bottom up parsing evaluation.

Example :
X -> Y | Z  i attribute is there in X,Y and Z
X.i = f( Y.i , Z.i ) means parent is taking attribute from there children

Bottom Up Parsers
LR( 0 ) , SLR( 1 ) , LR( 1 ) , LALR( 1 ) and Operator Precedence

Top Down Parsers
Non Recursive descent ( LL( 1 ) ) and Recursive descent

LR Parsers which are generated from LR grammar are also coming under bottom up parsing fashion Therefore option(C) is correct.

An assembler directive is a message to the assembler that tells the assembler something it needs to know in order to carry out the assembly process; for example, an assemble directive test the assembler where a program is to be located in memory.
Basic Assembly directives
EQU →Equate
ORG →Origin
START → Start (Define the start of the first control section in a program)
END → End (End of assembly language program and "starting address" for execution)

• Assembly languages are hardware dependent; there is a different one for each CPU series.
• Assembly language (or Assembler) is a compiled, low-level computer language. It is processor-dependent, since it basically translates the Assembler's mnemonics directly into the commands a particular CPU understands, on a one-to-one basis.
• These Assembler mnemonics are the instruction set for that processor

At the end of parsing, tokens are identified.

• Dead code elimination is a compiler optimization to remove code which does not affect the program results.
• Removing such code has several benefits: it shrinks program size, an important consideration in some contexts, and it allows the running program to avoid executing irrelevant operations, which reduces its running time.
• It can also enable further optimizations by simplifying program structure. Dead code includes code that can never be executed (unreachable code), and code that only affects dead variables (written to, but never read again), that is, irrelevant to the program.

A parse tree is an annotated parse tree if It shows attribute values at each node for given input string. The process of computing the attribute values at the nodes is called annotating or decorating the parse tree.

In a two pass compiler, during the first pass user defined address symbols are correlated with their binary equivalent

A single instruction in an assembly language program contains one macro operation

• The absolute loader is a kind of loader in which relocated object files are created, loader accepts these files and places them at a specified location in the memory.
• This type of loader is called absolute loader because no relocating information is needed, rather it is obtained from the programmer or assembler.
• The starting address of every module is known to the programmer, this corresponding starting address is stored in the object file then the task of loader becomes very simple that is to simply place the executable form of the machine instructions at the locations mentioned in the object file.
• In this scheme, the programmer or assembler should have knowledge of memory management. The programmer should take care of two things:
  • Specification of starting address of each module to be used. If some modification is done in some module then the length of that module may vary. This causes a change in the starting address of immediate next modules, it's then the programmer's duty to make necessary changes in the starting address of respective modules.
  • While branching from one segment to another the absolute starting address of respective module is to be known by the programmer so that such address can be specified at respective JMP instruction.

Top-down parsers come in two forms

• Predictive Parsers
  • Predictive parser is a recursive descent parser, which has the capability to predict which   production is to be used to replace the input string.­
  • Predict the production rule to be applied using lookahead tokens­
  ­
• Backtracking Parsers Will try different productions, backing up when a parse fails

Top-down parsers are predictive parsers, because next tokens are predicted