Explore topic-wise InterviewSolutions in .

There are MAINLY three TYPES of INTERMEDIATE CODE REPRESENTATIONS.

1. Syntax tree
2. Postfix
3. Three address code

There are mainly three types of intermediate code representations.

• A Compiler for different machines can be created by ATTACHING different back END to the existing front ENDS of each machine.
• A Compiler for different source languages can be created by PROVING different front ends for corresponding source languages t existing back end.
• A machine independent code optimizer can be applied to intermediate code in order to optimize the code GENERATION.

Phrase level error recovery is implemented by FILLING in the blank entries in the predictive parsing table with POINTERS to error routines. These routines MAY change, insert, or delete symbols on the input and ISSUE appropriate error messages. They may also pop from the stack.

Phrase level error recovery is implemented by filling in the blank entries in the predictive parsing table with pointers to error routines. These routines may change, insert, or delete symbols on the input and issue appropriate error messages. They may also pop from the stack.

Kernel items, whish include the INITIAL ITEM, S’→ .S, and all items WHOSE dots are not at the left end.
Non-kernel items, which have their dots at the left end.

Kernel items, whish include the initial item, S’→ .S, and all items whose dots are not at the left end.
Non-kernel items, which have their dots at the left end.

A handle of a STRING is a substring that matches the right side of a production, and whose reduction to the nonterminal on the left side of the production REPRESENTS ONE step along the reverse of a rightmost DERIVATION.
A handle of a right – sentential form γ is a production A→β and a position of γ where the string β may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of γ. That is , if S =>αAw =>αβw,then A→β in the position FOLLOWING α is a handle of αβw.

A handle of a string is a substring that matches the right side of a production, and whose reduction to the nonterminal on the left side of the production represents one step along the reverse of a rightmost derivation.
A handle of a right – sentential form γ is a production A→β and a position of γ where the string β may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of γ. That is , if S =>αAw =>αβw,then A→β in the position following α is a handle of αβw.

The set of prefixes of right sentential forms that can appear on the STACK of a shift-reduce parser are CALLED viable prefixes. An equivalent definition of a viable PREFIX is that it is a prefix of a right sentential form that does not continue past the right end of the rightmost handle of that sentential form.

The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. An equivalent definition of a viable prefix is that it is a prefix of a right sentential form that does not continue past the right end of the rightmost handle of that sentential form.

• YACC is an automatic tool for GENERATING the parser PROGRAM.
• YACC STANDS for Yet Another Compiler Compiler which is basically the utility AVAILABLE from UNIX.
• Basically YACC is LALR parser GENERATOR.

The following are the problems ASSOCIATED with top down parsing:

• Backtracking
• LEFT recursion
• Left factoring
• AMBIGUITY

The following are the problems associated with top down parsing:

• SLR parser- SIMPLE LR parser
• LALR parser- lookahead LR parser
• CANONICAL LR parser

1. LR PARSERS can be constructed to RECOGNIZE most of the PROGRAMMING languages for which the context FREE grammar can be written.
2. The class of grammar that can be parsed by LR parser is a superset of class of grammars that can be parsed using PREDICTIVE parsers.
3. LR parsers work using non backtracking shift reduce technique yet it is efficient one.

1. LR parsers can be constructed to recognize most of the programming languages for which the context free grammar can be written.
2. The class of grammar that can be parsed by LR parser is a superset of class of grammars that can be parsed using predictive parsers.
3. LR parsers work using non backtracking shift reduce technique yet it is efficient one.

A grammar is said to be OPERATOR precedence if it possess the following properties:
1. No production on the right side is ε.
2. There should not be any production RULE possessing two adjacent non TERMINALS at the right hand side.

A grammar is said to be operator precedence if it possess the following properties:
1. No production on the right side is ε.
2. There should not be any production rule possessing two adjacent non terminals at the right hand side.

A grammar G is said to be ambiguous if it generates more than one PARSE tree for some sentence of LANGUAGE L(G).
i.e. both leftmost and RIGHTMOST derivations are same for the given sentence.

A grammar G is said to be ambiguous if it generates more than one parse tree for some sentence of language L(G).
i.e. both leftmost and rightmost derivations are same for the given sentence.

Derivation from S means generation of string w from S. For constructing derivation two things are important.
i) Choice of non terminal from SEVERAL others.
ii) Choice of rule from production RULES for CORRESPONDING non terminal.
Instead of CHOOSING the arbitrary non terminal one can choose
i) EITHER leftmost derivation – leftmost non terminal in a sentinel form.
ii) or rightmost derivation – rightmost non terminal in a sentinel form.

Derivation from S means generation of string w from S. For constructing derivation two things are important.
i) Choice of non terminal from several others.
ii) Choice of rule from production rules for corresponding non terminal.
Instead of choosing the arbitrary non terminal one can choose
i) either leftmost derivation – leftmost non terminal in a sentinel form.
ii) or rightmost derivation – rightmost non terminal in a sentinel form.

