A compiler is a program that reads a program written in one language the source language & translate it into an equivalent program in another language- the target language.Compiler
compiler-compiler is a tool, which is used to develop the construct of compiler.It permits a portion of the specification of a language to be non-procedural rather than procedural.Compiler-Compiler :
Instead of writing a program to perform syntax analysis, the user writes a CFG & the Compiler-compiler automatically converts that grammar into a program for syntax analysis.Example:
TranslatorTranslator is program that performs the task of converting a program written in programming language into a program in another programming language- There are generally used three types of translators.These are- Compiler Interpreters Assemblers
When one or more phase are combined into a module than the module is referred as pass. A pass is read the source program to the output of the previous pass, makes the transformations specified by its phases & writes output into an intermediate file.Pass :
Pre-processor produces a input to compilers which are perform the following function:- Macro Processing File Inclusion Rational Preprocessor & Extension of LanguagePre-Processor :
Copy-restore:A hybrid between call-by-value & call-by-reference is copy restore linkage. 1.Before the call, the actual parameters are evaluated. The r-values of the actual are passed to the called procedure as in call by value. The l-value of those actual parameters having l-values is determined before the call. 2. When the call returns, the current r-values of the formal parameters are copied back into the l-values of the actual, using the l-values computed before the call. Generally, Copy restore is used by FORTAN implementation.
L-value :The term "l-value" refers to values that are appropriate on the left of an asignment expression.So, l-values are location.Sometimes, an expression has no l-value. Example: i:=5; [here i is l-value] A B [A is l-value] A +B [the expression has no l-value] P: = Q [P is served l-value]
R-Value:The term "r-value" refers to values that are appropriate on the right of an assignment/expression.That is, r-values are what we usually think of "values". Example: i:=5; [here 5 is r-value.] A B // A tensto B [B is r value] A+B [The expression is fully r-value] P: = Q; [Q is served r-value ]
Assembly code is passed to an assembler for further procesing that is, if the source language is assembly language & the target language is machine language, then the trasnlator is called an assembler.Assembler:
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. DAG for the expression is shown
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:Basic Blocks:
The advantages of generating intermediate code :The advantages of generating intermediate code 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.
There are some major issues in the design of a code generator. They are - Memory Management Instruction selection Register allocation Evaluation orderThe major issues in the design of a code generator
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.Dead elimination:
Describe primary structure-preserving transformations on basic blocks :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 : = b Dead-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.