Thursday, March 24, 2016
Discuss the capabilities of CFG
12:59 PM
No comments
The capabilities of CFG :
Context free grammars are capable of describing most of the syntax of programming language. suitable grammars for expressions can often be constructed using associatively & precedence information. So, context free grammar are most useful in describing nested structures such as balanced parentheses, matching begin-end's, corresponding if-then-else's & so on. These nested structures cannot be described by regular expression. The following grammars the string, which serves the language.
Stat if cond then stat
| if cond then stat else stat
|other -stat.What is CFG?Advantages of CFG
12:52 PM
No comments
Context Free Grammar : A CFG is a way of describing language by recursive rules. A CFG consists four tuples, denoted G = {V, T, P, S}
Where,
V = Finite set of variables. [Eg. {S, E}etc.]
T = Finite set of terminals. [Eg. {a, b, c,+}etc.]
P = Finite set of productions. [Eg. E E+E]
S = Start symbol.
Example :
Let a CFG which is given :
Here, V = {E}
T = {+, *, id}
S = E
So, the grammar notation is written as; G = (E, {+, *, id}, P, E)
Advantages of context free grammar :
- A grammar give a precise, yet easy to understand, syntactic specification of a programming language.
- An efficient parser can be constructed automatically from a properly designed grammar.
- A grammar imparts a structure to a program that is useful for its translation into object code for the detection of errors.
- Language ecvolved over a period of time.acquiring new constructs & performing additional tasks.
What is drawback of operator precedence parsing?
12:46 PM
No comments
Drawback of operator precedence parsing :
- Difficult to find token from the operator precedence parsing.
- It is itself tenuous. One can't always be sure the parser accepts exactly the desired language.
- Only a small class of grammar can be using operator precedence techniques.
What is Context Free Grammar With Example?
12:36 PM
No comments
Context Free Grammar : A CFG is a way of describing language by recursive rules. A CFG consists four tuples, denoted G = {V, T, P, S}
Where,
V = Finite set of variables. [Eg. {S, E}etc.]
T = Finite set of terminals. [Eg. {a, b, c,+}etc.]
P = Finite set of productions. [Eg. E E+E]
S = Start symbol.
Example :
Let a CFG which is given :
Here, V = {E}
T = {+, *, id}
S = E
So, the grammar notation is written as; G = (E, {+, *, id}, P, E)
What are the differences between single pass & multi-pass compiler?
12:25 PM
No comments
Single Pass Compiler | Multi-Pass Compiler |
---|---|
1. Single pass compiler can be made to use more space than multi-pass compiler | 1. Multi - pass compiler can be made to use less space than a single -pass compiler |
2. Single pass compiler is faster than a multi -pass compiler | 2. Multi - pass compiler is slower than a single pass compiler because each pass reads & writes an intermediate file. |
Translate the expression -
11:55 AM
No comments
Translate the expression -
-(a+b)*(c+d)+(a+b+c) into (ii) Quadruples
At first we construct the three address code the above expression :
Three address code :
0) T1 : = a+b
1) T2 : = -T1
2) T3 : = c+d
3) T4 : = T2*T3
4) T5 : = a+b
5) T6 : = T5+c
6) T7 : = T4+T6
-(a+b)*(c+d)+(a+b+c) into (ii) Quadruples
At first we construct the three address code the above expression :
Three address code :
0) T1 : = a+b
1) T2 : = -T1
2) T3 : = c+d
3) T4 : = T2*T3
4) T5 : = a+b
5) T6 : = T5+c
6) T7 : = T4+T6
SL NO | OP | ARG1 | ARG2 | RESULT |
---|---|---|---|---|
(0) | + | a | b | T1 |
(1) | uminus | T1 | - | T2 |
(2) | + | c | d | T3 |
(3) | * | T2 | T3 | T4 |
(4) | + | a | b | T5 |
(5) | + | T5 | c | T6 |
(6) | + | T4 | T6 | T7 |
Fig. (a) quadruple.
Translate the following assignment statement A : = -B*(C+D) into three address, quadruple & triple forms
11:39 AM
No comments
Here, given the expression - A: = -B*(C+D)
Three-address code :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
These statement are represented by quadruples as shown in fig . (a)
SL NO | OP | ARG1 | ARG2 | RESULT |
---|---|---|---|---|
(0) | Uminus | B | - | T1 |
(1) | + | C | D | T2 |
(2) | * | T1 | T2 | T3 |
(3) | := | T3 | - | A |
Fig. (a) quadruple representation of three -address statements.
These statement are represented by triples as shown in fig . (b)
SL NO | OP | ARG1 | ARG2 |
---|---|---|---|
(0) | Uminus | B | - |
(1) | + | C | D |
(2) | * | (0) | (1) |
(3) | := | A | (2) |
Fig. (b) triple representation of three -address statements.
Briefly describes quadruples, triples in representation of three address statements. What ate the benefits of quadruples over triples in optimizing compiler?
11:27 AM
No comments
Quardruples : Quadruples representation the three - address code by using four fields
These are -
OP, ARG1, ARG2 & RESULT.
Implementation of quadruples : Let us consider the following three - address code :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
These statement are represented by quadruples as shown in fig . (a)
SL NO | OP | ARG1 | ARG2 | RESULT |
---|---|---|---|---|
(0) | Uminus | B | - | T1 |
(1) | + | C | D | T2 |
(2) | * | T1 | T2 | T3 |
(3) | := | T3 | - | A |
Fig. (a) quadruple representation of three -address statements.
Triple : Triple representation the three address code by using three fields.
These are -
OP, ARG1, ARG2.
So, we use parenthesized number to represent pointer into the triple
structure.while symbol-table pointers are represented by names
themselves.
Implementation of quadruples : Let us consider the following three - address code :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
These statement are represented by quadruples as shown in fig . (a)
Fig. (b) triple representation of three -address statements.
The benefits of quadruples over triples in optimizing compiler : A more benefits of quadruples appear in an optimizing compiler, where we often move statements around.
Using the quadruples notation, the symbol table interposes an extra degree of indirection between the computation of a value & its use. If we move a statement computing A, the statements using A require no change. However, in the triples notation, moving a statements that defines a temporary value requires us to change all pointers to that statements in the ARG1 & ARG2 arrays. This problem makes triples difficult to use in an optimizing compiler.
SL NO | OP | ARG1 | ARG2 |
---|---|---|---|
(0) | Uminus | B | - |
(1) | + | C | D |
(2) | * | (0) | (1) |
(3) | := | A | (2) |
Fig. (b) triple representation of three -address statements.
The benefits of quadruples over triples in optimizing compiler : A more benefits of quadruples appear in an optimizing compiler, where we often move statements around.
Using the quadruples notation, the symbol table interposes an extra degree of indirection between the computation of a value & its use. If we move a statement computing A, the statements using A require no change. However, in the triples notation, moving a statements that defines a temporary value requires us to change all pointers to that statements in the ARG1 & ARG2 arrays. This problem makes triples difficult to use in an optimizing compiler.
Find the postfix notation for the following expressions -
10:11 AM
No comments
(i) (a+b) - c & (ii) a - (b+c)
(i) The postfix notation - (a+b)-c
= [ab+]-c
=ab+c-
(i) The postfix notation - a-(b+c)
=a-[bc+]
=abc+-
Discuss the purpose of the fields of an activation record
9:54 AM
No comments
Activation Code : Stack allocation collect fixed -storage by using activation record. The activation record contain the following steps -
- Storage for simple name & pointers to array & other data structures local to the procedure.
- Temporaries for expression evaluation & parameter passing.
- Information regarding attributes for local names & formal parameters, when these cannot be determined at compile time.
- The return address.
- A portion to the activation record of the caller.
It is customary & useful to place immediately above the Activation record Data whose size can't be determined until the procedure is called.
Pointers to the location of these arrays are stored at a fixed position in the activation record. Thus the compiler can generate code to access them indirectly though the top-of-stack pointer & for the array itself.
Write a translation scheme for providing three -address code for Boolean expressions : "OR", "AND" and "NOT"
9:32 AM
No comments
A OR B, A AND D, NOT D.
So, the translation scheme becomes -
T1 : = A OR B
T2 : = A AND D
T3 : = NOT D.What is Activation Code?
9:25 AM
2 comments
Activation Code : Stack allocation collect fixed -storage by using activation record. The activation record contain the following steps -
- Storage for simple name & pointers to array & other data structures local to the procedure.
- Temporaries for expression evaluation & parameter passing.
- Information regarding attributes for local names & formal parameters, when these cannot be determined at compile time.
- The return address.
- A portion to the activation record of the caller.
What is Postfix notation/Reverse Polish notation With Example?
9:17 AM
No comments
Postfix notation/Reverse Polish notation :
It is the form of an expression obtained from postorder traversal of the
tree representing this expression. So, in the postfix notation,
operators must be placed after the operands.
What is Prefix notation/Polish notation With Example?
9:14 AM
No comments
Prefix notation/Polish notation : It is the form of an expression obtained from preorder traversal of the tree representing this expression. So, in the prefix notation, operators must be placed before the operands.
What is infix notation with example?
9:08 AM
No comments
Infix notation : It is the form of an expression obtained from in order traversal of the tree representing this expression. So in the infix notation, Operators must be placed in the operands.
What is Intermediate Language with two properties?
9:05 AM
No comments
Intermediate Language with two properties : - After syntax & semantic analysis the compiler generates an explicit intermediate representation of the source program. This, intermediate representation as a program for an abstract machine.
It has two properties -
- It should be easy to produce &
- Easy to translate into the target program.
What is Object Program?
8:59 AM
No comments
Object Program : The output of a code generator is the object program. This takes a variety of forms : an absolute machine - language program, a locatable machine - language program, an assembly -language program & other language program.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVEExplain Syntax - Directed translation
2:53 AM
No comments
Syntax - Directed translation : Syntax - directed translation schemes to describe the output to generate for each input construct. A syntax - directed translation is merely a CFG in which a program fragment called an output action ( or sometimes a semantic action or semantic rule) is associated with each production for example, suppose output action is, associated with production A tensto XYZ. The action is executed whenever the syntax analyzer recognizing in its input a sub - string w which has a derivation of the form A or XYZ or w.
The syntax is :
Input string tensto parse tree tensto dependency graph tensto evaluation order for semantic rules.
What is the way to represent 3-address code? Write down the advantage & disadvantage of quadruples over triples?
2:42 AM
No comments
Three Address Code: Three address statements are a sequence of statements.
Typically,
the general form A : B op C, where A, & C are either programmer
defined names. Constants or compiler - generated temporary names. Op
stands for any operator, such as a fixed or floating -point arithmatic
operator or a logical operator on Boolean -valued data. Three address
statements usually contain three addresses, two for the operands &
one for the result.
Example : Let us consider the expression A : = -B*(C+D).
We get the following three-address code from the expression :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
The dis-advantages of quadruples over triples - quadruples tend to cluster the symbol table with temporary names. If we use integer codes for temporaries & don't enter temporaries in the symbol table.
The advantages of quadruples over triples : A more benefits of quadruples appear in an optimizing compiler, where we often move statements around. using the quadruple notation, the symbol table interposes an extra degree of indirection between the computation of a value & its use. if we move a statement computing A, the statements using A require no change. However, in the triples notation, moving a statements that defines a temporary value requires us to change all pointers to that statements in the ARG1 & ARG2 arrays. This problem makes triples difficult to use in an optimizing compiler.
Define different types of translation with example
2:23 AM
No comments
A translation is an input/output mapping. Generally three types of translation scheme are used -
- Three Address Statements
- Quadruples &
- Triples
Three Address Statements : Three address statements are a sequence of statements.
Typically, the general form A : B op C, where A, & C are either programmer defined names. Constants or compiler - generated temporary names. Op stands for any operator, such as a fixed or floating -point arithmatic operator or a logical operator on Boolean -valued data. Three address statements usually contain three addresses, two for the operands & one for the result.
Example : Let us consider the expression A : = -B*(C+D).
We get the following three-address code from the expression :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
Quardruples : Quadruples representation the three - address code by using four fields
These are -
OP, ARG1, ARG2 & RESULT.
Implementation of quadruples : Let us consider the following three - address code :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
These statement are represented by quadruples as shown in fig . (a)
SL NO | OP | ARG1 | ARG2 | RESULT |
---|---|---|---|---|
(0) | Uminus | B | - | T1 |
(1) | + | C | D | T2 |
(2) | * | T1 | T2 | T3 |
(3) | := | T3 | - | A |
Fig. (a) quadruple representation of three -address statements.
Triple : Triple representation the three address code by using three fields.
These are -
OP, ARG1, ARG2.
So, we use parenthesized number to represent pointer into the triple
structure.while symbol-table pointers are represented by names
themselves.
Implementation of quadruples : Let us consider the following three - address code :
T1 : = -B
T2 : = C+D
T3 : = T1+T2
A : = T3
These statement are represented by quadruples as shown in fig . (a)
SL NO | OP | ARG1 | ARG2 |
---|---|---|---|
(0) | Uminus | B | - |
(1) | + | C | D |
(2) | * | (0) | (1) |
(3) | := | A | (2) |
Fig. (b) triple representation of three -address statements.
Wednesday, March 23, 2016
What is Suffix?
11:57 PM
No comments
Suffix : A Suffix of a string is any number of trailing symbols of that string.
What is Prefix?
11:55 PM
No comments
Prefix : A prefix of a string is any number of leading symbols of that string.
What is String(Word)?
11:49 PM
No comments
String(Word) : A string (word) is a finite sequence of symbols of that string .
What is Symbol?
11:46 PM
No comments
Symbol : A symbol is an abstract entity set we shall not define formally; just an point & line are not defined in geometry.
What is Lexema?
11:36 PM
No comments
Lexema : A lexema is a sequence of characters in the source program that is matched by the pattern for a token.
Example : For Pascal statement -
Cons pi = 3.1416;
Here, the sub-string pi is a lexema for the token "identifier."
What is Token?
11:28 PM
No comments
Token : The string representing a program can be partitioned at the lowest level into a sequence of sub-string called tokens. Each token is a sequence of characters whose significant is possessed collectively rather than individually.
Example : Generally, these are used as tokens -
- Constants, e.g. 1.2.3.4.
- Operator symbols, e.g. +,-,*.EQ,
- Identifiers e.g. A, H2035B, SPEED,
- Keywords e.g, IF, GOTO, SUBROUTINE.
- Punctuation symbols, e.g. parenthesis, brackets, coma & semicolon.
What is Regular Expression? Properties of regular expression
11:16 PM
No comments
Regular Expression : The language accepts by finite automata are easily described by simple expression called regular expression.
Regular expression operators are union , concatenation & closure/star.
Properties of regular expression :
- Faka Set is a regular expression & denotes the empty set.
- Epsilon is regular expression & denotes the set {Epsilon}
- For each a in . a is a regular expression & denotes the set {a}.If r & s are regular expressions denoting the language R & S. respectively, then (r+s). (rs) & (r*) are regular expressions that denotes the sets RUS, RS & R* respectively.
Using suitable block diagram shows the different phases of a compiler & briefly describes the phases.
10:50 PM
No comments
A compiler operates in phases, each of which transform the source program from one representation to another. Generally, these are six types of phases in compiler. These are -
- Lexical Analysis
- Syntax Analysis
- Semantic Analysis
- Intermediate code generation
- Code Optimization
- Code Generation
Lexical Analysis : Linear Analysis is called lexical analysis or scanning. Linear analysis reads the character in the source program & groups them into tokens in which each token represents a logically cohesive sequence of characters such as identifier. A key words(if, while etc.). A punctuation character or multi-character operator like : =.
Syntax Analysis : Hierarchical analysis is called syntax analysis or parsing. in the syntax analysis, the character or tokens are grouped hierarchically into nested collection with collective meaning.
Semantic Analysis : The semantic analysis phase checks the source program for semantic errors & gathers type information for the sub-sequent code generation phase. It uses the hierarchical structure determined by the syntax - analysis phase to identify the operators & operands of expression & statements. An important component of semantic analysis is type checking.
What is Interpreter?
10:32 PM
No comments
Interpreter : Interpreter is kinds of translator that translates & execute each source language statement before translating & executing next one but don't produce an object program.
What is Assembler?
10:28 PM
No comments
Assembler : Assembly code is passed to an assembler for further processing that is, if the source language is assembly language language & the target language is machine language, Then the translator is called assembler.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE
What are the properties that good error detection & diagnostic should have?
10:22 PM
No comments
- Good error diagnostic can significantly help reduce debugging & maintenance effort. These are the properties of good error detection & diagnostic -
- The message should pinpoint the errors of the original source program. Rather than in terms of some internal representation that is totally mysterious to the user.
- The error message should be tasteful & understandable by the user.
From a compiler a designer point of view, what are the source of errors in compiler?
10:16 PM
No comments
- There are many sources to occur error. These are the source of errors in compiler-
- At the very onset, the design specifications for the program may be inconsistent or faulty.
- The algorithms are incorrect or inadequate (algorithmic errors).
- The programmer may introduce error in implementing the algorithm - such as logical errors or coding error.
- Key punching or transcription errors can occur when the program is types on to cards or into a file.
- The program may exceed a compiler or machine limit not impiled by the definition of the programming language.
- Compiler can inserts errors as it translates source program into an object program.This error is referred compiler errors.
Write the advantages of high -level language
10:17 AM
No comments
The advantages of high -level language : These are the advantages of high level language-
- Ease of understanding
- Naturalness
- Portability &
- Efficiency of use
Ease of understanding : - A high level language program is generally easier to read. Write & prove correct than is an assembly language program.
Naturalness : Much of the understanding of a high - level programming language comes from the ease with which one can express an algorithm in that language.
Portability : - User often be able to run their programs on a variety of machine. Language such as FROTAN or COBOL has relatively is well-defined "standard versions" & programs conforming to the standards should run on any machine.
Efficiency of use : - High level language is very efficient.
Write the necessary/motive of compiler
9:23 AM
No comments
The necessary/motive of compiler : A compiler is a program that reads a program written in one language - the source language & translates it into an equivalent program in another language - the target language.
So, the main motive of compiler that if reports to its user the presence of errors in the source program.
A compiler can also assist in producing reliable program. For Example, a compiler could check that the types of operands are compatible.
Compiler can also acts as index by using symbol table.
Some compiler makes the use of an assembler as an appendage.
Tuesday, March 22, 2016
Write some advantages & limitations of parses
11:50 AM
No comments
Pass: When one or more phases are combined into a module then the module is referred as pass. A pass is read the source program to the output of the previous pas, makes the transformations specified by its phases & writes output into an intermediate file.
Advantages :
- Reduced memory space.
- Requires less time.
Limitations of parses :-
- The interface between the lexical & syntactic analyzer can often be limited to a single token.
- It is very hard to perform code generation until the intermediate representation has been completely generated.
What is intermediate code? Why it is necessary in compiler?
11:41 AM
No comments
Intermediate Code : After syntax & semantic analysis the compiler generates an explicit intermediate representation of the source program. thsi, intermediate representation as a program for an abstract machine. It has two properties-
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE- It should be easy to produce &
- Easy to translate into the target program.
Necessary in compiler:
- To generate machine/assembly language
- To create stream of simple instructios after syntax analysis.
What are the types of errors found in different phases of compiler?
11:35 AM
No comments
- The lexical analyzer may be unable to proceed because the next token in the source program is misspelled.
- The syntaxb analyzer may be unable to infer structure for its input because a syntatic error such as a missing parenthesis has occured.
- The intermediate code generation detects an operator whose operands have incompatible types.
- The code optimizer, doing control flow analysis, may detect that certain statements can never be reached.
- The code generator may find a compiler - created control that is too large to fit in a word of the target machine.
- While entering information into the symbol table, the bookkeeping routine may discover an identifier.
Describe the main problem in code generation
11:24 AM
No comments
There are three main problems occur in code generation. They are-
- Deciding what machine instructions to generate.
- Deciding in what order the computations should be done.
- Deciding which register to use.
What instructions should we generate?
Most machines permit certain computations to be done in a variety of ways.
For Example: The target machine has an "add-one-to-storage" instruction (AOS), then for the three-address statement A : = A+1. We might generate the signal instruction AOS A.
rather than the more obvious sequence-
LOAD A
ADD# 1
STORE A
In what order should we perform computation?-
Some computation orders require fewer registers to hold intermediate results than others. Picking the best order is a very difficult problem in general.
What register should we use?
The register assignment problem occurs when the code generation. What is a DAG for basic blocks? Construct the DAG for the following basic blocks
10:58 AM
No comments
What is a DAG for basic blocks? Construct the DAG for the following basic blocks
DAG for the expression is shown
Here given the basic block-
a := b+c c : = b+c
b : = a-d d : = a-d
So, the DAG is -
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE
DAG(Directed acyclic graph):
A Directed acyclic graph is a graph with no cycles which gives a
picture of how the value computed by each statement in a basic block is
used in subsequent statement in the block . That is, a DAG has node for
every sub-expression of the expression. An interior node represents n
operator & its child represents an operand.
DAG is mainly used to identify the same expression.
Example: Let us the following expression-
a + a*(b-c)+(b-c)*d.
Here given the basic block-
a := b+c c : = b+c
b : = a-d d : = a-d
So, the DAG is -
Describe primary structure-preserving transformations on basic blocks
10:54 AM
No comments
Primary structure-preserving transformations on basic blocks-
- Common sub-expression elimination
- Dead-code elimination
- Renaming of temporary variable
- Interchanging of two independent-adjacent statements.
Common sub-expression elimination: Consider the basic block-
a : = b+c c : = b+c
b : = a-d d : = a-d
The 2nd and fourth statements compute same expression namely b + c - d. So, the transform basic block is as-
a : = b+c c : = b+c
b : = a-d d : = bDead-Code Elimination : Let us a variable x is dead, that is, never subsequently used. at the point where the statement x : = y + z appears in a basic block. Then this statement may be safely removed without changing the value of the basic block.
Renaming of temporary variable: Let us a statement t : = a+b where t is a temporary. If we change this statement t to u, then the value of basic block is not changed.
Interchange of statement: Let us consider the two adjacent statements-
t1 : = x+y
t2 : = a+b
We can interchange the two statement without effecting the value of the block if neithern a nor b is t1 & neither x nor y is t2. What do you understand by dead elimination?
10:46 AM
No comments
Dead elimination: A variable is live at a point in a program if its value can be used subsequently. Otherwise it is dead at that point. Let us a variable x is dead. That is, never subsequently used, at the point where the statement x : = y + z appears in a basic block. Then this statement may be safely removed without changing the value of the basic block.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVEWrite the major issues in the design of a code generator?
10:33 AM
No comments
There are some major issues in the design of a code generator. They are -
- Memory Management
- Instruction selection
- Register allocation
- Evaluation order
What are the advantages of generating intermediate code?
10:30 AM
No comments
Intermediate Code Generation: After syntax & semantic analysis the compiler generates an explicit intermediate representation of the source program. To implement intermediatecode such as -
- It should be easy to produce &
- Easy to translate into the target program
- Retargeting is faciliated.
- Finally, the representation of intermediate code is directly executed using a program, which is referred to as interpreter.
Basic Blocks
6:30 AM
No comments
Basic Blocks: A basic block is a sequence of consecutive statement in which flow of control enters at the beginning & leaves at the end without halt or possibility of branching except at the end of the basic block. The following sequence of three address statement form a basic block which is shown:
DAG(Directed acyclic graph)
6:26 AM
No comments
DAG(Directed acyclic graph): A Directed acyclic graph is a graph with no cycles which gives a picture of how the value computed by each statement in a basic block is used in subsequent statement in the block . That is, a DAG has node for every sub-expression of the expression. An interior node represents n operator & its child represents an operand.
DAG is mainly used to identify the same expression.
Example: Let us the following expression-
a + a*(b-c)+(b-c)*d.