A context FREE grammar G is a COLLECTION of the following
· V is a set of non terminals
· T is a set of terminals
· S is a START symbol
· P is a set of production rules
G can be represented as G = (V,T,S,P)
Production rules are given in the following form
Non TERMINAL → (V U T)*

A context free grammar G is a collection of the following
· V is a set of non terminals
· T is a set of terminals
· S is a start symbol
· P is a set of production rules
G can be represented as G = (V,T,S,P)
Production rules are given in the following form
Non terminal → (V U T)*

Reasons for SEPARATING the ANALYSIS PHASE into lexical and syntax analyzers:

• Simpler design.
• Compiler efficiency is IMPROVED.
• Compiler PORTABILITY is enhanced.

Reasons for separating the analysis phase into lexical and syntax analyzers:

There are two IMPORTANT ISSUES in parsing.

1. SPECIFICATION of SYNTAX
2. Representation of INPUT after parsing.

There are two important issues in parsing.

POSSIBLE error recovery ACTIONS are:

• Panic mode recovery
• DELETING an extraneous character
• Inserting a missing character
• Replacing an incorrect character by a correct character
• TRANSPOSING two ADJACENT characters

Possible error recovery actions are:

Semantic analysis is one in which certain checks are performed to ENSURE that components of a program fit TOGETHER meaningfully.Mainly PERFORMS type checking.

Semantic analysis is one in which certain checks are performed to ensure that components of a program fit together meaningfully.Mainly performs type checking.

Hierarchical analysis is one in which the TOKENS are GROUPED hierarchically into nested collections with COLLECTIVE meaning.Also TERMED as Parsing.

Hierarchical analysis is one in which the tokens are grouped hierarchically into nested collections with collective meaning.Also termed as Parsing.

• One or more instances (+)
• Zero or one instance (?)
• Character CLASSES ([ABC] where a,b,C are ALPHABET symbols DENOTES the regular expressions a | b | c.)
• Non regular sets

An identifier is defined as a letter followed by ZERO or more letters or digits.
The REGULAR expression for an identifier is given as
letter (letter | DIGIT)*

An identifier is defined as a letter followed by zero or more letters or digits.
The regular expression for an identifier is given as
letter (letter | digit)*

• Union – L U M ={s | s is in L or s is in M}
• Concatenation – LM ={st | s is in L and t is in M}
• Kleene CLOSURE – L* (ZERO or more CONCATENATIONS of L)
• Positive Closure – L+ ( one or more concatenations of L)

Tokens- Sequence of characters that have a COLLECTIVE meaning.
Patterns- There is a set of STRINGS in the input for which the same TOKEN is produced as output. This set of strings is described by a rule called a pattern associated with the token
Lexeme- A sequence of characters in the source PROGRAM that is MATCHED by the pattern for a token.

Tokens- Sequence of characters that have a collective meaning.
Patterns- There is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token
Lexeme- A sequence of characters in the source program that is matched by the pattern for a token.

The following is a LIST of some COMPILER construction tools:

• PARSER generators
• Scanner generators
• Syntax-directed translation ENGINES
• Automatic code generators
• Data-flow engines

The following is a list of some compiler construction tools:

Systems to help with the compiler-writing PROCESS are often been referred to as compiler-compilers, compiler-generators or translator-writing systems.
Largely they are ORIENTED around a particular MODEL of languages , and they are SUITABLE for generating compilers of languages SIMILAR model.

Systems to help with the compiler-writing process are often been referred to as compiler-compilers, compiler-generators or translator-writing systems.
Largely they are oriented around a particular model of languages , and they are suitable for generating compilers of languages similar model.

The back end of compiler includes those portions that DEPEND on the TARGET machine and GENERALLY those portions do not depend on the SOURCE language, just the intermediate language. These include
· Code optimization
· Code generation, along with error handling and symbol- table operations.

The back end of compiler includes those portions that depend on the target machine and generally those portions do not depend on the source language, just the intermediate language. These include
· Code optimization
· Code generation, along with error handling and symbol- table operations.

The FRONT end consists of those phases or PARTS of phases that depend PRIMARILY on the source language and are largely independent of the target machine. These include
· Lexical and Syntactic analysis
· The creation of SYMBOL table
· Semantic analysis
· Generation of intermediate code
A certain amount of code optimization can be done by the front end as well. Also includes error handling that goes along with each of these phases.

The front end consists of those phases or parts of phases that depend primarily on the source language and are largely independent of the target machine. These include
· Lexical and Syntactic analysis
· The creation of symbol table
· Semantic analysis
· Generation of intermediate code
A certain amount of code optimization can be done by the front end as well. Also includes error handling that goes along with each of these phases.

COUSINS of the COMPILER are:

• PREPROCESSORS
• ASSEMBLERS
• LOADERS and Link-Editors

Cousins of the compiler are:

A symbol table is a data structure containing a record for each identifier, with FIELDS for the attributes of the identifier. The data structure allows US to find the record for each identifier quickly and to STORE or RETRIEVE data from that record quickly.
Whenever an identifier is detected by a lexical analyzer, it is entered into the symbol table. The attributes of an identifier cannot be determined by the lexical analyzer.

A symbol table is a data structure containing a record for each identifier, with fields for the attributes of the identifier. The data structure allows us to find the record for each identifier quickly and to store or retrieve data from that record quickly.
Whenever an identifier is detected by a lexical analyzer, it is entered into the symbol table. The attributes of an identifier cannot be determined by the lexical analyzer.

COMPILERS are CLASSIFIED as:

• Single- PASS
• Multi-pass
• Load-and-go
• Debugging or OPTIMIZING

Compilers are classified as:

The following are the VARIOUS phases of a COMPILER:

• LEXICAL Analyzer
• Syntax Analyzer
• Semantic Analyzer
• Intermediate CODE GENERATOR
• Code optimizer
• Code generator

The following are the various phases of a compiler:

LINEAR ANALYSIS is one in which the stream of characters making up the SOURCE program is read from left to right and grouped into tokens that are sequences of characters having a collective meaning.Also CALLED lexical analysis or scanning.

Linear analysis is one in which the stream of characters making up the source program is read from left to right and grouped into tokens that are sequences of characters having a collective meaning.Also called lexical analysis or scanning.

Symbol table is a DATA STRUCTURE used by the compiler to keep TRACK of semantics of the variables. It stores information about SCOPE and binding information about NAMES.

Symbol table is a data structure used by the compiler to keep track of semantics of the variables. It stores information about scope and binding information about names.

In dynamic scoping a use of non-LOCAL variable refers to the non-local data declared in most recently called and still active procedure. THEREFORE each time NEW FINDINGS are set up for local names called procedure. In dynamic scoping symbol tables can be required at run time.

In dynamic scoping a use of non-local variable refers to the non-local data declared in most recently called and still active procedure. Therefore each time new findings are set up for local names called procedure. In dynamic scoping symbol tables can be required at run time.

The activation record is a block of memory used for MANAGING the information needed by a single execution of a procedure.

Various fields F activation record are:

•  Temporary variables
•  Local variables
•  SAVED machine registers
•  Control link
•  ACCESS link
•  Actual parameters
•  RETURN values

The activation record is a block of memory used for managing the information needed by a single execution of a procedure.

Various fields f activation record are:

The STRATEGIES are:

• STATIC ALLOCATION
• STACK allocation
• HEAP allocation

The strategies are:

•To REDUCE the SIZE of the CODE i.e. to OBTAIN the space complexity.
•To reduce the frequency of execution of code i.e. to obtain the time complexity.

•To reduce the size of the code i.e. to obtain the space complexity.
•To reduce the frequency of execution of code i.e. to obtain the time complexity.

• The semantic EQUIVALENCE of the source program must not be changed.
• The improvement over the program efficiency must be achieved without changing the algorithm of the program.
• The machine dependent optimization is based on the characteristics of the target machine for the instruction set used and addressing modes used for the instructions to produce the efficient target code.
• The machine independent optimization is based on the characteristics of the programming languages for appropriate programming structure and usage of efficient arithmetic PROPERTIES in order to reduce the execution time.
• Available expressions.
• REACHING definitions.
• LIVE variables.
• BUSY variables.

• CALL by VALUE
• Call by REFERENCE
• Copy-restore
• Call by NAME

The source code should be such that it should produce MINIMUM amount of target code.
There should not be any unreachable code.
Dead code should be completely removed from source language.
The optimizing COMPILERS should apply following code improving transformations on source language.

1. common subexpression elimination
2. dead code elimination
3. code movement
4. STRENGTH REDUCTION

The source code should be such that it should produce minimum amount of target code.
There should not be any unreachable code.
Dead code should be completely removed from source language.
The optimizing compilers should apply following code improving transformations on source language.

CODE motion is an optimization technique in which amount of code in a loop is DECREASED. This transformation is applicable to the expression that YIELDS the same RESULT independent of the number of times the loop is executed. Such an expression is placed before the loop.

Code motion is an optimization technique in which amount of code in a loop is decreased. This transformation is applicable to the expression that yields the same result independent of the number of times the loop is executed. Such an expression is placed before the loop.

• USING hash function we should obtain exact LOCATIONS of name in symbol table.
• The hash function should result in uniform DISTRIBUTION of NAMES in symbol table.
• The hash function should be such that there will be minimum NUMBER of collisions. 
• Collision is such a situation where hash function results in same location for storing the names.

ANALYSIS consists of THREE phases:

1. Linear Analysis.
2. HIERARCHICAL Analysis.
3. Semantic Analysis.

Analysis consists of three phases:

Analysis and Synthesis are the TWO parts of compilation.

• The analysis part BREAKS up the source program into constituent PIECES and creates an intermediate representation of the source program.
• The synthesis part constructs the DESIRED target program from the intermediate representation.

Analysis and Synthesis are the two parts of compilation.

A compiler is a PROGRAM that reads a program written in one language –the source language and translates it into an EQUIVALENT program in another language-the target language. The compiler REPORTS to its USER the presence of errors in the source program.

A compiler is a program that reads a program written in one language –the source language and translates it into an equivalent program in another language-the target language. The compiler reports to its user the presence of errors in the source program.